Gap Amplification for Local Hamiltonians with Combinatorial Soundness

1 Introduction

• Locality-preserving amplification is difficult to quantize because classical repetition redundantly encodes assignments, while quantum information cannot be cloned.For entangled witnesses, local views may reveal little about the global state, undermining consistency checks between repeated pieces.Source: §1 · p. 4
• The reduction maps constant-locality, constant-degree input Hamiltonians to 2-local Hamiltonians on O(n) qudits, with completeness ground energy at most 2^-polylog(n).The theorem states εmax(n) = 1/polylogloglog(n), and the authors say asymptotically good quantum locally testable codes would permit εmax(n) = Θ(1).Source: §1 · p. 5
• In the low-gap regime, degree and log-alphabet size are polylog(n); in the high-gap regime, both are 2^polyloglog(n).The regimes are divided at an amplified promise gap of order 1/log(n).Source: §1 · p. 5
• Combinatorial soundness requires every state to violate at least an ε fraction of terms, reducing analysis to states satisfying at least 1−ε of the terms exactly.The authors describe this restricted soundness notion as a technically more tractable first step.Source: §1 · p. 5
• The authors present combinatorial soundness as a meaningful milestone, while noting that good quantum locally testable codes are currently needed in the highest soundness regime.They believe this dependence is an artifact of their proof strategy; the result is described as comparable in strength to what suffices for the classical PCP theorem.Source: §1 · pp. 5–7
• The construction combines the HDX-based classical PCP of [BMVY25] with the circuit-to-Hamiltonian procedure of [ABN24], distributing violation information rather than copying the quantum witness.An HDX protocol fault-tolerantly computes whether input constraints are violated, then converts that protocol into a local Hamiltonian.Source: §1 · p. 6
• Soundness analysis must address adversarial postselection: the [ABN24] fault model permits coherent combinations of faults that can implement non-unitary operations.The authors introduce random noise and friendly postselection, a robust detectability lemma, and a zero-error quantum multiparty-computation template.Source: §1 · p. 6

2.1 Obstacles to Quantizing Gap Amplification

• Classical repetition-based amplification fails to transfer directly: quantum witness copies are unavailable, GHZ repetition is unsuitable, and local views of quantum codes cannot recover the logical state.The code obstacle follows from local indistinguishability: views smaller than the code distance look maximally mixed over the codespace.Source: §2.1 · p. 7

2.2 A Template for Gap Amplification: Multiparty Computation on an HDX

• The template replaces copying the quantum witness with secret sharing and multiparty computation, so players jointly evaluate constraints on shared data and copy only the resulting classical violation bits.Quantum secret sharing is possible despite no-cloning, and its local indistinguishability property supplies the secrecy needed for secret sharing.Source: §2.2 · pp. 8–9
• With ground energy at least 1/polylog n, the protocol makes an Ω(1) fraction of players output NO despite a constant fraction of faulty communication edges.The protocol simulates the input Hamiltonian’s sequential measurement circuit using quantum MPC on HDX cliques and fault-tolerant routing; HDX sampling limits faulty cliques and spreads violations among players.Source: §2.2 · pp. 9–11

2.3 Circuit-to-Hamiltonian and the Postselection Problem

• The ABN construction gives combinatorial soundness: a witness violating only an ϵ_ABN fraction of Hamiltonian terms corresponds to errors on a fixed set of O(ϵ_ABN) communication edges.Its known general soundness analysis controls low-energy states only when the protocol has near-constant physical depth.Source: §2.3 · p. 12
• Postselection complicates soundness because ABN witnesses can represent non-unitary postselection attacks, which the protocol’s fault tolerance must handle in addition to ordinary faults.The ABN construction is used because Feynman–Kitaev propagation is brittle: a single violated term can allow arbitrary cheating.Source: §2.3 · pp. 12–13
• A single cheater can exploit nonzero VQSS error or postselect a classical violation bit to remove a rejecting branch, undermining soundness.Quantum error correction protects encoded quantum data, but the final classical violation data is effectively repetition encoded and remains vulnerable.Source: §2.3 · pp. 13–14

2.4 Solving the Postselection Problem Part 1: Zero-Error Quantum MPC

