Optimization Using Locally-Quantum Decoders

Authors: Noah Shutty, Avijit Mandal, Seyoon Ragavan, Quentin Buzet, André Chailloux, Nicholas C. Rubin, Abid Khan, Sami Boulebnane, Ruslan Shaydulin, John Azariah, Stephen P. Jordan · arXiv:2604.24633 · submission cycle 2026-04-28 · score 8/10 (HIGH)

Abstract

It was pointed out in [JSW+25] that widely-studied optimization problems such as D-regular max-k-XORSAT can be reduced to decoding of LDPC codes, using quantum algorithms related to Regev's reduction. LDPC codes have very good decoders, such as Belief Propagation (BP), and this therefore makes D-regular max-k-XORSAT an enticing target for this class of quantum algorithms. However, BP was found insufficient to achieve quantum advantage. Here, we develop an intrinsically quantum decoding technique, which decodes classical LDPC codes subject to coherent superpositions of bit flip errors. For average-case instances of D-regular max-k-XORSAT drawn from Gallager's ensemble, this quantum decoder strongly outperforms classical belief propagation at many values of k and D. For some (k,D) the approximate optima achievable using this decoder surpass both Prange's algorithm and simulated annealing. However, we stop short of achieving quantum advantage because we identify an enhancement to Prange's algorithm that recovers a precise tie.

Executive summary

This is a major paper from the Google Quantum AI / JPMorgan / Inria axis on the boundary of quantum advantage for combinatorial optimisation. Building on Decoded Quantum Interferometry (DQI) and Regev's reduction, the authors design a new locally-quantum decoder based on Fine-Grained Unambiguous Measurements (FGUMs) that are aware of the parity-check structure of the dual code. For D-regular max-k-XORSAT instances drawn from Gallager's ensemble, Regev+FGUM beats both Prange's algorithm and simulated annealing for several (k,D) pairs (specifically (5,6), (6,7), (6,8), (7,8)). The quantum advantage claim is withheld because they construct a classical "Turbo Prange" that exactly matches the FGUM scores. Comparison with QAOA (depth p=16) is mixed: QAOA wins for (3,5)…(3,8) and (4,8), FGUM wins for the denser instances; in the large-D limit at fixed k, p=14 QAOA dominates Regev+FGUM asymptotically. The relevance to Yuan: this is the most quantitatively complete head-to-head between Grover-style structured-feasible-set quantum algorithms (Y4 territory) and QAOA (Y1, Y2, Y3 territory) on a clean benchmark, with explicit asymptotic and finite-instance comparisons.

Main contribution

Three contributions: (1) a new locally-quantum decoder (FGUM) that performs unambiguous state discrimination on groups of qubits aligned with the parity checks of the dual code, exploiting the a priori knowledge that uncorrupted codewords have parity zero on each check (Section IV); (2) an error-bound theorem (Section VI) for Regev's reduction that propagates the per-codeword decoding failure rate ε into a satisfaction-fraction bound for max-XORSAT, generalising prior bounds (Chailloux 2023, JSW 2025) to a form usable here; (3) Turbo Prange (Section VIII), a classical algorithm combining Prange with greedy local optimisation that exactly reproduces the FGUM satisfaction fractions, blocking the quantum advantage claim.

Key theorems / lemmas / algorithms

• Definition (Quantum Decoding Problem, QDP): given ∑_e P˜(e) |d + e⟩ for uniform d ∈ C^⊥, recover d.
• Definition (Code-aware FGUM, Section IV): partition the m qubits into m/D blocks aligned with parity checks; on each block apply an unambiguous measurement that exploits the constraint B^Td = 0; failed measurements yield erasures rather than bit flips.
• Equation (eq:emax) for maximum tolerable erasure rate: e_max ≈ e_max/D + (k/D - 1/D)(1 - (1-e_max)^D); for fixed k ≥ 3, large D: e_max ≈ x_k/D with x_k = (k-1)(1 - e^-x_k).
• Theorem (distributional closeness): if QDP succeeds with probability 1 - ε, the satisfaction fraction of Regev's reduction on average-case v is bounded in terms of ε.
• Theorem (project codeword bound): a "weird Cauchy" inequality controlling overlap of decoder outputs across codewords.
• Algorithmic recipes: Prange — classical Gaussian-elimination-based decoder; Turbo Prange — Prange followed by greedy local search; Regev+FGUM — Regev's reduction with FGUM as the locally-quantum decoder; DQI+BP — the JSW 2025 baseline.
• Asymptotic large-D result (Section IX): Regev+FGUM achieves satisfaction fraction 1/2 + (2π)^-1/2 D^-1/2 + O(1/D) for fixed k; QAOA at depth p achieves 1/2 + ν_p^k √(k/2) D^-1/2 + O(1/D). With p=14, QAOA dominates FGUM at all k ∈ {3,4,5,6}.

