BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

David Poulin

David Poulin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phcond-mat.str-elcond-mat.stat-mechInformation Theorymath.IThep-thComputational Complexitycond-mat.mes-hallmath-phmath.MP

Catalog footprint

What is connected

39works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

39 published item(s)

preprint2020arXiv

Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm

We present a detailed circuit implementation of Szegedy's quantization of the Metropolis-Hastings walk. This quantum walk is usually defined with respect to an oracle. We find that a direct implementation of this oracle requires costly arithmetic operations and thus reformulate the quantum walk in a way that circumvents the implementation of that specific oracle and which closely follows the classical Metropolis-Hastings walk. We also present heuristic quantum algorithms that use the quantum walk in the context of discrete optimization problems and numerically study their performances. Our numerical results indicate polynomial quantum speedups in heuristic settings.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Fault-tolerant gates on hypergraph product codes

Hypergraph product codes are a class of quantum low density parity check (LDPC) codes discovered by Tillich and Zémor. These codes have a constant encoding rate and were recently shown to have a constant fault-tolerant error threshold. With these features, they asymptotically offer a smaller overhead compared to topological codes. However, existing techniques to perform logical gates in hypergraph product codes require many separate code blocks, so only becomes effective with a very large number of logical qubits. Here, we demonstrate how to perform Clifford gates on this class of codes using code deformation. To this end, we generalize punctures and wormhole defects, the latter introduced in a companion paper. Together with state injection, we can perform a universal set of gates within a single block of the class of hypergraph product codes.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Topological wormholes

Locality plays a fundamental role in quantum computation but also severely restricts our ability to store and process quantum information. We argue that this restriction may be unwarranted and re-examine quantum error correcting codes. We proceed to introduce new defects on the surface code called wormholes. These novel defects entangle two spatially separated sectors of the lattice. When anyonic excitations enter the mouth of a wormhole, they emerge through the other mouth. Wormholes thus serve to connect two spatially separated sectors of a flat, $2$D lattice. We show that these defects are capable of encoding logical qubits and can be used to perform all gates in the Clifford group.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A linear-time benchmarking tool for generalized surface codes

Quantum information processors need to be protected against errors and faults. One of the most widely considered fault-tolerant architecture is based on surface codes. While the general principles of these codes are well understood and basic code properties such as minimum distance and rate are easy to characterize, a code's average performance depends on the detailed geometric layout of the qubits. To date, optimizing a surface code architecture and comparing different geometric layouts relies on costly numerical simulations. Here, we propose a benchmarking algorithm for simulating the performance of surface codes, and generalizations thereof, that runs in linear time. We implemented this algorithm in a software that generates performance reports and allows to quickly compare different architectures.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Detecting Topological Order with Ribbon Operators

We introduce a numerical method for identifying topological order in two-dimensional models based on one-dimensional bulk operators. The idea is to identify approximate symmetries supported on thin strips through the bulk that behave as string operators associated to an anyon model. We can express these ribbon operators in matrix product form and define a cost function that allows us to efficiently optimize over this ansatz class. We test this method on spin models with abelian topological order by finding ribbon operators for $\mathbb{Z}_d$ quantum double models with local fields and Ising-like terms. In addition, we identify ribbons in the abelian phase of Kitaev's honeycomb model which serve as the logical operators of the encoded qubit for the quantum error-correcting code. We further identify the topologically encoded qubit in the quantum compass model, and show that despite this qubit, the model does not support topological order. Finally, we discuss how the method supports generalizations for detecting nonabelian topological order.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Generalized surface codes and packing of logical qubits

We consider a notion of relative homology (and cohomology) for surfaces with two types of boundaries. Using this tool, we study a generalization of Kitaev's code based on surfaces with mixed boundaries. This construction includes both Bravyi and Kitaev's and Freedman and Meyer's extension of Kitaev's toric code. We argue that our generalization offers a denser storage of quantum information. In a planar architecture, we obtain a three-fold overhead reduction over the standard architecture consisting of a punctured square lattice.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Can long-range interactions stabilize quantum memory at nonzero temperature?