• The authors resolve zero-error VQSS for a 1/polylog(n) fraction of cheaters, using BGW code properties and quantum gate teleportation for universal MPC.Gate teleportation and CCZ-state distillation [NP25] enable universal operations; instantiating the approach with an almost-good QLTC yields a 1/polylog n-tolerant protocol.Source: §2.4 · pp. 14–15
• For commuting Hamiltonians, an optimal witness can produce a deterministic measurement string, eliminating the readout postselection attack; this reasoning fails for non-commuting terms.Sequential measurements of non-commuting terms can yield a no-violation string with nonzero probability even when the witness has high energy.Source: §2.4 · p. 15

2.5 Solving the Postselection Problem Part 2

• Noisy repetition readout, which independently flips each player's outcome bit with probability γ, weakens a single cheater's ability to infer the global branch, but does not stop colluding cheaters across cliques.For one cheater, the honest players' probability of seeing 1 after postselection onto 0 becomes approximately γ + γ(1 − ϵ)/ϵ to first order in γ; coordinated cross-clique postselection can still suppress the all-one branch.Source: §2.5 · pp. 16–17
• Friendly noisy postselection by honest players cancels cheater-induced branch bias when η is chosen relative to γ, while preserving completeness in YES instances.The common postselection factor reduces the state's norm but leaves the normalized branch weights at ϵ and (1 − ϵ).Source: §2.5 · pp. 17–18

2.6 Discussion

• The MPC framework needs robust, clique-like local communication neighborhoods with bounded degree, which HDXs provide where ordinary expander neighborhoods are tree-like.The authors identify alphabet reduction through proof composition as a natural next step, citing classical PCPP-based approaches.Source: §2.6 · pp. 18, 20
• The parameter regime and combinatorial-soundness focus avoid the Brandao-Harrow barrier [BH13], but general-soundness extension is not immediate because MPC may need to tolerate broader communication noise.Friendly postselection also poses a difficulty: under stated hypothetical conditions it could imply a QMA protocol for PostBQP, while adversarial fault tolerance for postselection circuits remains unknown.Source: §2.6 · p. 19
• A tensor-product ground state of k-qubit GHZ copies illustrates why alphabet reduction for generic Hamiltonians seems difficult, though the authors leave it open for their constructed Hamiltonians.They identify this as a direction for future work.Source: §2.6 · p. 20

2.7 Organization

• The proof roadmap covers protocol properties, quantum routing, fault-tolerance analyses for commuting and non-commuting inputs, protocol-to-Hamiltonian conversion, and assembly of the results.Section 3 gives preliminaries; Sections 4–7 develop the protocol and its analyses, Section 8 converts it into a Hamiltonian, Section 9 assembles the pieces, and Appendix A proves a robust variant of the [AALV09] detectability lemma.Source: §2.7 · p. 20

3 Preliminaries

• The preliminaries fix asymptotic notation, subset sampling, and the expectation-inner-product convention for L2 spaces.Source: §3 · p. 20

3.1 High-Dimensional Expanders

• HDXs are simplicial complexes with links and face distributions; the paper requires d-partite local spectral expansion with λ ≤ 1/polylog n and regular top-face and vertex distributions.Source: §3.1 · pp. 20–21
• Sparse HDXs can be constructed with q = Θ(log^c n), λ ≤ 1/√q, d < loglog_c n, n ≤ |X(1)| ≤ 2n, and vertex participation at most q^O(d^2) d-cliques.All vertices have isomorphic links and the same degree.Source: §3.1 · p. 21

3.1.1 Sampling Properties of HDX

• Up/down operators encode sampling between face levels and are adjoints; the down-up walk's second-largest singular value is at most α + poly(i)λ for α ∈ (1/i, 1).Source: §3.1.1 · p. 22

3.1.2 Concentration on HDX

• The preliminaries present an HDX Chernoff bound and a separate low-mean sampling bound for Boolean functions on partite link expanders.Source: §3.1.2 · pp. 22–23

3.2 Quantum Error Correction

• A Clifford encoding unitary exposes the syndrome in the last n − k qubits; reversible decoding applies the chosen correction, decodes the logical qubits, and retains the syndrome register.The retained syndrome register makes the overall map reversible.Source: §3.2 · pp. 24–25
• For any Pauli error, reversible decoding yields an encoded logical Pauli, and a t-bounded-distance decoder removes its logical effect when t < ∆/2 and |E| ≤ t.Source: §3.2 · pp. 25–26
• For the repetition code, fewer than d/2 X-errors produce no logical X component after reversible decoding; the decoded logical error is I or Z.Source: §3.2 · p. 27
• If |I| < d/2, then xI has strict majority 0 and b(I) = 0.Source: §3.2 · p. 27

