results for au:Poulin_D in:quant-ph

- Jan 09 2018 quant-ph arXiv:1801.01879v1A quantum error correcting protocol can be substantially improved by taking into account features of the physical noise process. We present an efficient decoder for the surface code which can account for general noise features, including coherences and correlations. We demonstrate that the decoder significantly outperforms the conventional matching algorithm on a variety of noise models, including non-Pauli noise and spatially correlated noise. The algorithm is based on an approximate calculation of the logical channel using a tensor-network description of the noisy state.
- Nov 30 2017 quant-ph arXiv:1711.11025v1We present two techniques that can greatly reduce the number of gates required for ground state preparation in quantum simulations. The first technique realizes that to prepare the ground state of some Hamiltonian, it is not necessary to implement the time-evolution operator: any unitary operator which is a function of the Hamiltonian will do. We propose one such unitary operator which can be implemented exactly, circumventing any Taylor or Trotter approximation errors. The second technique is tailored to lattice models, and is targeted at reducing the use of generic single-qubit rotations, which are very expensive to produce by distillation and synthesis fault-tolerantly. In particular, the number of generic single-qubit rotations used by our method scales with the number of parameters in the Hamiltonian, which contrasts with a growth proportional to the lattice site required by other techniques.
- Nov 15 2017 quant-ph arXiv:1711.04736v1As far as we know, a useful quantum computer will require fault-tolerant gates, and existing schemes demand a prohibitively large space and time overhead. We argue that a first generation quantum computer will be very valuable to design, test, and optimize fault-tolerant protocols tailored to the noise processes of the hardware. Our argument is essentially a critical analysis of the current methods envisioned to optimize fault-tolerant schemes, which rely on hardware characterization, noise modelling, and numerical simulations. We show that, even within a very restricted set of noise models, error correction protocols depend strongly on the details of the noise model. Combined to the intrinsic difficulty of hardware characterization and of numerical simulations of fault-tolerant protocols, we arrive at the conclusion that the currently envisioned optimization cycle is of very limited scope. On the other hand, the direct characterization of a fault-tolerant scheme on a small quantum computer bypasses these difficulties, and could provide a bootstrapping path to full-scale fault-tolerant quantum computation.
- Sep 11 2017 quant-ph arXiv:1709.02789v1Recently we proposed a family of magic state distillation protocols that obtains asymptotic performance that is conjectured to be optimal. This family depends upon several codes, called "inner codes" and "outer codes." We presented some small examples of these codes as well as an analysis of codes in the asymptotic limit. Here, we analyze such protocols in an intermediate size regime, using hundreds to thousands of qubits. We use BCH inner codes, combined with various outer codes. We extend our protocols by adding error correction in some cases. We present a variety of protocols in various input error regimes; in many cases these protocols require significantly fewer input magic states to obtain a given output error than previous protocols.
- Apr 25 2017 quant-ph arXiv:1704.06662v2We consider the problem of fault-tolerant quantum computation in the presence of slow error diagnostics, either caused by measurement latencies or slow decoding algorithms. Our scheme offers a few improvements over previously existing solutions, for instance it does not require active error correction and results in a reduced error-correction overhead when error diagnostics is much slower than the gate time. In addition, we adapt our protocol to cases where the underlying error correction strategy chooses the optimal correction amongst all Clifford gates instead of the usual Pauli gates. The resulting Clifford frame protocol is of independent interest as it can increase error thresholds and could find applications in other areas of quantum computation.
- Mar 24 2017 quant-ph arXiv:1703.07847v3We present an infinite family of protocols to distill magic states for $T$-gates that has a low space overhead and uses an asymptotic number of input magic states to achieve a given target error that is conjectured to be optimal. The space overhead, defined as the ratio between the physical qubits to the number of output magic states, is asymptotically constant, while both the number of input magic states used per output state and the $T$-gate depth of the circuit scale linearly in the logarithm of the target error $\delta$ (up to $\log \log 1/\delta$). Unlike other distillation protocols, this protocol achieves this performance without concatenation and the input magic states are injected at various steps in the circuit rather than all at the start of the circuit. The protocol can be modified to distill magic states for other gates at the third level of the Clifford hierarchy, with the same asymptotic performance. The protocol relies on the construction of weakly self-dual CSS codes with many logical qubits and large distance, allowing us to implement control-SWAPs on multiple qubits. We call this code the "inner code". The control-SWAPs are then used to measure properties of the magic state and detect errors, using another code that we call the "outer code". Alternatively, we use weakly-self dual CSS codes which implement controlled Hadamards for the inner code, reducing circuit depth. We present several specific small examples of this protocol.
- 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.
- Jul 25 2016 quant-ph arXiv:1607.06460v2The surface code is a many-body quantum system, and simulating it in generic conditions is computationally hard. While the surface code is believed to have a high threshold, the numerical simulations used to establish this threshold are based on simplified noise models. We present a tensor-network algorithm for simulating error correction with the surface code under arbitrary local noise. We use this algorithm to study the threshold and the subthreshold behavior of the amplitude-damping and systematic rotation channels. We also compare these results to those obtained by making standard approximations to the noise models.
- Jul 12 2016 quant-ph arXiv:1607.02579v1We show how to construct a large class of quantum error correcting codes, known as CSS codes, from highly entangled cluster states. This becomes a primitive in a protocol that foliates a series of such cluster states into a much larger cluster state, implementing foliated quantum error correction. We exemplify this construction with several familiar quantum error correction codes, and propose a generic method for decoding foliated codes. We numerically evaluate the error-correction performance of a family of finite-rate CSS codes known as turbo codes, finding that it performs well over moderate depth foliations. Foliated codes have applications for quantum repeaters and fault-tolerant measurement-based quantum computation.
- Jul 11 2016 quant-ph arXiv:1607.02159v4While topological quantum computation is intrinsically fault-tolerant at zero temperature, it loses its topological protection at any finite temperature. We present a scheme to protect the information stored in a system supporting non-cyclic anyons against thermal and measurement errors. The correction procedure builds on the work of Gács [Gacs 1986] and Harrington [Harrington 2004] and operates as a local cellular automaton. In contrast to previously studied schemes, our scheme is valid for both abelian and non-abelian anyons and accounts for measurement errors. We analytically prove the existence of a fault-tolerant threshold for a certain class of non-Abelian anyon models, and numerically simulate the procedure for the specific example of Ising anyons. The result of our simulations are consistent with a threshold between $10^{-4}$ and $10^{-3}$.
- 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.
- Mar 09 2016 cond-mat.str-el quant-ph arXiv:1603.02275v3We 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.
- Sep 18 2015 quant-ph arXiv:1509.05032v2We 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.
- Jan 20 2015 quant-ph arXiv:1501.04112v2A 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.
- Jun 20 2014 quant-ph arXiv:1406.4920v1The simulation of molecules is a widely anticipated application of quantum computers. However, recent studies \citeWBCH13a,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 \citeWBCH13a; 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 \citeWBCH13a,HWBT14a which relied on exponentially costly classical exact simulation.
- Mar 24 2014 quant-ph arXiv:1403.5280v1In 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.
- Mar 13 2014 quant-ph arXiv:1403.2734v1Steane'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.
- 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.
- 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.
- 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.
- Oct 14 2013 quant-ph arXiv:1310.3235v1In 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.
- Apr 23 2013 quant-ph arXiv:1304.6100v1We 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.
- Feb 16 2013 quant-ph arXiv:1302.3638v1We study the quantum error correction threshold of Kitaev's toric code over the group Z_d subject to a generalized bit-flip noise. This problem requires novel decoding techniques, and for this purpose we generalize the renormalization group method we previously introduced for Z_2 topological codes.
- Dec 07 2012 cond-mat.stat-mech quant-ph arXiv:1212.1442v1The 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.
- Sep 26 2012 quant-ph arXiv:1209.5750v1We 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.
- Jul 06 2012 quant-ph cond-mat.str-el arXiv:1207.1443v2We 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.
- 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.
- Apr 18 2012 quant-ph cond-mat.mes-hall arXiv:1204.3793v1We 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.
- Apr 12 2012 quant-ph arXiv:1204.2439v1We 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.
- Apr 04 2012 quant-ph arXiv:1204.0792v1We 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.
- Apr 20 2011 quant-ph arXiv:1104.3835v4Quantum 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.
- 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.
- Feb 08 2011 quant-ph arXiv:1102.1360v1We 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.
- Jan 25 2011 quant-ph arXiv:1101.4366v1Quantum state tomography, the ability to deduce the state of a quantum system from measured data, is the gold standard for verification and benchmarking of quantum devices. It has been realized in systems with few components, but for larger systems it becomes infeasible because the number of quantum measurements and the amount of computation required to process them grows exponentially in the system size. Here we show that we can do exponentially better than direct state tomography for a wide range of quantum states, in particular those that are well approximated by a matrix product state ansatz. We present two schemes for tomography in 1-D quantum systems and touch on generalizations. One scheme requires unitary operations on a constant number of subsystems, while the other requires only local measurements together with more elaborate post-processing. Both schemes rely only on a linear number of experimental operations and classical postprocessing that is polynomial in the system size. A further strength of the methods is that the accuracy of the reconstructed states can be rigorously certified without any a priori assumptions.
- Dec 10 2010 quant-ph cond-mat.str-el arXiv:1012.2050v1We 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.
- Jun 08 2010 quant-ph arXiv:1006.1362v1Topological 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.
- Jun 08 2010 quant-ph arXiv:1006.1358v1Quantum 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.
- Mar 19 2010 quant-ph cond-mat.stat-mech arXiv:1003.3675v1The 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.
- Feb 26 2010 quant-ph arXiv:1002.4632v1In 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.
- The original motivation to build a quantum computer came from Feynman who envisaged a machine capable of simulating generic quantum mechanical systems, a task that is believed to be intractable for classical computers. Such a machine would have a wide range of applications in the simulation of many-body quantum physics, including condensed matter physics, chemistry, and high energy physics. Part of Feynman's challenge was met by Lloyd who showed how to approximately decompose the time-evolution operator of interacting quantum particles into a short sequence of elementary gates, suitable for operation on a quantum computer. However, this left open the problem of how to simulate the equilibrium and static properties of quantum systems. This requires the preparation of ground and Gibbs states on a quantum computer. For classical systems, this problem is solved by the ubiquitous Metropolis algorithm, a method that basically acquired a monopoly for the simulation of interacting particles. Here, we demonstrate how to implement a quantum version of the Metropolis algorithm on a quantum computer. This algorithm permits to sample directly from the eigenstates of the Hamiltonian and thus evades the sign problem present in classical simulations. A small scale implementation of this algorithm can already be achieved with today's technology
- 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.
- Oct 14 2009 quant-ph cond-mat.stat-mech arXiv:0910.2299v2We 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.
- Sep 29 2009 quant-ph arXiv:0909.5200v1We 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\sqrtd =O(n).
- May 15 2009 quant-ph arXiv:0905.2199v2We 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.
- Sep 17 2008 quant-ph arXiv:0809.2705v1Preparing 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.
- Jan 09 2008 quant-ph arXiv:0801.1241v2We address the problem of decoding sparse quantum error correction codes. For Pauli channels, this task can be accomplished by a version of the belief propagation algorithm used for decoding sparse classical codes. Quantum codes pose two new challenges however. Firstly, their Tanner graph unavoidably contain small loops which typically undermines the performance of belief propagation. Secondly, sparse quantum codes are by definition highly degenerate. The standard belief propagation algorithm does not exploit this feature, but rather it is impaired by it. We propose heuristic methods to improve belief propagation decoding, specifically targeted at these two problems. While our results exhibit a clear improvement due to the proposed heuristic methods, they also indicate that the main source of errors in the quantum coding scheme remains in the decoding.
- Dec 19 2007 quant-ph arXiv:0712.2888v2We present a theory of quantum serial turbo-codes, describe their iterative decoding algorithm, and study their performances numerically on a depolarization channel. Our construction offers several advantages over quantum LDPC codes. First, the Tanner graph used for decoding is free of 4-cycles that deteriorate the performances of iterative decoding. Secondly, the iterative decoder makes explicit use of the code's degeneracy. Finally, there is complete freedom in the code design in terms of length, rate, memory size, and interleaver choice. We define a quantum analogue of a state diagram that provides an efficient way to verify the properties of a quantum convolutional code, and in particular its recursiveness and the presence of catastrophic error propagation. We prove that all recursive quantum convolutional encoder have catastrophic error propagation. In our constructions, the convolutional codes have thus been chosen to be non-catastrophic and non-recursive. While the resulting families of turbo-codes have bounded minimum distance, from a pragmatic point of view the effective minimum distances of the codes that we have simulated are large enough not to degrade the iterative decoding performance up to reasonable word error rates and block sizes. With well chosen constituent convolutional codes, we observe an important reduction of the word error rate as the code length increases.
- In the context of constrained quantum mechanics, reference systems are used to construct relational observables that are invariant under the action of the symmetry group. Upon measurement of a relational observable, the reference system undergoes an unavoidable measurement "back-action" that modifies its properties. In a quantum-gravitational setting, it has been argued that such a back-action may produce effects that are described at an effective level as a form of deformed (or doubly) special relativity. We examine this possibility using a simple constrained system that has been extensively studied in the context of quantum information. While our conclusions support the idea of a symmetry deformation, they also reveal a host of other effects that may be relevant to the context of quantum gravity, and could potentially conceal the symmetry deformation.
- Oct 24 2007 quant-ph cond-mat.stat-mech arXiv:0710.4304v2Belief propagation -- a powerful heuristic method to solve inference problems involving a large number of random variables -- was recently generalized to quantum theory. Like its classical counterpart, this algorithm is exact on trees when the appropriate independence conditions are met and is expected to provide reliable approximations when operated on loopy graphs. In this paper, we benchmark the performances of loopy quantum belief propagation (QBP) in the context of finite-tempereture quantum many-body physics. Our results indicate that QBP provides reliable estimates of the high-temperature correlation function when the typical loop size in the graph is large. As such, it is suitable e.g. for the study of quantum spin glasses on Bethe lattices and the decoding of sparse quantum error correction codes.
- Aug 10 2007 quant-ph arXiv:0708.1337v1Belief Propagation algorithms acting on Graphical Models of classical probability distributions, such as Markov Networks, Factor Graphs and Bayesian Networks, are amongst the most powerful known methods for deriving probabilistic inferences amongst large numbers of random variables. This paper presents a generalization of these concepts and methods to the quantum case, based on the idea that quantum theory can be thought of as a noncommutative, operator-valued, generalization of classical probability theory. Some novel characterizations of quantum conditional independence are derived, and definitions of Quantum n-Bifactor Networks, Markov Networks, Factor Graphs and Bayesian Networks are proposed. The structure of Quantum Markov Networks is investigated and some partial characterization results are obtained, along the lines of the Hammersely-Clifford theorem. A Quantum Belief Propagation algorithm is presented and is shown to converge on 1-Bifactor Networks and Markov Networks when the underlying graph is a tree. The use of Quantum Belief Propagation as a heuristic algorithm in cases where it is not known to converge is discussed. Applications to decoding quantum error correcting codes and to the simulation of many-body quantum systems are described.
- May 31 2007 quant-ph arXiv:0705.4282v2We introduce a general operational characterization of information-preserving structures (IPS) -- encompassing noiseless subsystems, decoherence-free subspaces, pointer bases, and error-correcting codes -- by demonstrating that they are isometric to fixed points of unital quantum processes. Using this, we show that every IPS is a matrix algebra. We further establish a structure theorem for the fixed states and observables of an arbitrary process, which unifies the Schrodinger and Heisenberg pictures, places restrictions on physically allowed kinds of information, and provides an efficient algorithm for finding all noiseless and unitarily noiseless subsystems of the process.
- Dec 18 2006 quant-ph arXiv:quant-ph/0612126v2We analyze a quantum mechanical gyroscope which is modeled as a large spin and used as a reference against which to measure the angular momenta of spin-1/2 particles. These measurements induce a back-action on the reference which is the central focus of our study. We begin by deriving explicit expressions for the quantum channel representing the back-action. Then, we analyze the dynamics incurred by the reference when it is used to sequentially measure particles drawn from a fixed ensemble. We prove that the reference thermalizes with the measured particles and find that generically, the thermal state is reached in time which scales linearly with the size of the reference. This contrasts a recent conclusion of Bartlett et al. that this takes a quadratic amount of time when the particles are completely unpolarized. We now understand their result in terms of a simple physical principle based on symmetries and conservation laws. Finally, we initiate the study of the non-equilibrium dynamics of the reference. Here we find that a reference in a coherent state will essentially remain in one when measuring polarized particles, while rotating itself to ultimately align with the polarization of the particles.
- Jun 15 2006 quant-ph arXiv:quant-ph/0606126v2We consider the problem of optimally decoding a quantum error correction code -- that is to find the optimal recovery procedure given the outcomes of partial "check" measurements on the system. In general, this problem is NP-hard. However, we demonstrate that for concatenated block codes, the optimal decoding can be efficiently computed using a message passing algorithm. We compare the performance of the message passing algorithm to that of the widespread blockwise hard decoding technique. Our Monte Carlo results using the 5 qubit and Steane's code on a depolarizing channel demonstrate significant advantages of the message passing algorithms in two respects. 1) Optimal decoding increases by as much as 94% the error threshold below which the error correction procedure can be used to reliably send information over a noisy channel. 2) For noise levels below these thresholds, the probability of error after optimal decoding is suppressed at a significantly higher rate, leading to a substantial reduction of the error correction overhead.
- Aug 19 2005 quant-ph arXiv:quant-ph/0508131v4Operator quantum error correction is a recently developed theory that provides a generalized framework for active error correction and passive error avoiding schemes. In this paper, we describe these codes in the stabilizer formalism of standard quantum error correction theory. This is achieved by adding a "gauge" group to the standard stabilizer definition of a code that defines an equivalence class between encoded states. Gauge transformations leave the encoded information unchanged; their effect is absorbed by virtual gauge qubits that do not carry useful information. We illustrate the construction by identifying a gauge symmetry in Shor's 9-qubit code that allows us to remove 4 of its 8 stabilizer generators, leading to a simpler decoding procedure and a wider class of logical operations without affecting its essential properties. This opens the path to possible improvements of the error threshold of fault-tolerant quantum computing.
- Jun 13 2005 quant-ph arXiv:quant-ph/0506085v2We present experimental results on the measurement of fidelity decay under contrasting system dynamics using a nuclear magnetic resonance quantum information processor. The measurements were performed by implementing a scalable circuit in the model of deterministic quantum computation with only one quantum bit. The results show measurable differences between regular and complex behaviour and for complex dynamics are faithful to the expected theoretical decay rate. Moreover, we illustrate how the experimental method can be seen as an efficient way for either extracting coarse-grained information about the dynamics of a large system, or measuring the decoherence rate from engineered environments.
- Jun 10 2005 quant-ph arXiv:quant-ph/0506069v1Operator 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.
- Using an elementary example based on two simple harmonic oscillators, we show how a relational time may be defined that leads to an approximate Schrodinger dynamics for subsystems, with corrections leading to an intrinsic decoherence in the energy eigenstates of the subsystem.
- In the absence of an external frame of reference physical degrees of freedom must describe relations between systems. Using a simple model, we investigate how such a relational quantum theory naturally arises by promoting reference systems to the status of dynamical entities. Our goal is to demonstrate using elementary quantum theory how any quantum mechanical experiment admits a purely relational description at a fundamental level, from which the original "non-relational" theory emerges in a semi-classical limit. According to this thesis, the non-relational theory is therefore an approximation of the fundamental relational theory. We propose four simple rules that can be used to translate an "orthodox" quantum mechanical description into a relational description, independent of an external spacial reference frame or clock. The techniques used to construct these relational theories are motivated by a Bayesian approach to quantum mechanics, and rely on the noiseless subsystem method of quantum information science used to protect quantum states against undesired noise. The relational theory naturally predicts a fundamental decoherence mechanism, so an arrow of time emerges from a time-symmetric theory. Moreover, there is no need for a "collapse of the wave packet" in our model: the probability interpretation is only applied to diagonal density operators. Finally, the physical states of the relational theory can be described in terms of "spin networks" introduced by Penrose as a combinatorial description of geometry, and widely studied in the loop formulation of quantum gravity. Thus, our simple bottom-up approach (starting from the semi-classical limit to derive the fully relational quantum theory) may offer interesting insights on the low energy limit of quantum gravity.
- This paper is an expanded and more detailed version of our recent work in which the Operator Quantum Error Correction formalism was introduced. This is a new scheme for the error correction of quantum operations that incorporates the known techniques - i.e. the standard error correction model, the method of decoherence-free subspaces, and the noiseless subsystem method - as special cases, and relies on a generalized mathematical framework for noiseless subsystems that applies to arbitrary quantum operations. We also discuss a number of examples and introduce the notion of ``unitarily noiseless subsystems''.
- We present a unified approach to quantum error correction, called operator quantum error correction. This scheme relies on a generalized notion of noiseless subsystems that is not restricted to the commutant of the interaction algebra. We arrive at the unified approach, which incorporates the known techniques -- i.e. the standard error correction model, the method of decoherence-free subspaces, and the noiseless subsystem method -- as special cases, by combining active error correction with this generalized noiseless subsystem method. Moreover, we demonstrate that the quantum error correction condition from the standard model is a necessary condition for all known methods of quantum error correction.
- Aug 20 2004 quant-ph arXiv:quant-ph/0408125v3We study the role of the information deposited in the environment of an open quantum system in course of the decoherence process. Redundant spreading of information -- the fact that some observables of the system can be independently ``read-off'' from many distinct fragments of the environment -- is investigated as the key to effective objectivity, the essential ingredient of ``classical reality''. This focus on the environment as a communication channel through which observers learn about physical systems underscores importance of quantum Darwinism -- selective proliferation of information about ``the fittest states'' chosen by the dynamics of decoherence at the expense of their superpositions -- as redundancy imposes the existence of preferred observables. We demonstrate that the only observables that can leave multiple imprints in the environment are the familiar pointer observables singled out by environment-induced superselection (einselection) for their predictability. Many independent observers monitoring the environment will therefore agree on properties of the system as they can only learn about preferred observables. In this operational sense, the selective spreading of information leads to appearance of an objective ``classical reality'' from within quantum substrate.
- Mar 31 2004 quant-ph arXiv:quant-ph/0403212v2We study macroscopic observables defined as the total value of a physical quantity over a collection of quantum systems. We show that previous results obtained for infinite ensemble of identically prepared systems lead to incorrect conclusions for finite ensembles. In particular, exact measurement of a macroscopic observable significantly disturbs the state of any finite ensemble. However, we show how this disturbance can be made arbitrarily small when the measurement are of finite accuracy. We demonstrate a tradeoff between state disturbance and measurement coarseness as a function of the size of the ensemble. Using this tradeoff, we show that the histories generated by any sequence of finite accuracy macroscopic measurements always generate a consistent family in the absence of large scale entanglement, for sufficiently large ensembles. Hence, macroscopic observables behave "classically" provided that their accuracy is coarser than the quantum correlation length-scale of the system. The role of these observable is also discussed in the context of NMR quantum information processing and bulk ensemble quantum state tomography.
- Collective rotation channels are a fundamental class of channels in quantum computing and quantum information theory. The commutant of the noise operators for such a channel is a C*-algebra which is equal to the set of fixed points for the channel. Finding the precise spatial structure of the commutant algebra for a set of noise operators associated with a channel is a core problem in quantum error prevention. We draw on methods of operator algebras, quantum mechanics and combinatorics to explicitly determine the structure of the commutant for the class of collective rotation channels.
- Oct 07 2003 quant-ph arXiv:quant-ph/0310038v1We present an efficient quantum algorithm to measure the average fidelity decay of a quantum map under perturbation using a single bit of quantum information. Our algorithm scales only as the complexity of the map under investigation, so for those maps admitting an efficient gate decomposition, it provides an exponential speed up over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of quantum chaos. Our result also illustrates the role of chaos in the process of decoherence.
- We report an efficient quantum algorithm for estimating the local density of states (LDOS) on a quantum computer. The LDOS describes the redistribution of energy levels of a quantum system under the influence of a perturbation. Sometimes known as the ``strength function'' from nuclear spectroscopy experiments, the shape of the LDOS is directly related to the survivial probability of unperturbed eigenstates, and has recently been related to the fidelity decay (or ``Loschmidt echo'') under imperfect motion-reversal. For quantum systems that can be simulated efficiently on a quantum computer, the LDOS estimation algorithm enables an exponential speed-up over direct classical computation.
- Jul 31 2003 quant-ph arXiv:quant-ph/0307229v2We study the emergence of objective properties in open quantum systems. In our analysis, the environment is promoted from a passive role of reservoir selectively destroying quantum coherence, to an active role of amplifier selectively proliferating information about the system. We show that only preferred pointer states of the system can leave a redundant and therefore easily detectable imprint on the environment. Observers who--as it is almost always the case--discover the state of the system indirectly (by probing a fraction of its environment) will find out only about the corresponding pointer observable. Many observers can act in this fashion independently and without perturbing the system: they will agree about the state of the system. In this operational sense, preferred pointer states exist objectively.
- Jul 01 2003 quant-ph arXiv:quant-ph/0306199v2We present two polarization-based protocols for quantum key distribution. The protocols encode key bits in noiseless subspaces or subsystems, and so can function over a quantum channel subjected to an arbitrary degree of collective noise, as occurs, for instance, due to rotation of polarizations in an optical fiber. These protocols can be implemented using only entangled photon-pair sources, single-photon rotations, and single-photon detectors. Thus, our proposals offer practical and realistic alternatives to existing schemes for quantum key distribution over optical fibers without resorting to interferometry or two-way quantum communication, thereby circumventing, respectively, the need for high precision timing and the threat of Trojan horse attacks.
- Mar 11 2003 quant-ph arXiv:quant-ph/0303042v2We show that deterministic quantum computing with a single bit (DQC1) can determine whether the classical limit of a quantum system is chaotic or integrable using O(N) physical resources, where $N$ is the dimension of the Hilbert space of the system under study. This is a square root improvement over all known classical procedures. Our study relies strictly on the random matrix conjecture. We also present numerical results for the nonlinear kicked top.
- May 08 2002 quant-ph arXiv:quant-ph/0205033v1We introduce a measure of the compatibility between quantum states--the likelihood that two density matrices describe the same object. Our measure is motivated by two elementary requirements, which lead to a natural definition. We list some properties of this measure, and discuss its relation to the problem of combining two observers' states of knowledge.
- Aug 24 2001 quant-ph arXiv:quant-ph/0108102v2The ultimate goal of the classicality programme is to quantify the amount of quantumness of certain processes. Here, classicality is studied for a restricted type of process: quantum information processing (QIP). Under special conditions, one can force some qubits of a quantum computer into a classical state without affecting the outcome of the computation. The minimal set of conditions is described and its structure is studied. Some implications of this formalism are the increase of noise robustness, a proof of the quantumness of mixed state quantum computing and a step forward in understanding the very foundation of QIP.