The power of quantum systems on a line

Abstract

We study the computational strength of quantum particles (each of finite dimensionality) arranged on a line. First, we prove that it is possible to perform universal adiabatic quantum computation using a one-dimensional quantum system (with 9 states per particle). This might have practical implications for experimentalists interested in constructing an adiabatic quantum computer. Building on the same construction, but with some additional technical effort and 12 states per particle, we show that the problem of approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete; QMA is a quantum analogue of NP. This is in striking contrast to the fact that the analogous classical problem, namely, one-dimensional MAX-2-SAT with nearest neighbor constraints, is in P. The proof of the QMA-completeness result requires an additional idea beyond the usual techniques in the area: Not all illegal configurations can be ruled out by local checks, so instead we rule out such illegal configurations because they would, in the future, evolve into a state which can be seen locally to be illegal. Our construction implies (assuming the quantum Church-Turing thesis and that quantum computers cannot efficiently solve QMA-complete problems) that there are one-dimensional systems which take an exponential time to relax to their ground states at any temperature, making them candidates for being one-dimensional spin glasses.

21 pages. v2 has numerous corrections and clarifications, and most importantly a new author, merged from arXiv:0705.4067. v3 is the published version, with additional clarifications, publisher's version available at http://www.springerlink.com

References in corpus (4)

• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• The Computational Power of Symmetric Hamiltonians
• Local Hamiltonians in Quantum Computation
• The Complexity of Quantum Systems on a One-dimensional Chain

Cited by in corpus (14)

• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
• Quantum computation, quantum state engineering, and quantum phase transitions driven by dissipation
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• The Complexity of the Consistency and N-representability Problems for Quantum States
• Local Hamiltonians in Quantum Computation
• Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
• The Complexity of Quantum Systems on a One-dimensional Chain
• Non-Identity Check Remains QMA-Complete for Short Circuits
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• The Detectability Lemma and Quantum Gap Amplification
• A PromiseBQP-complete String Rewriting Problem
• Two remarks on the local Hamiltonian problem
• Entanglement and ground states of gapped Hamiltonians