3.3 Fault Tolerance Notions

• A fault-tolerant distributed protocol maps an encoded input with bounded deviations to an encoded output with specified deviations despite faults on an allowed set of graph edges.The framework defines edge faults through Pauli operators on player registers or communications, and applies guarantees to executions whose faulty-edge measure is bounded.Source: §3.3 · pp. 28–29
• A friendly protocol maps an arbitrarily Pauli-deviated input to an output that is a bounded deviation from an encoding of some state.Source: §3.3 · p. 29
• Register-specific deviations bound Pauli-error support, and the framework handles superpositions of adversarial Pauli errors by linearity.The notion can be applied to multiple code blocks, with a separate deviation threshold for each register.Source: §3.3 · pp. 27–29
• Sequentially composed fault-tolerant gadgets remain fault-tolerant for the composed operation, while parallel gadgets do so for tensor-product operations, with fault sets combined by union.The parallel guarantee assumes fault tolerance is preserved when adjoining an untouched reference register.Source: §3.3 · pp. 29–30

4 Quantum Multiparty Computation with Zero Error

• The protocol tolerates an inverse polylogarithmic fraction of corrupted players and communication links while guaranteeing an exactly correct output up to faults on boundedly many qubits.It relies on explicit quantum locally testable codes with efficient robust decoding and asymptotically good codes with transversal CCZ.Source: §4 · p. 31
• Players verify encoded input wires with VQSS, compute gate by gate on shared encoded data, and suppress errors between gates so the components compose for circuits of arbitrary length.Transversal Pauli and CNOT gates, distillation, and teleportation supply the required operations; sequential composability preserves an exactly correct logical output.Source: §4 · pp. 31–32
• qLTC checks support zero-error VQSS, while a robust decoder suppresses faults introduced by repeated VQSS applications.The decoder prevents faults from spreading across repeated uses.Source: §4 · p. 31

4.1 Noise Model and Code Requirements

• An almost-good qLTC family satisfies the stated code assumptions with δ = 1/polylog(n).The assumptions require bounded-degree checks with soundness at least δ and an efficient robust decoder.Source: §4.1 · p. 33

4.2 Verification of Distributed Codewords

• For the qLTC codes specified by Assumption 4.2, few detected violations guarantee that the state is close to the code space, making the protocol zero-error.The protocol is simpler than the VQSS protocol for CSS codes described in, but its applicability is restricted to the stated qLTC family.Source: §4.2 · p. 33
• The protocol measures qLTC checks assigned to players and uses a thresholded count followed by Byzantine agreement to produce a shared accept-or-reject bit.Checks are partitioned into constant-many disjoint groups; the protocol uses encoded one-to-all-to-one communication for check measurements.Source: §4.2 · pp. 33–34
• Under the stated fault and input-error conditions, the protocol’s completeness and soundness guarantees restrict deviations on the input/output registers to a set of O(√ε n) players.The threshold is set to (wc0 + 2κ)√ε m, and the guarantee assumes an input Pauli deviation of the form specified in the proposition.Source: §4.2 · pp. 34–35
• Each player handles at most poly(n) qubits and gates during the protocol.The verification protocol is also used for states supplied by a QMA prover and as a subroutine in later distributed state-preparation procedures.Source: §4.2 · pp. 34–35

4.3 Error Suppression

• Error suppression is needed because faults may not stay on a fixed set of shares, especially when secret sharings move between cliques with different fault patterns.The protocol is built from the robust decoder/error suppressor in Assumption 4.2.Source: §4.3 · p. 37
• The repeated protocol measures qLTC syndromes and applies the constant-depth error-suppressor circuit from Assumption 4.2 in each repetition.The protocol uses encoded one-to-all-to-one transmission to route qubits to the players applying each gate.Source: §4.3 · p. 38
• The protocol provides a fault-tolerant identity gadget when the faulty edge set satisfies the stated bound, with polynomial per-player qubit and gate usage.The proposition gives a residual-error guarantee parameterized by √ε and the faulty edge set.Source: §4.3 · pp. 38–39
• After R = ceil(log100(2n)) rounds, repeated suppression gives residual error O(s); if F is empty, then s = 0 and the integer residual tR = 0.Source: §4.3 · p. 39

4.4 Transversal Gates and Classical Adaptivity

