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• 12 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 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, see quant-ph/0406180. In this paper we show that this important problem remains QMA-complete when the interactions of the 2-local Hamiltonian are restricted to 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 2-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.

•Nov 1, 2008•144 citations

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•40 citations

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•12 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•395 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.

Quantum Information and Computation•Nov 1, 2008•89 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, see quant-ph/0406180. 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•Apr 7, 2005•13 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.
The problem 2-LOCAL HAMILTONIAN has been shown to be complete for the quantum computational class QMA, see quant-ph/0406180. In this paper we show that this important problem remains QMA-complete when the interactions of the 2-local Hamiltonian are restricted to 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 2-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.
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.
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.
The problem 2-LOCAL HAMILTONIAN has been shown to be complete for the quantum computational class QMA, see quant-ph/0406180. 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.