A two-dimensional topologically ordered quantum memory is well protected against error if the energy gap is large compared to the temperature, but this protection does not improve as the system size increases. We review and critique some recent proposals for improving the memory time by introducing long-range interactions among anyons, noting that instability with respect to small local perturbations of the Hamiltonian is a generic problem for such proposals. We also discuss some broader issues regarding the prospects for scalable quantum memory in two-dimensional systems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Reducing the overhead for quantum computation when noise is biased

We analyse a model for fault-tolerant quantum computation with low overhead suitable for situations where the noise is biased. The basis for this scheme is a gadget for the fault-tolerant preparation of magic states that enable universal fault-tolerant quantum computation using only Clifford gates that preserve the noise bias. We analyse the distillation of $|T\rangle$-type magic states using this gadget at the physical level, followed by concatenation with the 15-qubit quantum Reed-Muller code, and comparing our results with standard constructions. In the regime where the noise bias (rate of Pauli $Z$ errors relative to other single-qubit errors) is greater than a factor of 10, our scheme has lower overhead across a broad range of relevant noise rates.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Thermalization, Error-Correction, and Memory Lifetime for Ising Anyon Systems

We consider two-dimensional lattice models that support Ising anyonic excitations and are coupled to a thermal bath. We propose a phenomenological model for the resulting short-time dynamics that includes pair-creation, hopping, braiding, and fusion of anyons. By explicitly constructing topological quantum error-correcting codes for this class of system, we use our thermalization model to estimate the lifetime of the quantum information stored in the encoded spaces. To decode and correct errors in these codes, we adapt several existing topological decoders to the non-Abelian setting. We perform large-scale numerical simulations of these two-dimensional Ising anyon systems and find that the thresholds of these models range between 13% to 25%. To our knowledge, these are the first numerical threshold estimates for quantum codes without explicit additive structure.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fault-tolerant conversion between the Steane and Reed-Muller quantum codes

Steane's 7-qubit quantum error-correcting code admits a set of fault-tolerant gates that generate the Clifford group, which in itself is not universal for quantum computation. The 15-qubit Reed-Muller code also does not admit a universal fault-tolerant gate set but possesses fault-tolerant T and control-control-Z gates. Combined with the Clifford group, either of these two gates generate a universal set. Here, we combine these two features by demonstrating how to fault-tolerantly convert between these two codes, providing a new method to realize universal fault-tolerant quantum computation. One interpretation of our result is that both codes correspond to the same subsystem code in different gauges. Our scheme extends to the entire family of quantum Reed-Muller codes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Reducing the quantum computing overhead with complex gate distillation

In leading fault-tolerant quantum computing schemes, accurate transformation are obtained by a two-stage process. In a first stage, a discrete, universal set of fault-tolerant operations is obtained by error-correcting noisy transformations and distilling resource states. In a second stage, arbitrary transformations are synthesized to desired accuracy by combining elements of this set into a circuit. Here, we present a scheme which merges these two stages into a single one, directly distilling complex transformations. We find that our scheme can reduce the total overhead to realize certain gates by up to a few orders of magnitude. In contrast to other schemes, this efficient gate synthesis does not require computationally intensive compilation algorithms, and a straightforward generalization of our scheme circumvents compilation and synthesis altogether.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Tensor Networks and Quantum Error Correction

We establish several relations between quantum error correction (QEC) and tensor network (TN) methods of quantum many-body physics. We exhibit correspondences between well-known families of QEC codes and TNs, and demonstrate a formal equivalence between decoding a QEC code and contracting a TN. We build on this equivalence to propose a new family of quantum codes and decoding algorithms that generalize and improve upon quantum polar codes and successive cancellation decoding in a natural way.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Trotter Step Size Required for Accurate Quantum Simulation of Quantum Chemistry