• The underlying CSS qLTC provides transversal logical Pauli, CNOT, and SWAP gates.The proposition’s adaptive setting uses gates with transversal physical implementations.Source: §4.4 · pp. 39–40
• The adaptive operation measures the first ℓ logical qubits, computes f from the outcomes, and applies Gf(x) to the remaining m codeblocks.The measured qubits may be measured in the computational or Hadamard basis as specified by B.Source: §4.4 · p. 40
• Players decode the logical values, compute f locally, apply their portions of the transversal gates, and then run repeated error suppression on the remaining codeblocks.The classical control bit can be discarded after the classically controlled transversal gate.Source: §4.4 · pp. 39–40
• Each output codeblock has a final Pauli deviation supported on at most c′√ε n qubits, with polynomial per-player qubit and gate usage.The proposition states the output guarantee for each of the m output codeblocks.Source: §4.4 · p. 40

• Gate teleportation uses |CZ⟩ for CZ and |+⟩ for Hadamard, with logical operations simulated using Protocols 3 and 4.The Hadamard teleportation circuit also uses a CZ gate, implemented recursively by Protocol 6.Source: §4.5 · pp. 44, 46, 47
• The stabilizer-state distillation used by Protocol 5 converts sufficiently close multi-copy inputs into |0⟩, |+⟩, or |CZ⟩ using polynomially many specified operations [NP25].The input may be δψnψ-deviated from the target copies and need not be Pauli-deviated.Source: §4.5 · p. 44
• Protocol 5 fault-tolerantly initializes logical |0⟩, |+⟩, or |CZ⟩ on distributed codeblocks.It prepares and distributes candidate states, verifies codeblocks, then applies logical distillation to accepted blocks.Source: §4.5 · pp. 44, 46
• Protocol 6 implements logical H and CZ fault-tolerantly, with parameters depending on gate support size m and error rate ε.The stated guarantee covers m ∈ {1, 2}; the proof in this part establishes the CZ case, whose output is a [T_es√ε]_2-deviation from EncQ(CZ |ψ⟩).Source: §4.5 · pp. 47, 49

4.5 Clifford Gates

• The Hadamard case uses Fact 4.10’s fixed teleportation circuit with Protocols 5, 4, and 3, and the previously proved CZ case.The construction implements logical resource preparation, adaptive logical steps, cleanup, and its single logical CZ box, respectively.Source: §4.5 · p. 49
• The chain-length and deviation bounds ensure every invoked proposition, including the recursive CZ case, remains within its required input radii.The proof bounds each relevant chain by L boxes and verifies the active blocks stay within the admissible radii.Source: §4.5 · p. 49
• The Hadamard teleportation protocol’s final output block is a c′√ε-deviation from EncQ(H |ψ⟩).The argument expands terms along chains of boxes that feed into and affect the final logical output block.Source: §4.5 · p. 49

4.6 Non-Clifford Gates

• CCZ gate teleportation uses a |CCZ⟩ resource state, CNOT gates, destructive Z-basis measurements, and adaptive Pauli and CZ gates.Source: §4.6 · p. 50
• Distributed magic-state preparation combines qLTC-encoded CCZ inputs, verification, and logical distillation.The distillation protocol takes multiple approximate CCZ states and outputs |CCZ⟩ using CNOTs, measurements, and adaptive Pauli and CZ gates.Source: §4.6 · p. 50
• The teleported CCZ protocol is a (√ε, Kε)-fault-tolerant protocol for CCZ.It prepares a logical CCZ resource state, then performs logical teleportation with adaptive transversal and Clifford gates.Source: §4.6 · p. 51

4.7 Combining Everything

• The construction handles Init, X, Y, Z, CNOT, H, CZ, and CCZ gates, with each gate occurrence implemented by its corresponding whole-register gadget.The gate set is universal and chosen for simplicity of presentation.Source: §4.7 · p. 53
• Composing the input-sanitization stage with the gate gadgets yields a (Q⊗k, ccomp√ε, Kε)-fault-tolerant protocol for the ideal circuit.The gadgets are composed sequentially with matching code families and thresholds.Source: §4.7 · p. 54
• For an arbitrarily Pauli-deviated encoded input, the protocol outputs a ccomp√ε-deviation of an encoded state U|ξ⟩ for some k-qubit state |ξ⟩.Input sanitization replaces a rejected input with an encoded |0⟩ state so computation can proceed.Source: §4.7 · pp. 51, 54
• The circuit protocol is efficiently constructible, with polynomial work per player in n and T.It invokes O(T + k) gadgets, each with per-player work complexity poly(n).Source: §4.7 · p. 54

4.8 Converting to Repetition Code

