Quantum Decoding Algorithms: Quantum Speedups in Optimization

Jan Ljubas, Tim Byrnes · arXiv:2605.00312 · submitted 2026-05-04 · score 8/10 (HIGH)

Abstract

Attaining a quantum speedup in solving practically useful optimization problems has been one of the holy grails in the field of quantum computing. While prior approaches have demonstrated speedups for certain structured problem classes, establishing a clear and scalable advantage on broadly useful practical optimization problems remains challenging. Recently, a new approach to solving the max-LINSAT class of optimization problems has emerged, called Decoded Quantum Interferometry (DQI). In DQI, a combination of techniques rooted in (classical) coding theory and interferometry are used to obtain the solution of max-LINSAT. In the special problem instance of the optimal polynomial intersection (OPI) problem, strong evidence exists to show that an superpolynomial speedup exists over the best classical methods in obtaining an approximate solution. In this review, we give a self-contained description of DQI and the necessary background to understand the algorithm. Specifically, we give the essentials of Galois fields, optimization problems such as max-LINSAT and OPI, and coding theory, followed by a step-by-step walkthrough of the quantum algorithm and its operating principle.

Executive summary

This is a 24-page tutorial review of Decoded Quantum Interferometry (DQI), the Jordan et al. (2024) algorithm that — in its OPI specialization — gives strong evidence of a superpolynomial quantum speedup over Prange's algorithm for an approximate-optimization task in max-LINSAT. For Yuan, this is the most important quantum-optimization development of the past 18 months and a direct competitor on the same axis as Y3/Y4 ("when does quantum optimization actually beat classical?"). The review is self-contained: it walks through Galois fields, max-LINSAT/max-XORSAT/OPI, coding theory, the seven steps of the DQI circuit, the analytic semicircle-law performance bound, and recent extensions (multivariate OPI, HDQI for non-diagonal Pauli Hamiltonians). It also surveys empirical follow-ups including a noise analysis showing exponential degradation with a noise-weighted sparsity parameter — the same kind of crossover question Yuan studied in Y3.

Main contribution

The paper's contribution is exposition rather than new algorithm. It rederives the DQI target state |DQI⟩ = Σ_{x∈F_pⁿ} P(f(x))|x⟩ where P is a degree-ℓ amplifying polynomial expanded in elementary symmetric polynomials of the constraint values f_i(x), and shows how the Dicke-state structure of these symmetric polynomials enables the seven-step circuit (W/E/S register construction, decoding-via-Berlekamp-Massey, QFT-based syndrome transfer). The authors emphasize three points: (i) the algorithm reduces a quantum-state-preparation task to a classical linear-code decoding problem, so it inherits efficiency exactly when an efficient classical decoder exists for the dual code; (ii) the optimal-weight choice w_k* yields an analytic semicircle-law bound ⟨s⟩/m = (√(ℓ/m·(1−r/p)) + √(r/p·(1−ℓ/m)))² that quantifies the quantum advantage parameter regime; (iii) HDQI (Schmidhuber–Poremba–Quek 2025) extends DQI from diagonal Hamiltonians to general Pauli Hamiltonians via symplectic-code decoding — a strict superset of DQI's reach.

Key algorithms / theorems

DQI target state (Eq. dqistate): |DQI⟩ ∝ Σ_x P(f(x))|x⟩ with P(f) = Σ_kα_kf^k a degree-ℓ amplifying polynomial.
Symmetric-polynomial decomposition (Eq. symmpolydecomp): P(f) = Σ_ku_kP^(k)(f₁,…,f_m) where P^(k) is the elementary symmetric polynomial of degree k — this is what couples the algorithm to Dicke-state preparation.
The seven-step DQI algorithm for max-XORSAT (Sec. 4.3): (1) prepare weight superposition Σ_kw_k|k⟩_W; (2) Dicke-state preparation in error register E; (3) decouple W; (4) apply controlled-(B^Ty) and v·y phases; (5) QFT to map to syndrome register S; (6) syndrome decoding (the heart of the algorithm — Berlekamp-Massey for Reed-Solomon codes in OPI); (7) uncompute and read out x.
Semicircle law (Eq. 1369-1373): ⟨s⟩/m = (√(ℓ/m·(1−r/p)) + √(r/p·(1−ℓ/m)))² for r/p < 1−ℓ/m, otherwise saturates at 1. This characterizes the asymptotic constraint-satisfaction rate under optimal weight choice.
Performance gap on OPI (Sec. 5): for n ≈ p/10, r ≈ ⌊p/2⌋, DQI achieves ⟨s⟩/m ≈ 0.7179 vs Prange's 0.55; the largest gap Δ ≈ 0.21 occurs at n/p ≈ 0.293.
HDQI extension (Sec. 6.2): for H = Σv_iP_i with P_i∈{I,X,Y,Z}^⊗n, prepare ρ(H) = P²(H)/Tr[P²(H)] via pilot state + controlled Pauli + symplectic-code decoding; reduces to LDPC decoding when H is local.
Poisson summation formula for linear codes (Theorem in App. B): the underlying duality QFT(C) → C^⊥ that powers the syndrome-space mapping; explains why DQI generalizes beyond Reed-Solomon.