The simulation of molecules is a widely anticipated application of quantum computers. However, recent studies \cite{WBCH13a,HWBT14a} have cast a shadow on this hope by revealing that the complexity in gate count of such simulations increases with the number of spin orbitals $N$ as $N^8$, which becomes prohibitive even for molecules of modest size $N\sim 100$. This study was partly based on a scaling analysis of the Trotter step required for an ensemble of random artificial molecules. Here, we revisit this analysis and find instead that the scaling is closer to $N^6$ in worst case for real model molecules we have studied, indicating that the random ensemble fails to accurately capture the statistical properties of real-world molecules. Actual scaling may be significantly better than this due to averaging effects. We then present an alternative simulation scheme and show that it can sometimes outperform existing schemes, but that this possibility depends crucially on the details of the simulated molecule. We obtain further improvements using a version of the coalescing scheme of \cite{WBCH13a}; this scheme is based on using different Trotter steps for different terms. The method we use to bound the complexity of simulating a given molecule is efficient, in contrast to the approach of \cite{WBCH13a,HWBT14a} which relied on exponentially costly classical exact simulation.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Branching MERA codes: a natural extension of polar codes

We introduce a new class of circuits for constructing efficiently decodable error-correction codes, based on a recently discovered contractible tensor network. We perform an in-depth study of a particular example that can be thought of as an extension to Arikan's polar code. Notably, our numerical simulation show that this code polarizes the logical channels more strongly while retaining the log-linear decoding complexity using the successive cancellation decoder. These codes also display improved error-correcting capability with only a minor impact on decoding complexity. Efficient decoding is realized using powerful graphical calculus tools developed in the field of quantum many-body physics. In a companion paper, we generalize our construction to the quantum setting and describe more in-depth the relation between classical and quantum error correction and the graphical calculus of tensor networks.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fault-Tolerant Renormalization Group Decoder for Abelian Topological Codes

We present a three-dimensional generalization of a renormalization group decoding algorithm for topological codes with Abelian anyonic excitations that we previously introduced for two dimensions. This 3D implementation extends our previous 2D algorithm by incorporating a failure probability of the syndrome measurements, i.e., it enables fault-tolerant decoding. We report a fault-tolerant storage threshold of 1.9(4)% for Kitaev's toric code subject to a 3D bit-flip channel (i.e. including imperfect syndrome measurements). This number is to be compared with the 2.9% value obtained via perfect matching. The 3D generalization inherits many properties of the 2D algorithm, including a complexity linear in the space-time volume of the memory, which can be parallelized to logarithmic time.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Hardness of decoding quantum stabilizer codes

In this article we address the computational hardness of optimally decoding a quantum stabilizer code. Much like classical linear codes, errors are detected by measuring certain check operators which yield an error syndrome, and the decoding problem consists of determining the most likely recovery given the syndrome. The corresponding classical problem is known to be NP-complete, and a similar decoding problem for quantum codes is also known to be NP-complete. However, this decoding strategy is not optimal in the quantum setting as it does not take into account error degeneracy, which causes distinct errors to have the same effect on the code. Here, we show that optimal decoding of stabilizer codes is computationally much harder than optimal decoding of classical linear codes, it is #P.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Subsystem surface codes with three-qubit check operators

We propose a simplified version of the Kitaev's surface code in which error correction requires only three-qubit parity measurements for Pauli operators XXX and ZZZ. The new code belongs to the class of subsystem stabilizer codes. It inherits many favorable properties of the standard surface code such as encoding of multiple logical qubits on a planar lattice with punctured holes, efficient decoding by either minimum-weight matching or renormalization group methods, and high error threshold. The new subsystem surface code (SSC) gives rise to an exactly solvable Hamiltonian with 3-qubit interactions, topologically ordered ground state, and a constant energy gap. We construct a local unitary transformation mapping the SSC Hamiltonian to the one of the ordinary surface code thus showing that the two Hamiltonians belong to the same topological class. We describe error correction protocols for the SSC and determine its error thresholds under several natural error models. In particular, we show that the SSC has error threshold approximately 0.6% for the standard circuit-based error model studied in the literature. We also consider a model in which three-qubit parity operators can be measured directly. We show that the SSC has error threshold approximately 0.97% in this setting.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Algorithms for the Markov Entropy Decomposition