• The readout outputs the repetition-code encoding of the input state, with one qubit held by each player.It prepares fresh encoded |0⟩ blocks, applies logical CNOTs from the input block to each, and then routes and decodes the blocks.Source: §4.8 · p. 54
• The protocol’s output differs from the ideal repetition encoding only on qubits held by players in W(F), yielding a fault-tolerant identity protocol with the repetition code.The guarantee applies under the stated input-deviation and faulty-edge bounds.Source: §4.8 · p. 55
• Each good player outside W(F) decodes the correct logical qubit after routing.The protocol uses polynomially many qubits and gates per player.Source: §4.8 · p. 56

5.1 The Classical Clique-to-Clique Routing Protocol

• The classical template routes cliques according to any permutation in O(log n) rounds, using majority transfers and achieving the stated bounds on failed paths in both corruption regimes.A transfer succeeds when the endpoint cliques are good; a union bound over path length yields at most η + µ/log^c n failed paths in the first regime and η + 1/log^c n in the second.Source: §5.1 · pp. 57–58

5.2 One Clique-to-Clique Transfer in the Quantum Setting

• Quantum clique-to-clique transfer encodes each qubit into an inner code, forwards it through the shared smaller clique, then decodes and applies error suppression.When each endpoint clique has at most β bad edges, the protocol is a (Q, ctransfer√β, F)-fault-tolerant identity protocol and uses at most poly(d) qubits and gates per player.Source: §5.2 · p. 59

5.3 Partial Fault-Tolerance Preliminaries

• Sequential composition of partially fault-tolerant protocols preserves partial fault tolerance, with c12 = c2c1 and β12 = min{c2β1 + β2, 1}.The bad output block set can depend on the bad input blocks and fault pattern, but not on the particular Pauli deviation on good blocks.Source: §5.3 · pp. 61–62

5.4 Clique-to-Clique Routing in the Quantum Setting

• Proposition 5.6 routes any permutation in O(log n) rounds with work (1/λ)^O(d^2), as a partially fault-tolerant protocol for the N-qubit permutation unitary.The protocol has parameters (Q⊗N, crouteδ, Gµ, µ log^c n). The stated regimes are low corruption (µ, λ ≲ 1/log^{c+1} n), almost-constant corruption (µ ≲ 1/polylogloglog n, d = Θ(log log3 n), λ = 1/log^c n), and constant corruption (µ < µ0, d = Θ(log log2 n), λ = 1/log^c n), the last assuming an asymptotically good quantum LTC.Source: §5.4 · pp. 62–63
• Each clique participates in at most O(log N) paths, bounding the fraction of failed paths by µλ·O(log N) ≤ µ/log^c n for sufficiently large n.Source: §5.4 · p. 63
• R is a (Q⊗N, crouteδ, Gµ, µ log^c n)-partially FT protocol for Uπ, with codewords within crouteδ on at least 1−µ/log^c n of paths.The constant croute depends on the inner- and outer-code parameters used in Lemma 5.2.Source: §5.4 · p. 63

6 Distributed Computing Protocol for Commuting LH

• The protocol implements the sequential measurement circuit using quantum-multiparty computation on HDX cliques, routes outputs between layers, and converts measurement blocks to repetition-code blocks.Witness qubits are MPC-encoded; each layer's clique gates are followed by routing for the next layer's inputs.Source: §6 · pp. 64–65
• For commuting Hamiltonians, adversarial faulty executions under the stated edge-corruption bound yield a large expected fraction of vertices reporting violations through their OR checks.Theorem 6.2 assumes ground energy εM and corruption measure bounded by min(ε polylog n, ε0).Source: §6 · p. 65

6.1 Completeness

• A zero-energy ground state encoded for the protocol produces zero expected vertex-check violations, since the measurement outputs encode only 0s.Claim 6.3 establishes this completeness result for the encoded ground state.Source: §6.1 · p. 66

6.2 Robust Measurement Circuit for a Gapped Commuting Hamiltonian

• For a commuting Hamiltonian, simultaneous diagonalization implies that inputs of energy δ yield measurement strings with at least δm ones, supporting robust detection.The sequential circuit measures each term; each common eigenstate produces a definite outcome string whose weight reflects its energy.Source: §6.2 · p. 66

6.3 Soundness of Serial Repetition