Detailed walkthrough

Problem framing (Sec. 3 — Max-LINSAT). A max-LINSAT instance is parameterized by (n, m, p, r): n variables in F_p, m linear-equation constraints, target sets T_i⊂F_p each of size r. The objective f(x) counts how many constraints x satisfies, with f_i(x) ∈ {±1}. Special cases include max-XORSAT (p=2, r=1) and OPI (the "optimal polynomial intersection" problem, where x parameterizes a degree-(n−1) polynomial Q over F_p and constraint i asks whether Q(y_i) ∈ T_i).

The amplifying polynomial trick (Sec. 4.2). A naive quantum approach prepares Σ_x(f(x)+m)|x⟩, biasing measurement toward high-f outcomes. DQI strengthens this by preparing Σ_xP(f(x))|x⟩ for a chosen degree-ℓ polynomial P. The crucial observation is that since f_i² = 1, products of f_i's reduce to elementary symmetric polynomials of the constraint values, and these in turn map onto Dicke states |D^m_k⟩ (symmetric superpositions with exactly k excitations). Constructive interference between Dicke amplitudes is what produces the speedup: each f_i₁…f_{i_k} product carries a parity bit about whether an even or odd number of those k constraints is satisfied, and the QFT step turns the algebraic structure of the dual code into amplitude amplification of high-f solutions.

Why decoding shows up (Sec. 4.3 step 6). After the QFT step, the amplitude on |x⟩ depends on whether x can be reached by adding an "error" vector y of Hamming weight ≤ ℓ to a syndrome representative. To clean up the auxiliary E register without disturbing the desired amplitudes on |x⟩, one must compute, for each prepared (x, y), the unique low-weight y that produces a given syndrome — i.e., a syndrome-decoding subroutine for the dual code C^⊥. For OPI, C^⊥ is a Reed-Solomon code admitting Berlekamp-Massey decoding in polynomial time, which is what makes DQI efficient there. For other codes — and therefore other max-LINSAT instances — the algorithm is only as efficient as the available classical decoder.

Performance and the semicircle law (Sec. 5). Optimizing the weights {w_k} for fixed (m, ℓ, p, r) yields an analytic asymptotic constraint-satisfaction rate (the semicircle law). The OPI specialization with p large, n ≈ p/10, r ≈ p/2 gives ⟨s⟩/m ≈ 0.7179 for DQI vs 0.55 for Prange — and crucially, matching DQI's quality with a classical algorithm appears to require superpolynomial time. This is the strongest claim in the review: not just a polynomial constant-factor improvement, but evidence of a complexity-class separation on a structured problem where efficient classical decoding is available on the dual side but the primal optimization remains hard. The largest analytical gap Δ ≈ 0.21 occurs at n/p ≈ 0.293.

Caveats the authors flag (Sec. 7). (i) DQI's superpolynomial speedup is OPI-specific; for general max-LINSAT it inherits whatever classical decoder is available, which may not exist; (ii) for max-XORSAT, fast classical algorithms match or beat DQI — there is no quantum advantage; (iii) the cleanest provable separation is in query complexity, à la Yamakawa–Zhandry, which is a different complexity-theoretic claim than wall-clock improvement on a real problem. Reported empirical extensions: BMW industrial-LP applications (Sabater 2025); a quantum-chemistry max-cut application whose advantage was contested by Parekh et al.; Bu et al. (2025) noise analysis showing DQI quality degrades exponentially with a noise-weighted sparsity parameter under local depolarizing noise — the precise "noise-regime crossover" question Yuan analyzed in Y3.

