arXiv:2610.04952
Gap Amplification for Local Hamiltonians with Combinatorial Soundness
Mitali Bafna, Quynh T. Nguyen, Tina Zhang
Abstract
The quantum PCP conjecture is one of the major open problems in quantum complexity theory. It has resisted attack in part because many primitives used in the proof of the classical PCP theorem, such as locality-preserving gap amplification and alphabet reduction, have no obvious quantum analogues due to quantum no-cloning. Locality-preserving gap amplification is a procedure that takes as input a local Hamiltonian problem instance and produces a new instance with a larger promise gap, without increasing the locality of the Hamiltonian, and instead moderately increasing its local qudit dimension. Obtaining this kind of control over the locality during gap amplification is critical to the success of many known strategies for proving the classical PCP theorem. In this work, we put forth the first known viable template for quantum locality-preserving gap amplification, and we prove that our procedure amplifies the combinatorial gap of local Hamiltonians. Our work introduces a new framework for reasoning about quantum gap amplification in terms of fault-tolerant computation, and illuminates a route toward importing one of the central ingredients in classical PCPs into the quantum setting. In particular, we build upon ideas from the recent classical PCP of Bafna--Minzer--Vyas based on high-dimensional expanders, and the circuit-to-Hamiltonian construction of Anshu--Breuckmann--Nguyen, in addition to several recent advances in quantum coding theory.
AI Summary
The paper studies locality-preserving gap amplification for local Hamiltonians, a primitive sought in approaches to quantum PCP. It replaces redundant copying of the quantum witness with secret sharing and distributed computation: players jointly measure constraints, then distribute only classical violation information. For a constant-locality, constant-degree projective Hamiltonian on $n$ qubits, the reduction produces a $2$-local Hamiltonian on $O(n)$ qudits. Zero input ground energy gives output ground energy at most $2^{-\operatorname{polylog}(n)}$. Input normalized ground energy $\epsilon_{\mathrm{in}}$ gives combinatorial energy $\min\{\epsilon_{\mathrm{in}}\operatorname{polylog}(n),1/\operatorname{polylogloglog}(n)\}$. Here combinatorial energy counts the weighted fraction of terms having nonzero expectation, rather than their total expectation. Output degree and log qudit dimension are $\operatorname{polylog}(n)$ below amplified gap $O(1/\log n)$, and $2^{\operatorname{polyloglog}(n)}$ in the higher-gap regime. Suitable asymptotically good quantum locally testable codes would raise the amplification ceiling to a constant. Commuting inputs retain exact zero-energy completeness. The construction combines high-dimensional-expander routing, zero-error quantum multiparty computation built from locally testable codes and gate teleportation, and an adapted ABN circuit-to-Hamiltonian construction. Its coherent fault model permits adversarial postselection. The analysis addresses this using zero-error verification, deliberately noisy classical readout, “friendly” postselection, and a postselection-robust detectability lemma. The result does not establish amplification of ordinary ground-energy soundness. Extending the analysis requires handling distributed small errors and controlling friendly postselection beyond exact constraint satisfaction. Quantum alphabet reduction and proof composition also remain unresolved, so the construction does not yield quantum PCP.
We used ChatGPT 5.4 and Claude Opus 4.6 to assist with elementary calculations and choosing parameters in proofs of lemmas in Sections 4, 8 and Appendix A.
Error found: The noncommuting reduction assumes a fixed set of constant-description projectors, a scope restriction omitted from the abstract and informal main theorem. The ground-state proof does not justify its postselection estimate with the stated parameter scaling, although choosing smaller injectivity parameters repairs that estimate without changing the advertised locality and alphabet bounds. The final proof prints injectivity parameters with a positive exponent, making them exceed one instead of being exponentially small.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- Accepted to FOCS 2026