• Serial repetition uses HDX concentration to ensure many vertex OR checks detect violations, even after excluding bad cliques and vertices; the lemma treats two regimes of μ−η relative to λ².The lemma uses constant d when μ−η ≤ λ² and d = Θ(loglog2n) when μ−η ≥ λ².Source: §6.3 · pp. 67–68

6.4 Fault Tolerance of the Protocol under Adversarial Edge-Corruptions

• The fault-tolerance analysis bounds exceptional clique sets and shows the protocol is fault-tolerant outside their forward light cone, using the initial MPC gadget to handle arbitrary starting deviations.The section's proposition formalizes fault tolerance under an edge-corruption pattern.Source: §6.4 · p. 70
• Outside the exceptional gates’ combined light cone, data blocks have errors of weight at most τd, while measurement-block errors are confined to bad vertices.The guarantee applies to outputs whose backward light cones avoid the exceptional gates; the exceptional output blocks and work registers are absorbed into an auxiliary register.Source: §6.4 · pp. 70, 72

6.5 Moving from Physical Measurements to Logical Measurements

• For every valid tensor-network state, physical encoded-output measurements are represented by a logical density matrix supported on states with Pauli errors localized to Kdata and Kmeas.The data-wire support lies in Kdata; measurement-wire X-support lies in Kmeas, while measurement-wire Z-support may be arbitrary.Source: §6.5 · pp. 73–74
• Measurements on the logical density matrix can in turn be represented by a mixture of valid logical-circuit inputs for projectors on measurement qubits in K′.Each pure state in the mixture has the form |ξ⟩⊗|0m⟩.Source: §6.5 · pp. 75–76

6.6 Soundness of the Protocol for the Tensor-Network State

• The protocol-space vertex OR-check Πv computes the OR of measurement bits stored at vertex v, and modified checks restrict the included locations to those outside K′ and good in their clique.Each vertex stores physical measurement bits for the cliques and layers containing it.Source: §6.6 · p. 76
• Fault tolerance ensures that for a good vertex, each relevant repetition block has no X-error at its stored coordinate and less than d/2 total X-weight, so majority decoding returns the correct bit.This is used to show the modified projectors act identically on the relevant state components.Source: §6.6 · p. 77
• Lemma 6.18 assumes bad-edge measure at most ε, λ ⩽ 1/log^(c+1) n, and ε ≲ μ log^c n.It is stated in the parameter setting of Proposition 5.6.Source: §6.6 · p. 78
• HDX concentration bounds the maximum fraction η of omitted gates touching any circuit layer by Oℓ(ε/log^c n), which the lemma’s assumption makes at most μ/2.The bound uses concentration lemmas in three relevant regimes, as in Proposition 5.6.Source: §6.6 · p. 78
• Ev Tr(Πv|Ψ⟩⟨Ψ|) ≳ϵ/λ in the low-energy regime ϵ ⩽λ², and choosing λ = 1/polylog n completes the proof under the assumed corruption bound.The proof applies Lemma 6.17 with parameters μ = ϵ and μ(E).Source: §6.6 · p. 78

7 Modified Distributed Computing Protocol for Non-Commuting LH

• Noisy repetition readout limits adversarial postselection on 0, while weak gates favoring 1 compensate for residual postselection; noisy repetition alone is insufficient.The repetition code’s vulnerability to Z errors motivates the change; a coherent superposition of error patterns can otherwise collapse the measurement distribution to the all-zero string.Source: §7 · pp. 79–80

7.1 Completeness

• With a zero-energy ground state, the modified protocol has near-perfect completeness and an efficiently preparable output state; threshold-check analysis requires (τout − γ′) · √Cmin ≥ polylog n.The measurement bits follow an i.i.d. Bernoulli distribution with parameter γ′.Source: §7.1 · p. 82

7.2 Robust Measurement Circuit from the Robust Detectability Lemma

• For Hamiltonians meeting Assumption 7.4, the sequential measurement circuit is (ϵ/r, ϵ/r′, 2^−r′′ϵM)-robust when its unnormalized minimum energy is at least ϵM.The result adapts the detectability lemma to sequential measurements, where the state changes between layers; r, r′, and r′′ depend only on the assumption’s constants.Source: §7.2 · p. 83

7.3 Fault Tolerance of the Measurement Distribution under Adversarial Edge-Corruptions

• For corrupted edge sets E with µ(E) ≤ ε0, Pγ has fault-tolerance guarantees outside exceptional clique sets of size at most κN per layer, with κ ≤ µ(E)/polylog n.The exceptional sets depend only on E; the guarantee applies to fault patterns supported on E.Source: §7.3 · p. 84

