# 3-local Hamiltonian is QMA-complete

@article{Kempe20033localHI, title={3-local Hamiltonian is QMA-complete}, author={Julia Kempe and Oded Regev}, journal={Quantum Inf. Comput.}, year={2003}, volume={3}, pages={258-264} }

It has been shown by Kitaev that the 5-local Hamiltonian problem is QMA-complete. Here we reduce the locality of the problem by showing that 3-local Hamiltonian is already QMA-complete.

#### Topics from this paper

#### 87 Citations

The local Hamiltonian problem on a line with eight states is QMA-complete

- Computer Science, Mathematics
- Quantum Inf. Comput.
- 2013

This work shows that the 1D problem on a chain of qubits has heuristics which work well, while the 13-state qudit case has been shown to be QMA-complete. Expand

2D Local Hamiltonian with Area Laws Is QMA-Complete

- Mathematics, Computer Science
- 2020 IEEE International Symposium on Information Theory (ISIT)
- 2020

The 2D local Hamiltonian problem with the constraint that the ground state obeys area laws is QMA-complete and similar results are proved in 2D translation- invariant systems and for the 3D Heisenberg and Hubbard models with local magnetic fields. Expand

Two-dimensional local Hamiltonian problem with area laws is QMA-complete

- Physics, Computer Science
- 2014

It is shown that the two-dimensional (2D) local Hamiltonian problem with the constraint that the ground state obeys area laws is QMA-complete, and not all ground states of 2D local Hamiltonians with area laws have efficient classical representations that support efficient computation of local expectation values. Expand

2-Local Hamiltonian with Low Complexity is QCMA

- Mathematics, Computer Science
- ArXiv
- 2019

We prove that 2-Local Hamiltonian (2-LH) with Low Complexity problem is QCMA-complete by combining the results from the QMA-completeness[4] of 2-LH and QCMA-completeness of 3-LH with Low… Expand

The Complexity of the Local Hamiltonian Problem

- Computer Science, Mathematics
- SIAM J. Comput.
- 2006

This paper settles the question and shows that the 2-LOCAL HAMILTONIAN problem is QMA-complete, and demonstrates that adiabatic computation with two-local interactions on qubits is equivalent to standard quantum computation. Expand

The Complexity of the Local Hamiltonian Problem

- Mathematics, Computer Science
- FSTTCS
- 2004

The 2-Local Hamiltonian problem is shown to be QMA-complete, and adiabatic computation with two-local interactions on qubits is equivalent to standard quantum computation. Expand

Quantum-Merlin-Arthur-complete problems for stoquastic Hamiltonians and Markov matrices

- Physics, Mathematics
- 2010

We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is Quantum-Merlin-Arthur-complete (QMA-complete). We also show that finding the highest energy of a stoquastic… Expand

Hamiltonian complexity.

- Physics, Medicine
- Reports on progress in physics. Physical Society
- 2012

The foundational results, guiding problems, and future directions of this emergent field known as Hamiltonian complexity are reviewed. Expand

The Complexity of the Separable Hamiltonian Problem

- Mathematics, Computer Science
- 2012 IEEE 27th Conference on Computational Complexity
- 2012

This paper defines two variants of the canonical Local Hamiltonian problem where, in addition, the witness is promised to be separable, and shows that the Separable Sparse Hamiltonian Problem is the first non-trivial problem shown to be QMA(2)-Complete. Expand

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

- Physics, Computer Science
- Quantum Inf. Comput.
- 2008

It is obtained that quantum adiabatic computation using 2-local interactions restricted to a 2-D square lattice is equivalent to the circuitmodel of quantum computation. Expand

#### References

SHOWING 1-6 OF 6 REFERENCES

The 2-local Hamiltonian problem encompasses NP

- Mathematics, Physics
- 2003

We show that the NP-complete problems max cut and independent set can be formulated as the 2-local Hamiltonian problem as defined by Kitaev. The 5-local Hamiltonian problem was the first problem to… Expand

Quantum NP - A Survey

- Physics, Mathematics
- 2002

We describe Kitaev's result from 1999, in which he defines the complexity class QMA, the quantum analog of the class NP, and shows that a natural extension of 3-SAT, namely local Hamiltonians, is QMA… Expand

Classical and quantum computation, volume

- Graduate Studies in Mathematics. AMS,
- 2002

Kitaev

- A. H. Shen, and M. N. Vyalyi. Classical and quantum computation, volume 47 of Graduate Studies in Mathematics. AMS
- 2002

Classical and quantum computation, volume 47 of Graduate Studies in Mathematics

- Classical and quantum computation, volume 47 of Graduate Studies in Mathematics
- 2002

Universality of adiabatic quantum computation with two-body interactions

- Universality of adiabatic quantum computation with two-body interactions