The Power of Quantum Systems on a Line
- 1 October 2007
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 373-383
- https://doi.org/10.1109/focs.2007.46
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). 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 analogous classical problem, one dimensional MAX-2-SAT with nearest neighbor constraints, which is in P.The proof of the QMA-completeness result requires an additional idea beyond the usual techniques in the area: Some illegal configurations cannot be ruled out by local checks, and are instead ruled out because they would, in the future, evolve into a state which can be seen locally to be illegal. Assuming BQP ne QMA, our construction gives a one-dimensional system which takes an exponential time to relax to its ground state at any temperature. This makes it a candidate for a one-dimensional spin glass.Keywords
Other Versions
This publication has 16 references indexed in Scilit:
- Ground state of a class of noncritical one-dimensional quantum spin systems can be approximated efficientlyPhysical Review A, 2007
- Error-correcting codes for adiabatic quantum computationPhysical Review A, 2006
- Efficient Approximation of the Dynamics of One-Dimensional Quantum Spin SystemsPhysical Review Letters, 2006
- Universally Programmable Quantum Cellular AutomatonPhysical Review Letters, 2006
- The Complexity of the Local Hamiltonian ProblemSIAM Journal on Computing, 2006
- The density-matrix renormalization groupReviews of Modern Physics, 2005
- Adiabatic Quantum Computation is Equivalent to Standard Quantum ComputationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- On one-dimensional quantum cellular automataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982