The Markov entropy decomposition (MED) is a recently-proposed, cluster-based simulation method for finite temperature quantum systems with arbitrary geometry. In this paper, we detail numerical algorithms for performing the required steps of the MED, principally solving a minimization problem with a preconditioned Newton's algorithm, as well as how to extract global susceptibilities and thermal responses. We demonstrate the power of the method with the spin-1/2 XXZ model on the 2D square lattice, including the extraction of critical points and details of each phase. Although the method shares some qualitative similarities with exact-diagonalization, we show the MED is both more accurate and significantly more flexible.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Degenerate Viterbi decoding

We present a decoding algorithm for quantum convolutional codes that finds the class of degenerate errors with the largest probability conditioned on a given error syndrome. The algorithm runs in time linear with the number of qubits. Previous decoding algorithms for quantum convolutional codes optimized the probability over individual errors instead of classes of degenerate errors. Using Monte Carlo simulations, we show that this modification to the decoding algorithm results in a significantly lower block error rate.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Local topological order inhibits thermal stability in 2D

We study the robustness of quantum information stored in the degenerate ground space of a local, frustration-free Hamiltonian with commuting terms on a 2D spin lattice. On one hand, a macroscopic energy barrier separating the distinct ground states under local transformations would protect the information from thermal fluctuations. On the other hand, local topological order would shield the ground space from static perturbations. Here we demonstrate that local topological order implies a constant energy barrier, thus inhibiting thermal stability.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Practical learning method for multi-scale entangled states

We describe a method for reconstructing multi-scale entangled states from a small number of efficiently-implementable measurements and fast post-processing. The method only requires single particle measurements and the total number of measurements is polynomial in the number of particles. Data post-processing for state reconstruction uses standard tools, namely matrix diagonalisation and conjugate gradient method, and scales polynomially with the number of particles. Our method prevents the build-up of errors from both numerical and experimental imperfections.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quantum error correction benchmarks for continuous weak parity measurements

We present an experimental procedure to determine the usefulness of a measurement scheme for quantum error correction (QEC). A QEC scheme typically requires the ability to prepare entangled states, to carry out multi-qubit measurements, and to perform certain recovery operations conditioned on measurement outcomes. As a consequence, the experimental benchmark of a QEC scheme is a tall order because it requires the conjuncture of many elementary components. Our scheme opens the path to experimental benchmarks of individual components of QEC. Our numerical simulations show that certain parity measurements realized in circuit quantum electrodynamics are on the verge of being useful for QEC.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quantum Markov Networks and Commuting Hamiltonians

Quantum Markov networks are a generalization of quantum Markov chains to arbitrary graphs. They provide a powerful classification of correlations in quantum many-body systems---complementing the area law at finite temperature---and are therefore useful to understand the powers and limitations of certain classes of simulation algorithms. Here, we extend the characterization of quantum Markov networks and in particular prove the equivalence of positive quantum Markov networks and Gibbs states of Hamiltonians that are the sum of local commuting terms on graphs containing no triangles. For more general graphs we demonstrate the equivalence between quantum Markov networks and Gibbs states of a class of Hamiltonians of intermediate complexity between commuting and general local Hamiltonians.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Practical characterization of quantum devices without tomography

Quantum tomography is the main method used to assess the quality of quantum information processing devices, but its complexity presents a major obstacle for the characterization of even moderately large systems. The number of experimental settings required to extract complete information about a device grows exponentially with its size, and so does the running time for processing the data generated by these experiments. Part of the problem is that tomography generates much more information than is usually sought. Taking a more targeted approach, we develop schemes that enable (i) estimating the fidelity of an experiment to a theoretical ideal description, (ii) learning which description within a reduced subset best matches the experimental data. Both these approaches yield a significant reduction in resources compared to tomography. In particular, we demonstrate that fidelity can be estimated from a number of simple experimental settings that is independent of the system size, removing an important roadblock for the experimental study of larger quantum information processing units.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space

We consider the manifold of all quantum many-body states that can be generated by arbitrary time-dependent local Hamiltonians in a time that scales polynomially in the system size, and show that it occupies an exponentially small volume in Hilbert space. This implies that the overwhelming majority of states in Hilbert space are not physical as they can only be produced after an exponentially long time. We establish this fact by making use of a time-dependent generalization of the Suzuki-Trotter expansion, followed by a counting argument. This also demonstrates that a computational model based on arbitrarily rapidly changing Hamiltonians is no more powerful than the standard quantum circuit model.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Universal topological phase of 2D stabilizer codes

