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:quant-ph/0302079 · Quantum Information and Computation

3-Local Hamiltonian is QMA-complete

Julia Kempe, Oded Regev

Published May 1, 2003• 112 citations
arXivHTMLPDF

Abstract

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.
DOI
10.26421/qic3.3-7

Related papers

3-local Hamitonian is QMA-complete

KempeJulia, RegevOded

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.

Quantum Information and Computation•May 1, 2003•7 citations

THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP

Paweł Wocjan, Thomas Beth

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 be shown to be complete for the quantum complexity class QMA — the quantum analog of NP. Subsequently, it was shown that 3-locality is already sufficient for QMA-completeness. It is still not known whether the 2-local Hamiltonian problem is QMA-complete. Therefore it is interesting to determine what problems can be reduced to the 2-local Hamiltonian problem. Kitaev showed that 3-SAT can be formulated as a 3-local Hamiltonian problem. We extend his result by showing that 2-locality is sufficient in order to encompass NP.

arXiv:quant-ph/0301087•International Journal of Quantum Information•Sep 1, 2003•16 citations

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

HallgrenSean, NagajDaniel, NarayanaswamiSandeep

The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which w...

Quantum Information and Computation•Sep 1, 2013•0 citations

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

Sean Hallgren, Daniel Nagaj, S. Narayanaswami

The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. 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. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.

arXiv:1312.1469•Dec 5, 2013•13 citations

2-Local Hamiltonian with Low Complexity is QCMA

Yinghao Chen

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 Complexity[6]. The idea is straightforward. It has been known that 2-LH is QMA-complete. By putting a low complexity constraint on the input state, we make the problem QCMA. Finally, we use similar arguments as in [4] to show that all QCMA problems can be reduced to our proposed problem.

arXiv:1909.03787•Sep 6, 2019•0 citations

The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness

Itay Shalit, Mark Zhandry

The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in $\mathsf{NP}$ for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\mathsf{QMA}$-complete. CLH is complete for the complexity class $\mathsf{QIMA}$, defined through quantum verifiers whose local gates commute. Therefore, CLH is $\mathsf{QMA}$-complete if and only if $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.

quant-pharXiv:2609.38957•Oct 1, 2026•0 citations
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 be shown to be complete for the quantum complexity class QMA — the quantum analog of NP. Subsequently, it was shown that 3-locality is already sufficient for QMA-completeness. It is still not known whether the 2-local Hamiltonian problem is QMA-complete. Therefore it is interesting to determine what problems can be reduced to the 2-local Hamiltonian problem. Kitaev showed that 3-SAT can be formulated as a 3-local Hamiltonian problem. We extend his result by showing that 2-locality is sufficient in order to encompass NP.
The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in NP\mathsf{NP}NP for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is QMA\mathsf{QMA}QMA-complete. CLH is complete for the complexity class QIMA\mathsf{QIMA}QIMA, defined through quantum verifiers whose local gates commute. Therefore, CLH is QMA\mathsf{QMA}QMA-complete if and only if QIMA=QMA\mathsf{QIMA}=\mathsf{QMA}QIMA=QMA. In this work, we introduce a classical-oracle analogue QIMAO\mathsf{QIMA}^{\mathcal{O}}QIMAO and construct a classical oracle O\mathcal{O}O such that BQPO⊈QIMAO\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}BQPO⊆QIMAO. Since BQPO⊆QMAO\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}BQPO⊆QMAO for any classical oracle O\mathcal{O}O, this implies QIMAO≠QMAO\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}QIMAO=QMAO for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is BQP\mathsf{BQP}BQP-hard, and hence also against the possibility that it is QMA\mathsf{QMA}QMA-complete.