Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0705.4067

The Complexity of Quantum Systems on a One-dimensional Chain

Sandy Irani

Published May 28, 2007• 18 citations
arXivHTMLPDF

Abstract

We prove that adiabatic computation is equivalent to standard quantum computation even when the adiabatic quantum system is restricted to be a set of particles on a one-dimensional chain. We give a construction that uses a 2-local Hamiltonian on nearest neighbors using particles that can have ten distinct states. This implies a construction of a one-dimensional chain of qubits in which the Hamiltonian is 6-local. We adapt this construction to show that the 2-local Hamiltonian for 13-state particles is QMA-complete which in turn implies that the 8-local Hamiltonian restricted to a one-dimensional chain of qubits is QMA-complete.

DOI
10.48550/arxiv.0705.4067

Related papers

The Power of Quantum Systems on a Line

Dorit Aharonov, Daniel Gottesman, Sandy Irani +1 more

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.

Annual Symposium on Foundations of Computer Science•Oct 1, 2007•51 citations

Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation

Dorit Aharonov, Wim van Dam, Julia Kempe +3 more

The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.

SIAM Review•Jan 1, 2008•414 citations

The complexity of quantum spin systems on a two-dimensional square lattice

Roberto I. Oliveira, Barbara M. Terhal

The problem 2-LOCAL HAMILTONIAN has been shown to be complete for the quantum computational class QMA. In this paper we show that this important problem remains QMA-complete when the interactions of the 2-local Hamiltonian are between qubits on a two-dimensional (2-D) square lattice. Our results are partially derived with novel perturbation gadgets that employ mediator qubits which allow us to manipulate k-local interactions. As a side result, we obtain that quantum adiabatic computation using 2-local interactions restricted to a 2-D square lattice is equivalent to the circuit model of quantum computation. Our perturbation method also shows how any stabilizer space associated with a k-local stabilizer (for constant k) can be generated as an approximate ground-space of a 2-local Hamiltonian.

arXiv:quant-ph/0504050•Quantum Information and Computation•Nov 1, 2008•286 citations

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

Dorit Aharonov, Wim van Dam, Julia Kempe +3 more

Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models provides a new vantage point from which to tackle the central issues in quantum computation, namely designing new quantum algorithms and constructing fault tolerant quantum computers. In particular, by translating the main open questions in the area of quantum algorithms to the language of spectral gaps of sparse matrices, the result makes these questions accessible to a wider scientific audience, acquainted with mathematical physics, expander theory and rapidly mixing Markov chains.

arXiv:quant-ph/0405098•May 18, 2004•165 citations

New construction for a QMA complete three-local Hamiltonian

Daniel Nagaj, Shay Mozes

We present a new way of encoding a quantum computation into a three-local Hamiltonian. Our construction is novel in that it does not include any terms that induce legal-illegal clock transitions. Therefore, the weights of the terms in the Hamiltonian do not scale with the size of the problem as in previous constructions. This improves the construction by Kempe and Regev [Quantum Inf. Comput. 3, 258–264 (2003); e-print quant-ph∕0302079] who were the first to prove that three-local Hamiltonian is complete for the complexity class QMA, the quantum analog of NP. Quantum k-SAT, a restricted version of the local Hamiltonian problem using only projector terms, was introduced by Bravyi (e-print quant-ph∕0602108) as an analog of the classical k-SAT problem. Bravyi proved that quantum 4-SAT is complete for the class QMA with one-sided error (QMA1) and that quantum 2-SAT is in P. We give an encoding of a quantum circuit into a quantum 4-SAT Hamiltonian using only three-local terms. As an intermediate step to this three-local construction, we show that quantum 3-SAT for particles with dimensions 3×2×2 (a qutrit and two qubits) is QMA1 complete. The complexity of quantum 3-SAT with qubits remains an open question.

arXiv:quant-ph/0612113•Journal of Mathematical Physics•Jul 1, 2007•63 citations

Hamiltonian quantum cellular automata in one dimension

Daniel Nagaj, Paweł Wocjan

