Quantum Complexity: Open Problems and Proof Targets

Quantum complexity research asks which computational tasks quantum resources can solve or verify efficiently and which assumptions obstruct them. The useful starting point is a precise promise problem or restricted model. Famous conjectures motivate a program, but a graduate project should target a lemma whose hypotheses, failure cases and relation to the conjecture can be checked.

Required background. Quantum complexity classes defines BQP, QMA and verifier models; query complexity separates oracle results from ordinary circuit claims.

Local Hamiltonians connect proofs to physics

For $H=\sum_{j=1}^{m}h_j$ with bounded local terms, the local-Hamiltonian promise problem distinguishes $E_0\leq a$ from $E_0\geq b$. The allowed gap $b-a$, locality, geometry, local dimension and interaction norm determine the problem. An inverse-polynomial gap and a constant fraction of $m$ are substantially different promises.

The quantum PCP program asks about hardness at constant relative energy precision in an appropriate local-Hamiltonian formulation. No-low-energy-trivial-state (NLTS) results instead constrain the circuit complexity of preparing low-energy states. A preparation-complexity theorem is not automatically a computational-hardness reduction.

Selected established results and unresolved directions

Established: Anshu, Breuckmann and Nirkhe proved an NLTS result using good quantum codes. Conjectural in the selected literature: the corresponding stronger quantum-PCP goals. The 2024 Natarajan–Nirkhe note identifies an error in an earlier claimed games-version construction; distinguish games and Hamiltonian versions and check corrections before using a claimed implication. NLTS paper, status note.

This page does not infer the status of every October 2026 conjecture from an older survey. The defensible entry directions are robust questions about reductions, parameter preservation and restricted models; confirm the exact subproblem’s current status with its authors’ later papers before claiming novelty.

Competing approaches and bottlenecks

Coding theory can supply highly entangled low-energy structures. Gap amplification seeks to preserve locality while increasing relative hardness. Interactive-proof methods explore verification with constrained communication. Tensor-network or commuting restrictions can reveal tractable regimes. The challenge is often retaining all required parameters simultaneously, not finding an isolated example with one desired property.

Graduate project: audit a parameter-preserving reduction

Choose a short reduction or proof lemma from the survey and reconstruct a table of input size, locality, interaction strength, promise gap and completeness/soundness. Work through one finite toy instance independently. A laptop symbolic calculation can check examples, but the deliverable must include a written argument valid for the declared family.

The baseline is the original statement with all hypotheses intact. Failure tests remove commutativity, bounded degree or a gap assumption one at a time and locate the proof step that fails. A numerical counterexample disproves a universal claim; absence of one does not prove it. Research begins with a new restricted theorem, a counterexample to an overgeneralization or a rigorously improved parameter tradeoff.

Entry points and update triggers

Read the Aharonov–Arad–Vidick survey for the logical map, then the two later papers for distinct advances and corrections. Sources checked on 11 October 2026; selected evidence horizon is 2013–2024. A corrected reduction or new theorem with the exact required parameters is an update trigger; a similarly titled result is insufficient.

References

• D. Aharonov, I. Arad and T. Vidick, “The Quantum PCP Conjecture,” arXiv:1309.7495 (2013). Survey.
• A. Anshu, N. P. Breuckmann and C. Nirkhe, “NLTS Hamiltonians from good quantum codes,” STOC 2023, 1090–1096 (2023). Preprint.
• A. Natarajan and C. Nirkhe, “The status of the quantum PCP conjecture (games version),” arXiv:2403.13084 (2024). Status note.