Later we will choose

• When µ(E)/polylog n ≲ ϵ, good vertices in good cliques hold a noisy repetition encoding of a logical distribution supported with probability at least 1 − 2^−poly(M) on strings of weight ≳ ϵM.The underlying distribution excludes the lightcone of exceptional cliques.Source: Later we will choose · p. 85
• The physical distribution P(z) remains mostly supported on high-weight strings after good-clique noise is added, provided the stated fault and postselection conditions hold.The bad-clique-only distribution is related to a logical distribution supported on strings of weight at least c′ϵM; good-clique noise does not significantly increase low-weight mass.Source: Later we will choose · pp. 88–89
• The noisy postselection operator Aη is needed to bound the tilting caused by adversarial faults on good cliques; without it, low-weight mass may increase.The authors leave open whether tighter control of the logical distribution could avoid this issue.Source: Later we will choose · p. 89

7.4 Proof of Omitted Claims

• For at most O(Mµ(E)/polylog n) faults, the physical distribution reduces to a faulty logical sequential measurement distribution, to which robust detectability applies.The resulting logical distribution places all but o(1) probability on strings with weight at least c′ϵM.Source: §7.4 · p. 91

7.5 Soundness of the Tensor-Network State

• When ϵ ≥ 1/polylog n, constant-order γ, γ′, and 1−γ′′ with η ≈ 1/2 permit vertex-threshold checks despite significant Bernoulli noise.Choosing γ ≲ 1/poly(Cmax) and η = γ^0.3 instead recovers the serial-repetition setting, but requires strong postselection as η tends to zero.Source: §7.5 · pp. 92–93
• Under the HDX sampling lemma’s assumptions, an Ω(1) fraction of vertices see many good cliques from S while having few locally bad cliques.The lemma requires λ ≤ 1/poly(d), µ ≳ Ω(1/log^c n), and d = Ω(c^2 log log^2 n); its two vertex properties are quantified in the passage.Source: §7.5 · p. 93
• At least an Ω(1)-fraction of vertices satisfy all three events and hence have the desired properties in their local views.The proof uses a union bound and the HDX-Chernoff lemma to bound bad cliques in each selected vertex’s link by O(1/log^c n).Source: §7.5 · p. 94
• The expected OR-check energy is at least (1 − (1 − γ′′)Cmax)ϵ polylog n, with the factor accounting for noise.The argument uses Lemma 6.9: vertices seeing at least one 1 have measure ϵ polylog n.Source: §7.5 · p. 95
• When ϵ ≳ 1/√Cmin, a vertex violates the threshold check with probability at least 1/2; in the stated HDX setting for ϵ ≥ 1/polylog n, expected threshold-check energy is at least 1/200.Source: §7.5 · p. 95

8.1 One-Qubit Toy Example

• The [ABN24] toy construction uses gate teleportation, replacing non-invertible Bell projections with an invertible perturbation that introduces Pauli faults handled by fault tolerance.Each teleportation step can produce nontrivial Bell outcomes with amplitude controlled by δ.Source: §8.1 · pp. 95–96

8.2 The Tensor-Network Circuit-to-Hamiltonian Mapping

• The graph-grouped tensor-network Hamiltonian is frustration-free, with ground states encoding noisy executions of the distributed protocol with Pauli faults.Its edge and vertex terms enforce communications and local computations, respectively.Source: §8.2 · pp. 96, 98, 99

8.3 Combinatorial Soundness

• For δedge, δvertex ≤ e−poly(m,log |V|), any ε-combinatorial state yields output e−polylog(m,|V|) max(ε|V|,1)-close in trace distance to a mixture of (Θ(ε), Θ(ε))-faulty executions.The executions have at most Θ(ε) faulty vertices and edges.Source: §8.3 · pp. 99–100

8.4 A Modified Construction for Handling Postselection Gates

• For protocols with postselection gates, the modified encoding uses a noisy postselection operator with η = 1/2−o(1) and remains frustration-free.The modification is motivated by the non-commuting Hamiltonian measurement circuit; the small amount of postselection is crucial for fault-tolerance analysis.Source: §8.4 · p. 103
• For any ε-combinatorial state, the reduced output state is close in trace distance to a mixture of outputs from Θ(ε)-vertex- and edge-faulty executions.For ε = 0, the same statement holds with m replacing m/ε in the exponent.Source: §8.4 · p. 103
• The modified proof treats applying A⊗M to output qubits as noisy postselection and chooses injectivity parameters to establish the soundness bound.A commutes with Π, and the proof uses ηM · I ≺ A ⪯ I.Source: §8.4 · pp. 103–104

