Quantum Adiabatic Computation With a Constant Gap is Not Useful in One Dimension

Abstract

We show that it is possible to use a classical computer to efficiently simulate the adiabatic evolution of a quantum system in one dimension with a constant spectral gap, starting the adiabatic evolution from a known initial product state. The proof relies on a recently proven area law for such systems, implying the existence of a good matrix product representation of the ground state, combined with an appropriate algorithm to update the matrix product state as the Hamiltonian is changed. This implies that adiabatic evolution with such Hamiltonians is not useful for universal quantum computation. Therefore, adiabatic algorithms which are useful for universal quantum computation either require a spectral gap tending to zero or need to be implemented in more than one dimension (we leave open the question of the computational power of adiabatic simulation with a constant gap in more than one dimension).

4 pages, no figures

References in corpus (6)

• An Area Law for One Dimensional Quantum Systems
• Matrix product states represent ground states faithfully
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Error correcting codes for adiabatic quantum computation
• Simulating adiabatic evolution of gapped spin systems
• The computational difficulty of finding MPS ground states

Cited by in corpus (16)

• Adiabatic Quantum Computing
• Can One Trust Quantum Simulators?
• Lieb-Robinson Bound and Locality for General Markovian Quantum Dynamics
• Connecting global and local energy distributions in quantum spin models on a lattice
• Unfrustrated Qudit Chains and their Ground States
• A simple proof of the detectability lemma and spectral gap amplification
• Local tests of global entanglement and a counterexample to the generalized area law
• Quantum and Classical in Adiabatic Computation
• Exponential bound on information spreading induced by quantum many-body dynamics with long-range interactions
• Computing energy density in one dimension
• A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians
• Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
• Why the Quantitative Condition Fails to Reveal Quantum Adiabaticity
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• On fixed-gap adiabatic quantum computation
• Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics