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

Quantum Information and Computation

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

Roberto I. Oliveira, Barbara M. Terhal

Published Nov 1, 2008• 89 citations
Publisher

Abstract

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.

DOI
10.26421/qic8.10-2

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 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

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 Complexity of Quantum Systems on a One-dimensional Chain

Sandy Irani

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.

arXiv:0705.4067•May 28, 2007•12 citations

The complexity of antiferromagnetic interactions and 2D lattices

Stephen Piddock, Ashley Montanaro

Estimation of the minimum eigenvalue of a quantum Hamiltonian can be formalised as the Local Hamiltonian problem. We study the natural special case of the Local Hamiltonian problem where the same 2-local interaction, with differing weights, is applied across each pair of qubits. First we consider antiferromagnetic/ferromagnetic interactions, where the weights of the terms in the Hamiltonian are restricted to all be of the same sign. We show that for symmetric 2-local interactions with no 1-local part, the problem is either QMA-complete or in StoqMA. In particular the antiferromagnetic Heisenberg and antiferromagnetic XY interactions are shown to be QMA-complete. We also prove StoqMA-completeness of the antiferromagnetic transverse field Ising model. Second, we study the Local Hamiltonian problem under the restriction that the interaction terms can only be chosen to lie on a particular graph. We prove that nearly all of the QMA-complete 2-local interactions remain QMA-complete when restricted to a 2D square lattice. Finally we consider both restrictions at the same time and discover that, with the exception of the antiferromagnetic Heisenberg interaction, all of the interactions which are QMA-complete with positive coefficients remain QMA-complete when restricted to a 2D triangular lattice.

arXiv:1506.04014•Quantum Information and Computation•May 1, 2017•28 citations

Realizable Hamiltonians for universal adiabatic quantum computers

Jacob Biamonte, Peter J. Love

It has been established that local lattice spin Hamiltonians can be used for universal adiabatic quantum computation. However, the two-local model Hamiltonians used in these proofs are general and hence do not limit the types of interactions required between spins. To address this concern, the present paper provides two simple model Hamiltonians that are of practical interest to experimentalists working toward the realization of a universal adiabatic quantum computer. The model Hamiltonians presented are the simplest known quantum-Merlin-Arthur-complete (QMA-complete) two-local Hamiltonians. The two-local Ising model with one-local transverse field which has been realized using an array of technologies, is perhaps the simplest quantum spin model but is unlikely to be universal for adiabatic quantum computation. We demonstrate that this model can be rendered universal and QMA-complete by adding a tunable two-local transverse ${\ensuremath{\sigma}}^{x}{\ensuremath{\sigma}}^{x}$ coupling. We also show the universality and QMA-completeness of spin models with only one-local ${\ensuremath{\sigma}}^{z}$ and ${\ensuremath{\sigma}}^{x}$ fields and two-local ${\ensuremath{\sigma}}^{z}{\ensuremath{\sigma}}^{x}$ interactions.

arXiv:0704.1287•Physical Review A•Jul 28, 2008•173 citations

The Complexity of Local Stoquastic Hamiltonians on 2D Lattices

Gabriel Waite, Michael J. Bremner

We show the 2-Local Stoquastic Hamiltonian problem on a 2D square qubit lattice is StoqMA-complete. We achieve this by extending the spatially sparse circuit construction of Oliveira and Terhal, as well as the perturbative gadgets of Bravyi, DiVincenzo, Oliveira, and Terhal. Our main contributions demonstrate StoqMA circuits can be made spatially sparse and that geometrical, stoquastic-preserving, perturbative gadgets can be constructed, without an increase to particle dimension.

arXiv:2502.14244•Quantum•May 6, 2026•1 citation
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.
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 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.
Estimation of the minimum eigenvalue of a quantum Hamiltonian can be formalised as the Local Hamiltonian problem. We study the natural special case of the Local Hamiltonian problem where the same 2-local interaction, with differing weights, is applied across each pair of qubits. First we consider antiferromagnetic/ferromagnetic interactions, where the weights of the terms in the Hamiltonian are restricted to all be of the same sign. We show that for symmetric 2-local interactions with no 1-local part, the problem is either QMA-complete or in StoqMA. In particular the antiferromagnetic Heisenberg and antiferromagnetic XY interactions are shown to be QMA-complete. We also prove StoqMA-completeness of the antiferromagnetic transverse field Ising model. Second, we study the Local Hamiltonian problem under the restriction that the interaction terms can only be chosen to lie on a particular graph. We prove that nearly all of the QMA-complete 2-local interactions remain QMA-complete when restricted to a 2D square lattice. Finally we consider both restrictions at the same time and discover that, with the exception of the antiferromagnetic Heisenberg interaction, all of the interactions which are QMA-complete with positive coefficients remain QMA-complete when restricted to a 2D triangular lattice.
It has been established that local lattice spin Hamiltonians can be used for universal adiabatic quantum computation. However, the two-local model Hamiltonians used in these proofs are general and hence do not limit the types of interactions required between spins. To address this concern, the present paper provides two simple model Hamiltonians that are of practical interest to experimentalists working toward the realization of a universal adiabatic quantum computer. The model Hamiltonians presented are the simplest known quantum-Merlin-Arthur-complete (QMA-complete) two-local Hamiltonians. The two-local Ising model with one-local transverse field which has been realized using an array of technologies, is perhaps the simplest quantum spin model but is unlikely to be universal for adiabatic quantum computation. We demonstrate that this model can be rendered universal and QMA-complete by adding a tunable two-local transverse ${\ensuremath{\sigma}}^{x}{\ensuremath{\sigma}}^{x}$ coupling. We also show the universality and QMA-completeness of spin models with only one-local ${\ensuremath{\sigma}}^{z}$ and ${\ensuremath{\sigma}}^{x}$ fields and two-local ${\ensuremath{\sigma}}^{z}{\ensuremath{\sigma}}^{x}$ interactions.