Two topological phases are equivalent if they are connected by a local unitary transformation. In this sense, classifying topological phases amounts to classifying long-range entanglement patterns. We show that all 2D topological stabilizer codes are equivalent to several copies of one universal phase: Kitaev's topological code. Error correction benefits from the corresponding local mappings.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A renormalization group decoding algorithm for topological quantum codes

Topological quantum error-correcting codes are defined by geometrically local checks on a two-dimensional lattice of quantum bits (qubits), making them particularly well suited for fault-tolerant quantum information processing. Here, we present a decoding algorithm for topological codes that is faster than previously known algorithms and applies to a wider class of topological codes. Our algorithm makes use of two methods inspired from statistical physics: renormalization groups and mean-field approximations. First, the topological code is approximated by a concatenated block code that can be efficiently decoded. To improve this approximation, additional consistency conditions are imposed between the blocks, and are solved by a belief propagation algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Efficient Direct Tomography for Matrix Product States

In this note, we describe a method for reconstructing matrix product states from a small number of efficiently-implementable measurements. Our method is exponentially faster than standard tomography, and it can also be used to certify that the unknown state is an MPS. The basic idea is to use local unitary operations to measure in the Schmidt basis, giving direct access to the MPS representation. This compares favorably with recently and independently proposed methods that recover the MPS tensors by performing a variational minimization, which is computationally intractable in certain cases. Our method also has the advantage of recovering any MPS, while other approaches were limited to special classes of states that exclude important examples such as GHZ and W states.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Fast Decoders for Topological Quantum Codes

We present a family of algorithms, combining real-space renormalization methods and belief propagation, to estimate the free energy of a topologically ordered system in the presence of defects. Such an algorithm is needed to preserve the quantum information stored in the ground space of a topologically ordered system and to decode topological error-correcting codes. For a system of linear size L, our algorithm runs in time log L compared to L^6 needed for the minimum-weight perfect matching algorithm previously used in this context and achieves a higher depolarizing error threshold.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Information preserving structures: A general framework for quantum zero-error information

Quantum systems carry information. Quantum theory supports at least two distinct kinds of information (classical and quantum), and a variety of different ways to encode and preserve information in physical systems. A system's ability to carry information is constrained and defined by the noise in its dynamics. This paper introduces an operational framework, using information-preserving structures to classify all the kinds of information that can be perfectly (i.e., with zero error) preserved by quantum dynamics. We prove that every perfectly preserved code has the same structure as a matrix algebra, and that preserved information can always be corrected. We also classify distinct operational criteria for preservation (e.g., "noiseless", "unitarily correctible", etc.) and introduce two new and natural criteria for measurement-stabilized and unconditionally preserved codes. Finally, for several of these operational critera, we present efficient (polynomial in the state-space dimension) algorithms to find all of a channel's information-preserving structures.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Lieb-Robinson Bound and Locality for General Markovian Quantum Dynamics

The Lieb-Robinson bound shows the existence of a maximum speed of signal propagation in discrete quantum mechanical systems with local interactions. This generalizes the concept of relativistic causality beyond field theory, and provides a powerful tool in theoretical condensed matter physics and quantum information science. Here, we extend the scope of this seminal result by considering general Markovian quantum evolution, where we prove that an equivalent bound holds. In addition, we use the generalized bound to demonstrate that correlations in the stationary state of a Markov process decay on a length-scale set by the Lieb-Robinson velocity and the system's relaxation time.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Markov entropy decomposition: a variational dual for quantum belief propagation