Detailed walkthrough

The setup (Sections II–III). Max-k-XORSAT asks for x ∈ F₂ⁿ minimising |Bx - v|, with B a sparse m×n binary matrix. Regev's reduction prepares a state |ψ_P⟩ ∝ ∑_x P(Bx - v)|Bx⟩, biased toward small Hamming distance from v. Via Hadamard duality this becomes the problem of decoding a corrupted dual codeword ∑_e P˜(e)|d + e⟩ where d ∈ C^⊥. For the standard product distribution P_α, each bit of d goes through the classical-quantum channel d_j → √(1-α^⊥)|d_j⟩ + √α^⊥|¬d_j⟩, with α^⊥ = 1/2 - √(α(1-α)). Measurement collapses to BSC(α^⊥); USD measurement (Chailloux 2023) collapses to an erasure channel with rate 2√(α^⊥(1-α^⊥)).

The new idea (Section IV, FGUM). The previously studied locally-quantum decoders all worked block by block but treated each block in isolation. The novelty here is to align the blocks with the parity checks of C^⊥: each block of D qubits is exactly the support of one parity check, so the codeword d restricted to the block is constrained to have even parity. The FGUM measurement on each block is then a fine-grained refinement that uses this constraint to either (a) identify the block exactly with probability p₀ or (b) declare erasure with probability 1 - p₀. Crucially, only Gallager-ensemble matrices admit such an alignment (the construction requires that the parity checks can be partitioned into a perfect matching at the bit-vertex level, which exists for Gallager but not generic LDPC).

Erasure rate and tolerable α (Section V). Equation (eq:E) counts the expected number of F₂-linear equations constraining the erased bits, broken into three cases (parity check defining an erased block, defining a non-erased block, or not aligned with the partition). Setting ν = e_max m and demanding E = e_max m yields the fixed-point equation (eq:emax) whose largest root gives the maximum tolerable erasure rate. The minimum tolerable α follows from α_min = (1 - e_max)(1 - 2^1-D), and the satisfaction fraction comes from substituting back into (eq:simple_satfrac). Numerical evaluation for various (k,D) produces the Regev+FGUM column of Table 1 (re-rendered below).

The error-bound theorem (Sections VI–VII). The decoder fails on individual codewords with some probability ε_d. Sections VI–VII propagate that into a guarantee on Regev's output: for average-case v, the expected satisfaction fraction is close to the ideal one with corrections controlled by the average decoding failure rate. Lemma (innerproduct) and Theorem (weirdcauchy) form the technical core; the key trick is bounding the cross-codeword overlap of decoder outputs using Cauchy-Schwarz with carefully chosen normalisations.

