Gap Amplification for Local Hamiltonians with Combinatorial Soundness

AI summary

Overview

Research area: Quantum complexity theory, specifically the quantum PCP conjecture, local Hamiltonian gap amplification, quantum multiparty computation, high-dimensional expanders, and quantum coding theory.

Technical level: Advanced. The paper assumes familiarity with the classical PCP theorem, QMA, local Hamiltonians, quantum error-correcting codes, secret sharing, and multiparty computation.

Scope: The paper proposes a template for locality-preserving gap amplification of local Hamiltonians and proves that it amplifies a restricted notion called combinatorial soundness.

What This Paper Is About

The quantum PCP conjecture asks whether the ground-energy problem for local Hamiltonians remains hard to approximate even when the promise gap is a constant. Classical proofs of the PCP theorem rely on locality-preserving gap amplification, which increases the promise gap without increasing constraint locality, but the standard quantum approaches fail because quantum information cannot be cloned and entangled ground states have local views that look nearly maximally mixed.

The paper introduces a different route: instead of redundantly repeating the quantum witness, the construction repeats only classical “violation information,” computed and distributed fault-tolerantly using quantum secret sharing and multiparty computation on a high-dimensional expander. The authors prove that this procedure amplifies the combinatorial gap of local Hamiltonians, a weaker but technically tractable form of soundness.

Key Contributions

1. A viable template for quantum locality-preserving gap amplification. The authors present what they describe as the first known viable template for a quantum procedure that amplifies the promise gap without increasing the locality of the Hamiltonian, instead increasing the local qudit dimension.

2. A polynomial-time reduction with explicit parameters. Theorem 1.2 maps an (O(1))-local, (O(1))-degree Hamiltonian on (n) qubits to a (2)-local Hamiltonian on (O(n)) qudits with completeness ground energy at most (2^{-\operatorname{polylog}(n)}) and combinatorial energy (\varepsilon = \min{\varepsilon_{\mathrm{in}} \cdot \operatorname{polylog}(n), \varepsilon_{\max}(n)}), where (\varepsilon_{\max}(n) = 1/\operatorname{polylogloglog} n), or (\Theta(1)) assuming asymptotically good quantum locally testable codes.

3. Replacing witness repetition with secret sharing and multiparty computation. The key conceptual move is to distribute only the classical information about which constraints are violated, using secure quantum multiparty computation based on secret sharing rather than repetition of the quantum witness.

4. New technical tools of independent interest. The paper develops fault-tolerant classical readout in the presence of ABN-style faults using random noise and “friendly postselection,” proves a detectability lemma robust against adversarial postselection, and gives a zero-error quantum multiparty computation template using recent coding-theoretic advances, solving an open problem stated in [19, Section 6].

Main Findings

• Combinatorial soundness is amplified. If the input Hamiltonian has normalized ground energy (\varepsilon_{\mathrm{in}}), the output Hamiltonian has combinatorial energy at least (\min{\varepsilon_{\mathrm{in}} \cdot \operatorname{polylog}(n), \varepsilon_{\max}(n)}), meaning every state violates at least that fraction of randomly sampled terms.

• Completeness holds with small ground energy. If the input Hamiltonian has ground energy (0), the output Hamiltonian has ground energy at most (2^{-\operatorname{polylog}(n)}).

• Degree and alphabet blowup depend on the gap regime. In the low-gap regime, where the amplified promise gap is (O(1/\log n)), the output has degree and log-alphabet size (\operatorname{polylog}(n)). In the high-gap regime, where the amplified promise gap is (\Omega(1/\log n)), the output has degree and log-alphabet size (2^{\operatorname{polyloglog}(n)}).

• Good quantum locally testable codes improve the soundness ceiling. Assuming asymptotically good quantum locally testable codes, the maximum soundness (\varepsilon_{\max}(n)) can be taken as (\Theta(1)). The authors believe the current dependence is an artifact of the proof strategy.

• The distributed protocol detects violations widely. In the NO case, when the input Hamiltonian has ground energy at least (1/\operatorname{polylog} n) and a (0.001) fraction of communication edges are faulty, every input state causes an (\Omega(1)) fraction of vertices to output NO with high probability.

• High-dimensional expander sampling drives the amplification. A clique is called “good” if it has less than (10%) corrupted internal edges. Even with a constant fraction of corrupted edges, only a (1/\operatorname{polylog} n) fraction of cliques contain more than (0.1) fraction of corrupted edges, and the vertex-clique sampling property ensures that an (\Omega(1)) fraction of players see at least one violation.

• Postselection is the central technical obstacle. The ABN circuit-to-Hamiltonian construction allows low-energy witnesses that are coherent sums over Pauli faults, which can effectively implement non-unitary operations such as postselection. This forces the multiparty computation and verifiable secret sharing to be zero-error, since cheaters could otherwise postselect on a rare failure event.