9 The Final Reduction

• Preprocessing builds a high-dimensional expander with O(n) cliques, pads the input Hamiltonian, then forms a sequential circuit measuring N constraints per layer.Source: §9 · p. 105
• The reduction implements the measurement circuit through a distributed protocol, using P for commuting inputs and Pγ for non-commuting inputs, then unweights its edges.Source: §9 · pp. 105–106
• Communication qubits are encoded into linear-distance quantum codes and sent across parallel edges; the protocol is then converted into a 2-local Hamiltonian with vertex output constraints.Source: §9 · p. 106
• ε_max(n) = 1/polylogloglog n unconditionally, and becomes Θ(1) assuming asymptotically good quantum locally testable codes.The stated unconditional corruption tolerance comes from existing almost-good quantum locally testable codes.Source: §9 · pp. 106, 108
• 2^-polylog(n) bounds output ground energy when H_in has zero ground energy; for commuting inputs, completeness instead has exactly zero energy.Source: §9 · pp. 106, 108
• ε = min(ε_in polylog n, ε_max(n)) is guaranteed as combinatorial energy when H_in has normalized ground energy ε_in; the output is 2-local on O(n) qudits.The input is assumed to have constant locality and degree; the fixed-constraint-set assumption is needed only for non-commuting inputs.Source: §9 · pp. 105–106
• For ε ≲1/log n, D and log Σ are polylog(n); for ε ≳1/log n, the construction uses d = O(polyloglog n) and λ = 1/polylog n.These parameter regimes determine the interaction-degree and alphabet-size bounds.Source: §9 · p. 107
• Soundness transfers because P′ corruption induces O(µ′) corruption in Pγ, allowing the protocol’s soundness analysis to yield combinatorial energy at least ≳ ε polylog n.Source: §9 · p. 108

A A Robust Detectability Lemma for Circuits

• The proof compares an energy-based lower bound on the weight of low-violation outcomes with an upper bound obtained by decomposing their post-measurement states into local sectors.The energy lower bound follows because every nonzero post-measurement state has energy at least E0.Source: A A Robust Detectability Lemma for… · pp. 112, 114
• Pyramids grown downward from layer terms contain O(1) constraints and qubits, allowing inside factors to be separated from commuting outside factors.Constantly many disjoint pyramid families cover each layer, and the argument is repeated for later-layer suffixes.Source: A A Robust Detectability Lemma for… · pp. 112, 113, 115, 117
• Within each pyramid, X-blocks make projectors act as 0 or I, while products of projectors contract the Y-space by a constant factor.A sector with s Y-pyramids is suppressed by θ^(2s), while its top-layer energy is at most s plus the first-layer violation count.Source: A A Robust Detectability Lemma for… · pp. 113, 115, 116
• Unlike the original detectability lemma [AALV09], Lemma A.5 controls the incoherent outcome probability of the sequential measurement circuit, retaining a tail used for robustness to adversarial faults.The original formulation bounds a coherent product of layer projectors; the sequential version directly bounds the sum over low-violation outcomes.Source: A A Robust Detectability Lemma for… · p. 114
• The low-violation outcomes have an exponentially small total probability when the ground-energy lower bound exceeds a constant multiple of the per-layer violation threshold.The lemma applies to every input density matrix and retains an exponentially small tail in the threshold.Source: A A Robust Detectability Lemma for… · pp. 114, 117

A.1 Robust version

• Lightcone arguments confine the effects of faults to a bounded number of input ancillas and output measurement bits, even for coherent sums of non-unitary fault patterns.The circuit’s constant depth and bounded-size gates bound the affected ancillas in terms of the number of faulty locations.Source: §A.1 · pp. 118, 119, 121
• For ground energy at least E0, the uncorrupted circuit outputs all zeros with probability at most 1/(1 + κE0), and at most 2^-κ′E0 when E0 is bounded above.The constants depend on the Hamiltonian parameters and, for κ′, the upper bound on E0.Source: §A.1 · p. 118
• Under Assumption A.1, the sequential measurement circuit is (ϵ/r, ϵ/r′, 2^-r′′ϵM)-robust for constants depending only on that assumption’s parameters.The bound applies when the Hamiltonian has minimum eigenvalue at least ϵM.Source: §A.1 · pp. 120–121