Turbo Prange (Section VIII). The classical antagonist. Prange's algorithm randomly picks a set of bits to "guess" and uses Gaussian elimination to determine the rest, then evaluates objective. Turbo Prange iterates: take the best Prange output, perform greedy local search (single-bit flips lowering the cost), repeat. The authors show empirically — and partly analytically — that Turbo Prange exactly matches Regev+FGUM's satisfaction fractions on the Gallager-ensemble instances. This is the second time (the first was Chailloux 2023's USD-decoder vs. plain Prange) that a locally-quantum decoder has been classically simulated by a Prange-family algorithm. The pattern suggests that to actually achieve quantum advantage, one needs decoders that are not "locally" structured, and the conclusion explicitly flags this as the next direction.

Comparison with QAOA (Section IX). The authors evaluate QAOA at depth p=16 exactly on the (D,k)-regular hypertree using techniques from Boulebnane-Farhi 2021 and Farhi 2025. The finite-instance picture is mixed (Table 1 last column); the asymptotic large-D picture (Table on ν_p^k) is unambiguous: p=14 QAOA strictly dominates Regev+FGUM in the limit of fixed k and D → ∞. So in the limit of dense, sparse-row LDPC codes, QAOA wins.

Conclusion (Section X). The authors are explicit: locally-quantum decoders broaden the toolbox but probably can't break through to true advantage on max-k-XORSAT. The future directions they flag are (i) genuinely non-local quantum decoders such as BPQM (belief propagation with quantum messages), (ii) adaptive strategies. This is a "good honest no" paper that maps the boundary precisely.

Figure rendering: the paper uses TikZ-drawn Tanner graphs and a few synthetic plots; none are PDF/PNG figures and so none were extracted. Refer to Figure 1 of the source PDF for the (2,3)-Gallager Tanner graph illustration.

Citations to Yuan's papers

Overlap with Y1–Y6

• Y1 (warm-started QAOA): Adjacent — Y1 is QAOA scaling at constant depth; this paper's Section IX is QAOA scaling at depth p=14, p=16 against a quantum-decoder baseline. Both share Boulebnane-Farhi 2021's BF21 hypertree analysis as the QAOA cost model.
• Y2 (quasi-binary portfolio QAOA): Tangential — QAOA is the shared object but the constraint structure and encoding differ.
• Y3 (QAOA DGMVP portfolio): Tangential method overlap. Y3 uses dual annealing / layerwise as parameter optimisers; this paper's QAOA evaluations are at hypertree-exact angles, no parameter optimisation needed at infinite-size limit.
• Y4 (Grover + ADMM cardinality-constrained): Strong conceptual overlap. Y4 achieves O(√(C(n,k)/M)) rotations — an amplitude-amplification advantage that is in the same family as the quantum-advantage claims being adjudicated here. The paper's central conclusion (locally-quantum decoders can be matched by Prange-family classical algorithms) is a cautionary tale for any structured-quantum-search advantage claim. Y4's epsilon-approximation guarantee should be examined against the same benchmark: is there a "Turbo" classical algorithm exploiting the cardinality structure that matches Y4's quantum output?
• Y5 (GW + Pauli sparsity): Method-class overlap on dequantisation arguments. Y5 also navigates the boundary of quantum advantage by demonstrating quantum-inspired classical algorithms achieving exponential speed-ups via Pauli sparsity. Both papers contain explicit "no advantage here" or "matched by classical" findings, and Y5's Pauli-sparse Gibbs-state framework provides the kind of structural classical insight that DQI/Regev+FGUM lack.
• Y6 (PBR Heron2): Unrelated.

Recommended action for Yuan

• Cite in Y4 follow-ups discussing quantum-advantage boundaries. This paper is the most current benchmark for the "structured-search-vs-Prange" pattern. If Y4 has follow-ups that defend its O(√(C(n,k)/M)) advantage against possible classical analogues, this paper's "Turbo Prange" construction is the cautionary example to reference.
• Read deeper. Yuan should know the Section IX QAOA-vs-decoder asymptotic results — they shape the "can QAOA beat structured quantum decoders?" question that any post-Y3 QAOA scaling paper has to acknowledge. The fact that p=14 QAOA dominates Regev+FGUM in the dense limit is a useful data point when arguing for QAOA's relevance.
• Consider a methodological cross-pollination with Y5. Y5's quantum-inspired SDP relaxations leverage Pauli-sparsity; Regev+FGUM's setting (Gallager-ensemble LDPC codes) has its own sparsity structure. A paper exploring whether Y5-style Pauli-sparse Gibbs-state preparation gives a quantum-inspired classical algorithm matching Regev+FGUM would be a natural Y5 extension — and would put Yuan in conversation with the Google/JPMorgan Quantum AI authors on the dequantisation frontier.

Deep analysis generated from LaTeX source · not peer review · author claims not verified.