We present a lower bound for the free energy of a quantum many-body system at finite temperature. This lower bound is expressed as a convex optimization problem with linear constraints, and is derived using strong subadditivity of von Neumann entropy and a relaxation of the consistency condition of local density operators. The dual to this minimization problem leads to a set of quantum belief propagation equations, thus providing a firm theoretical foundation to that approach. The minimization problem is numerically tractable, and we find good agreement with quantum Monte Carlo for the spin-half Heisenberg anti-ferromagnet in two dimensions. This lower bound complements other variational upper bounds. We discuss applications to Hamiltonian complexity theory and give a generalization of the structure theorem of Hayden, Jozsa, Petz and Winter to trees in an appendix.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Coarse grained belief propagation for simulation of interacting quantum systems at all temperatures

We continue our numerical study of quantum belief propagation initiated in [Phys. Rev. A, 77 (2008), p. 052318]. We demonstrate how the method can be expressed in terms of an effective thermal potential that materializes when the system presents quantum correlations, but is insensitive to classical correlations. The thermal potential provides an efficient means to assess the precision of belief propagation on graphs with no loops. We illustrate these concepts using the one-dimensional quantum Ising model and compare our results with exact solutions. We also use the method to study the transverse field quantum Ising spin glass for which we obtain a phase diagram that is largely in agreement with the one obtained in [arXiv:0706.4391] using a different approach. Finally, we introduce the coarse grained belief propagation (CGBP) algorithm to improve belief propagation at low temperatures. This method combines the reliability of belief propagation at high temperatures with the ability of entanglement renormalization to efficiently describe low energy subspaces of quantum systems with local interactions. With CGBP, thermodynamic properties of quantum systems can be calculated with a high degree of accuracy at all temperatures.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer

We present a quantum algorithm to prepare the thermal Gibbs state of interacting quantum systems. This algorithm sets a universal upper bound D^alpha on the thermalization time of a quantum system, where D is the system's Hilbert space dimension and alpha < 1/2 is proportional to the Helmholtz free energy density of the system. We also derive an algorithm to evaluate the partition function of a quantum system in a time proportional to the system's thermalization time and inversely proportional to the targeted accuracy squared.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Tradeoffs for reliable quantum information storage in 2D systems

We ask whether there are fundamental limits on storing quantum information reliably in a bounded volume of space. To investigate this question, we study quantum error correcting codes specified by geometrically local commuting constraints on a 2D lattice of finite-dimensional quantum particles. For these 2D systems, we derive a tradeoff between the number of encoded qubits k, the distance of the code d, and the number of particles n. It is shown that kd^2=O(n) where the coefficient in O(n) depends only on the locality of the constraints and dimension of the Hilbert spaces describing individual particles. We show that the analogous tradeoff for the classical information storage is k\sqrt{d} =O(n).

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Preparing ground states of quantum many-body systems on a quantum computer

Preparing the ground state of a system of interacting classical particles is an NP-hard problem. Thus, there is in general no better algorithm to solve this problem than exhaustively going through all N configurations of the system to determine the one with lowest energy, requiring a running time proportional to N. A quantum computer, if it could be built, could solve this problem in time sqrt(N). Here, we present a powerful extension of this result to the case of interacting quantum particles, demonstrating that a quantum computer can prepare the ground state of a quantum system as efficiently as it does for classical systems.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Algebraic and information-theoretic conditions for operator quantum error-correction

Operator quantum error-correction is a technique for robustly storing quantum information in the presence of noise. It generalizes the standard theory of quantum error-correction, and provides a unified framework for topics such as quantum error-correction, decoherence-free subspaces, and noiseless subsystems. This paper develops (a) easily applied algebraic and information-theoretic conditions which characterize when operator quantum error-correction is feasible; (b) a representation theorem for a class of noise processes which can be corrected using operator quantum error-correction; and (c) generalizations of the coherent information and quantum data processing inequality to the setting of operator quantum error-correction.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Comment on "Some non-conventional ideas about algorithmic complexity"

We comment on a recent paper by D'Abramo [Chaos, Solitons & Fractals, 25 (2005) 29], focusing on the author's statement that an algorithm can produce a list of strings containing at least one string whose algorithmic complexity is greater than that of the entire list. We show that this statement, although perplexing, is not as paradoxical as it seems when the definition of algorithmic complexity is applied correctly.

0 citations0 reviewsNo code linkedOpen access