• A classical analogue exists. The work of [11] shows a classical analogue of Theorem 1.2 and constructs classical PCPs of size (n^{\exp(\log^*(n))}) by combining this gap amplification with PCPs of proximity from [5]. The authors argue that Theorem 1.2 is already of comparable strength to what suffices for the classical PCP theorem, unlike previous quantum gap amplification procedures.

Methodology in Plain English

The construction starts with an input Hamiltonian whose terms are measured by a shallow sequential measurement circuit: depth (T = O(1)), with (N = n/2) gates per timestep, each gate measuring one term and writing out a classical bit. This circuit is distributed across a high-dimensional expander graph, whose vertices are players and whose (d)-cliques are groups of players responsible for individual gates.

Each qubit of the input witness is encoded into a ([d,1,\Delta]) quantum error-correcting code and split into (d) shares, one for each player in the relevant clique. The players then jointly execute each gate using a quantum multiparty computation protocol. At the end of each gate, the quantum output wires remain encoded, while the measurement outcome is copied as a classical bit to every player in the clique. Fault-tolerant routing moves the encoded wires between timesteps; the wiring is decomposed into two perfect matchings using Hall’s theorem and routed with a fault-tolerant routing procedure.

At the end of the protocol, each player outputs YES only if every measurement outcome it learned indicates a satisfied term. In an honest execution, every player outputs YES when the input state has zero energy. When the input has energy at least (1/\operatorname{polylog} n), the expander sampling properties ensure that a constant fraction of players see a violation, even if a (0.001) fraction of communication edges are corrupted.

The distributed protocol is then compiled into a local Hamiltonian using the Anshu–Breuckmann–Nguyen circuit-to-Hamiltonian construction, which is based on gate teleportation and is more robust than the Feynman–Kitaev clock Hamiltonian. The ABN construction guarantees that a state satisfying all but an (\epsilon_{\mathrm{ABN}}) fraction of terms encodes an adversarially faulty execution in which faults are confined to a set (S) of size (O(\epsilon_{\mathrm{ABN}})) of communication edges. The remaining challenge is that these faults appear in a coherent sum, giving the prover postselection power; the paper’s technical tools are designed to make the protocol sound even against such postselection attacks.

Why This Matters

Impact on research. The quantum PCP conjecture has resisted progress partly because no quantum analogue of locality-preserving gap amplification was known; all previous quantum gap amplification procedures were locality-increasing. This paper supplies a candidate template and proves a meaningful restricted soundness guarantee, giving a concrete route toward importing a central ingredient of classical PCP proofs into the quantum setting. The auxiliary tools—postselection-robust detectability, friendly postselection, and zero-error quantum multiparty computation—are likely to be useful beyond this application.

Potential real-world applications. The paper does not report deployed applications; the following are longer-term areas where the underlying techniques could matter:

• Quantum verification and testing: Improved local Hamiltonian gap amplification is relevant to verifying quantum states and certifying ground-state properties of physical systems.
• Secure distributed quantum computation: The zero-error quantum multiparty computation and verifiable secret sharing tools apply to settings where mutually distrustful parties jointly compute on shared quantum data.
• Fault-tolerant quantum computing: The fault-tolerant routing and readout techniques, including friendly postselection, are relevant to compiling and validating fault-tolerant circuits.
• Quantum error correction and code design: The reliance on quantum locally testable codes and secret-sharing codes connects the result to practical code constructions.

Industry relevance. Quantum computing companies working on verification, error correction, and distributed or cloud-based quantum computation could benefit indirectly from the coding and multiparty computation techniques. The cryptographic tools for zero-error quantum secret sharing and multiparty computation are also relevant to quantum-safe security research. The result itself is foundational and not an immediate engineering recipe.

Future Directions

• Remove the good-qLTC assumption. The authors conjecture that the dependence of (\varepsilon_{\max}(n)) on asymptotically good quantum locally testable codes is an artifact of the proof strategy and can be eliminated to obtain (\varepsilon_{\max}(n) = \Theta(1)) unconditionally.

• Extend beyond combinatorial soundness. The paper proves only that every state violates a large fraction of terms, not the full soundness statement that no low-energy state exists. Generalizing the analysis to ordinary soundness is the natural next milestone.

• Quantize alphabet reduction and proof composition. The classical PCP route interleaves gap amplification with alphabet reduction or PCPs of proximity; neither is currently known to quantize. The paper explicitly leaves open how to combine its amplification with a quantum alphabet-reduction step.

• Improve the degree and alphabet blowups. The high-gap regime incurs degree and log-alphabet size (2^{\operatorname{polyloglog}(n)}). Reducing this overhead, and extending the construction to other gap regimes and input Hamiltonian families, are natural follow-up questions.

Target Audience

Quantum complexity theorists and researchers working on the quantum PCP conjecture will find the main conceptual and technical contributions most relevant. The paper is also suited to researchers in quantum cryptography and coding theory interested in zero-error multiparty computation, verifiable secret sharing, and quantum locally testable codes. Graduate students with a background in quantum information, PCPs, and local Hamiltonians will benefit, though the material is advanced and assumes familiarity with the classical PCP literature and quantum error correction.

Authors’ 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.