Extensions worth knowing (Sec. 6). Multivariate OPI (mOPI) extends to polynomials Q(y₁,…,y_m) with p^m constraints — exponentially more constraints than univariate OPI, hinting at an even larger speedup if it can be made rigorous. HDQI (Schmidhuber–Poremba–Quek 2025) lifts DQI from diagonal to general Pauli Hamiltonians — the broader Hamiltonian-optimization regime that includes ground-state and Gibbs-state preparation, conceptually closer to Y5's Pauli-sparse Gibbs-state SDP framework. The HDQI symplectic code becomes a classical LDPC code for local Hamiltonians, enabling parallelizable classical decoding — Yuan should pay attention here as a potential interface between Y4-style structured quantum search and Y5-style Pauli-sparse Gibbs preparation.

Figures

Figures section omitted — the paper's source figures are .eps (no converter installed). Five figures appear in the paper: a workflow diagram contrasting classical vs DQI approaches to OPI; the OPI polynomial visualization; an approximate-nearest-codeword decoding diagram for RM(1,3); the seven-step DQI circuit diagram with W/E/S registers; and the semicircle-law performance comparison plot of DQI vs Prange's algorithm.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y3 (QAOA portfolio + quantum-advantage analysis) — strongest conclusion overlap. Both papers are about the central question "when does quantum optimization beat classical?" Y3 concluded that for DGMVP under thermal noise the answer is no but in the shot-noise regime it is yes. This DQI review is the strongest existing positive answer for a structured problem family (OPI). Yuan's next quantum-advantage piece needs to engage with DQI head-on, including the Bu et al. noise analysis that closely parallels Y3's own noise-regime crossover.
Y4 (Grover + ADMM cardinality-constrained). Both are structured-problem quantum-advantage proposals but use very different mechanisms — Y4 leverages amplitude amplification on a structured feasible set, DQI leverages QFT-coding-theory duality. Worth comparing in Y4-style follow-ups: how does a Grover-rotation count compare to a DQI circuit on a problem expressible in both frameworks?
Y5 (GW + Gibbs + Pauli sparsity) — non-trivial method overlap via HDQI. The HDQI extension reduces general Pauli-Hamiltonian optimization to classical LDPC decoding for local Hamiltonians, and prepares filter states ρ(H) = P²(H)/Tr[P²(H)] that for suitable P become Gibbs states. This is conceptually the same Pauli-sparse-Gibbs-state object Yuan exploits in Y5, approached from a different direction (decoding rather than dequantization). A direct comparison between HDQI Gibbs preparation and Y5's quantum-inspired SDP relaxations would be a publishable methods note.
Y1, Y2 (warm-started / quasi-binary QAOA). No method overlap — DQI is not a variational algorithm and does not use a QAOA-style ansatz. It is the alternative paradigm to QAOA for structured optimization.
Y6 (PBR/Heron foundations). No overlap.

Recommended action for Yuan

Read carefully and add to citation list for any quantum-optimization paper. This is the canonical 2026 reference for DQI; the review is self-contained and exactly the level of detail needed to discuss DQI in related-work or as a baseline.
Track the HDQI thread closely. Schmidhuber et al. 2025 (cited here as schmidhuber2025HDQI) and the broader-Hamiltonian extension (bu2026HDQI) are direct competitors / complements to Y5's Pauli-sparse Gibbs-state framework. A focused comparison piece — "HDQI vs quantum-inspired Pauli-sparse SDPs for structured Hamiltonian optimization" — could be high-impact, and Yuan is uniquely positioned to write it.
Email Tim Byrnes at NYU Shanghai. The review explicitly calls out as open questions: (a) what other optimization problems can be mapped into max-LINSAT/OPI form (cardinality-constrained binary optimization à la Y4 is a natural candidate); (b) whether DQI's noise-degradation crossover (Bu et al. 2025) maps onto the shot-noise vs thermal-noise picture of Y3. A short note proposing collaboration on (a) or (b) would not be premature.
Implement DQI as a baseline on at least one Y3-style portfolio instance. Even if portfolio doesn't fit max-LINSAT exactly, a small toy comparison would clarify whether the DQI vs QAOA-portfolio comparison is even meaningful at problem sizes Yuan studies, before committing to a larger benchmarking effort.