The quantum PCP conjecture for local Hamiltonians
Fix an integer $k \ge 2$ and $\varepsilon > 0$, and consider the following promise problem. The input consists of $m$ positive semidefinite operators $0 \le h_j \le I$ on $n$ qubits, each acting on at most $k$ qubits, and rational numbers $0 \le a < b \le 1$ with $b - a \ge \varepsilon$; the local matrices and the thresholds have binary descriptions of polynomial length. With $$H = \frac{1}{m} \sum_{j=1}^{m} h_j,$$ decide whether $\lambda_{\min}(H) \le a$ or $\lambda_{\min}(H) \ge b$, promised that one of the two holds. Here QMA is the class of promise problems with polynomial-time quantum verifiers, polynomially many witness qubits, completeness at least $2/3$ and soundness at most $1/3$. Kitaev proved that the local Hamiltonian problem is QMA-complete when $b - a$ is only required to be at least an inverse polynomial in $n$, and Kempe, Kitaev and Regev that $k = 2$ suffices. The NLTS conjecture of Freedman and Hastings, which the statement below implies unless QMA equals NP, was proved by Anshu, Breuckmann and Nirkhe.
Problem. Do there exist an integer $k \ge 2$ and a constant $\varepsilon > 0$ for which this promise problem is QMA-hard under quantum polynomial-time reductions, that is, every promise problem in QMA reduces to it by a uniform polynomial-time quantum computation with bounded error?
Source: Raised by Aharonov and Naveh (2002) and formulated by Aharonov, Arad, Landau and Vazirani (2009); in this form, Aharonov, Arad and Vidick (2013), Conjecture 1.3 (quantum PCP by gap amplification). Stated with explicit normalisations by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- MP — Mathematical Physics
- Secondary
- SP
- Keywords
- AIM Open Applied Problems, local Hamiltonians, probabilistically checkable proofs, QMA
References
@article{aharonov2013,
author = {Aharonov, Dorit and Arad, Itai and Vidick, Thomas},
title = {Guest column: the quantum {PCP} conjecture},
journal = {ACM SIGACT News},
volume = {44},
number = {2},
year = {2013},
pages = {47--79},
doi = {10.1145/2491533.2491549},
eprint = {1309.7495},
archivePrefix = {arXiv},
}
@misc{aharonov2002,
author = {Aharonov, Dorit and Naveh, Tomer},
title = {Quantum {NP} -- a survey},
year = {2002},
eprint = {quant-ph/0210077},
archivePrefix = {arXiv},
}
@inproceedings{aharonov2009,
author = {Aharonov, Dorit and Arad, Itai and Landau, Zeph and Vazirani, Umesh},
title = {The detectability lemma and quantum gap amplification},
booktitle = {Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009)},
publisher = {ACM},
address = {New York},
year = {2009},
pages = {417--426},
doi = {10.1145/1536414.1536472},
}
@book{kitaev2002,
author = {Kitaev, A. Yu. and Shen, A. H. and Vyalyi, M. N.},
title = {Classical and Quantum Computation},
series = {Graduate Studies in Mathematics},
volume = {47},
publisher = {American Mathematical Society},
address = {Providence, RI},
year = {2002},
doi = {10.1090/gsm/047},
}
@article{kempe2006,
author = {Kempe, Julia and Kitaev, Alexei and Regev, Oded},
title = {The complexity of the local {H}amiltonian problem},
journal = {SIAM J. Comput.},
volume = {35},
number = {5},
year = {2006},
pages = {1070--1097},
doi = {10.1137/S0097539704445226},
}
@article{freedman2014,
author = {Freedman, Michael H. and Hastings, Matthew B.},
title = {Quantum systems on non-$k$-hyperfinite complexes: a generalization of classical statistical mechanics on expander graphs},
journal = {Quantum Inf. Comput.},
volume = {14},
number = {1-2},
year = {2014},
pages = {144--180},
doi = {10.26421/QIC14.1-2-9},
}
@inproceedings{anshu2023,
author = {Anshu, Anurag and Breuckmann, Nikolas P. and Nirkhe, Chinmay},
title = {{NLTS} {H}amiltonians from good quantum codes},
booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)},
publisher = {ACM},
address = {New York},
year = {2023},
pages = {1090--1096},
doi = {10.1145/3564246.3585114},
eprint = {2206.13228},
archivePrefix = {arXiv},
}
@article{buhrman2025,
author = {Buhrman, Harry and Helsen, Jonas and Weggemans, Jordi},
title = {Quantum {PCP}s: on adaptivity, multiple provers and reductions to local {H}amiltonians},
journal = {Quantum},
volume = {9},
year = {2025},
pages = {1791},
doi = {10.22331/q-2025-07-11-1791},
eprint = {2403.04841},
archivePrefix = {arXiv},
}
@misc{aim-quantum-pcp,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The quantum PCP conjecture for local Hamiltonians}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/200-quantum-pcp.md},
note = {Entry 200 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00465, "The quantum PCP conjecture for local Hamiltonians", clopen.solutions.