We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of ten-dimensional qudits that makes it possible to realize universal quantum computing without any external control during the computational process. We only require the ability to prepare an initial computational basis state that encodes both the quantum circuit and its input. The computational process is then carried out by the autonomous Hamiltonian time evolution. After a time polynomially long in the size of the quantum circuit has passed, the result of the computation is obtained with high probability by measuring a few qudits in the computational basis. This result also implies that there cannot exist efficient classical simulation methods for generic translationally invariant nearest-neighbor Hamiltonians on qudit chains, unless quantum computers can be efficiently simulated by classical computers (or, put in complexity theoretic terms, unless $\mathrm{BPP}=\mathrm{BQP}$).

arXiv:0802.0886•Physical Review A•Sep 9, 2008•61 citations
We prove that adiabatic computation is equivalent to standard quantum computation even when the adiabatic quantum system is restricted to be a set of particles on a one-dimensional chain. We give a construction that uses a 2-local Hamiltonian on nearest neighbors using particles that can have ten distinct states. This implies a construction of a one-dimensional chain of qubits in which the Hamiltonian is 6-local. We adapt this construction to show that the 2-local Hamiltonian for 13-state particles is QMA-complete which in turn implies that the 8-local Hamiltonian restricted to a one-dimensional chain of qubits is QMA-complete.
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.
The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models allows one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.
The problem 2-LOCAL HAMILTONIAN has been shown to be complete for the quantum computational class QMA. In this paper we show that this important problem remains QMA-complete when the interactions of the 2-local Hamiltonian are between qubits on a two-dimensional (2-D) square lattice. Our results are partially derived with novel perturbation gadgets that employ mediator qubits which allow us to manipulate k-local interactions. As a side result, we obtain that quantum adiabatic computation using 2-local interactions restricted to a 2-D square lattice is equivalent to the circuit model of quantum computation. Our perturbation method also shows how any stabilizer space associated with a k-local stabilizer (for constant k) can be generated as an approximate ground-space of a 2-local Hamiltonian.
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models provides a new vantage point from which to tackle the central issues in quantum computation, namely designing new quantum algorithms and constructing fault tolerant quantum computers. In particular, by translating the main open questions in the area of quantum algorithms to the language of spectral gaps of sparse matrices, the result makes these questions accessible to a wider scientific audience, acquainted with mathematical physics, expander theory and rapidly mixing Markov chains.
We present a new way of encoding a quantum computation into a three-local Hamiltonian. Our construction is novel in that it does not include any terms that induce legal-illegal clock transitions. Therefore, the weights of the terms in the Hamiltonian do not scale with the size of the problem as in previous constructions. This improves the construction by Kempe and Regev [Quantum Inf. Comput. 3, 258–264 (2003); e-print quant-ph∕0302079] who were the first to prove that three-local Hamiltonian is complete for the complexity class QMA, the quantum analog of NP. Quantum k-SAT, a restricted version of the local Hamiltonian problem using only projector terms, was introduced by Bravyi (e-print quant-ph∕0602108) as an analog of the classical k-SAT problem. Bravyi proved that quantum 4-SAT is complete for the class QMA with one-sided error (QMA1) and that quantum 2-SAT is in P. We give an encoding of a quantum circuit into a quantum 4-SAT Hamiltonian using only three-local terms. As an intermediate step to this three-local construction, we show that quantum 3-SAT for particles with dimensions 3×2×2 (a qutrit and two qubits) is QMA1 complete. The complexity of quantum 3-SAT with qubits remains an open question.
We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of ten-dimensional qudits that makes it possible to realize universal quantum computing without any external control during the computational process. We only require the ability to prepare an initial computational basis state that encodes both the quantum circuit and its input. The computational process is then carried out by the autonomous Hamiltonian time evolution. After a time polynomially long in the size of the quantum circuit has passed, the result of the computation is obtained with high probability by measuring a few qudits in the computational basis. This result also implies that there cannot exist efficient classical simulation methods for generic translationally invariant nearest-neighbor Hamiltonians on qudit chains, unless quantum computers can be efficiently simulated by classical computers (or, put in complexity theoretic terms, unless BPP=BQP\mathrm{BPP}=\mathrm{BQP}BPP=BQP).