Quantum PCP and Hamiltonian complexity
64Finding the lowest energy of a system of many interacting quantum parts is, in the worst case, hard even for a quantum computer. The quantum PCP question asks whether even a rough estimate stays hard, and related questions ask how complex low-energy states must be.
Review
D. Aharonov, I. Arad and T. Vidick, The Quantum PCP Conjecture, SIGACT News (arXiv), 2013. https://arxiv.org/abs/1309.7495 reference checked
See also
Proof
- Fingerprint
- 14e3082cf422…
- Public log
- Entry 335, in checkpoint 2,123
- In the log by
- Block 969,698, 2026-10-03
This text was in the PubPhys log by that date. The date says nothing about when the problem was first posed.