No exponential quantum advantage for decoded quantum interferometry with local quantum decoders

The paper in detail

DQI prepares a superposition over candidate solutions \(z\) with amplitude proportional to \(\Phi(Bz+x_0)\). It does so by creating a superposition of codewords of the code with parity-check matrix \(B^{\mathsf T}\), entangled with an error register, and then uncomputing the codeword. That uncomputation is a decoding problem: in the Fourier basis each qudit holds a codeword symbol subjected to a coherent error whose law is set by the amplitude function. With the product amplitude function \(\Phi_\beta=\prod_j\sqrt{p_\beta(x_j)}\), a successful decoder makes DQI sample from the Gibbs measure at inverse temperature \(\beta\), and for Max-XORSAT the satisfied fraction is \(s=\tfrac12+\tfrac12\tanh(\beta/2)\).

The question is the largest \(\beta\) at which DQI still works, first for decoders that estimate each symbol from its logarithmic-radius neighbourhood in the factor graph (local decoders, with arbitrary quantum measurements allowed there), then for any decoder. Equivalently, how high a satisfied fraction can DQI reach, and do classical local algorithms reach the same value?

The main insight is that each decoding threshold is a known phase transition of the primal Gibbs measure. On a tree, the overlap of BPQM's two possible message states and the bias of an ordinary belief-propagation message for the primal problem obey the same recursion with the two kinds of nodes exchanged, so local decoding fails exactly when distant variables carry information about the root: the reconstruction threshold \(\beta_d\). For the optimal decoder, block success equals the squared Bhattacharyya coefficient between right-hand sides generated from a planted assignment and uniformly random ones, so it succeeds exactly while these are indistinguishable, below the condensation threshold \(\beta_c\).

Converted to satisfied fractions, \(\beta_d\) for \((3,6)\) gives \(s_d\approx0.863\), and simulated annealing does better on every pair tested. The open question the paper leaves is whether an efficient nonlocal decoder can work between \(\beta_d\) and \(\beta_c\), which would be the only route to an advantage on these instances.

Transferable methods

1. BPQM overlaps follow the belief-propagation recursion

   To bound every local decoder, the authors need the optimal success probability on a tree. BPQM achieves it, and its messages are pure qubit states characterised by one overlap. The recursion for that overlap turns out to be belief propagation for the primal problem with the node roles swapped, which links decoding to reconstruction.

   A binary message is \(\ket{\psi_y(a)}=\sqrt{\tfrac{1+a}{2}}\ket0+(-1)^{y}\sqrt{\tfrac{1-a}{2}}\ket1\), with overlap \(a\) between \(y=0\) and \(y=1\); the channel gives \(a=\sigma_\beta=\tanh(\beta/2)\). At a symbol node, two messages combine losslessly into one with overlap \(ab\). At a check node, with probability \((1+ab)/2\) the outgoing overlap is \((a+b)/(1+ab)\), otherwise \((b-a)/(1-ab)\). The root is decoded by the Helstrom measurement with success \(\tfrac12\bigl(1+\sqrt{1-U_t^{2}}\bigr)\).

   Editorial remark: writing \(a=\tanh h_1\), \(b=\tanh h_2\), the check-node rule is \(\tanh(h_1\pm h_2)\), which is how belief propagation adds two log-likelihood ratios about one variable, while the symbol-node product \(ab\) is the belief-propagation rule at a parity check. So overlaps on the code's tree evolve like biases on the primal tree, and Corollary 4.11 bounds the error by \[1-P_t\ \ge\ \tfrac14\,\sigma_\beta^{2}\,\bar{\mathfrak m}_t^{\,2k},\] which stays positive exactly when reconstruction holds.

   How to reuse it

   For any quantum message-passing decoder on pure-state channels, look for the classical recursion its overlaps satisfy; a duality between the code's factor graph and the primal factor graph often turns a quantum decoding threshold into a known statistical-physics transition.

2. Three thresholds in one set of units

   The paper's numbers come from several sources (population dynamics, cavity results in spin units, density evolution), and the comparison with the Holevo limit depends on getting the conversions right. Writing them in terms of \(\beta\) makes each threshold a single number that can be checked independently.

   The bit-flip rate after measuring each symbol is \(\alpha^{\perp}=\tfrac12-\tfrac12\operatorname{sech}(\beta/2)\), and the Holevo limit for a code of rate \(1-k/D\) requires \(h\bigl(p_\beta(1)\bigr)\ge1-k/D\) with \(p_\beta(1)=1/(1+e^{\beta})\). For rate 1/2 this gives \(p_\beta(1)=0.110\) and \(\beta_H=2.0905\), the value in Table 7 for both \((3,6)\) and \((6,12)\).

   Editorial checks: \(\beta_d=1.8388\) gives \(\alpha^{\perp}=0.1559\) (Table 5: 0.1560) and \(s_d=0.8628\); \(\rho_c=0.1748\) gives \(\beta_c=1.990\); the Holevo error rate is \(\rho_H=0.187>\rho_c\). Unambiguous discrimination followed by belief propagation is erasure decoding of a \((3,6)\) LDPC code, whose threshold \(0.4294\) gives \(\beta=2\,\mathrm{atanh}(0.4294)=0.918\), as in Table 7. Halving \(\beta_d\) gives 0.919, the units of Piveteau et al., whose reported BPQM threshold is 0.920.

   How to reuse it

   When a quantum algorithm's success reduces to decoding at an inverse temperature, express every competing threshold (channel capacity, Holevo, statistical-physics transitions, classical algorithms) in that one parameter before comparing; disagreements in units are a common source of apparent advantages.

Source: Sections 2.1, 3.2–3.3, 4.6; Tables 5, 7–9. Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. The reconstruction threshold is also where the cavity method predicts local Markov chains stop mixing quickly. If that prediction holds, DQI with local decoders gives no exponential speedup for Gibbs sampling and no advantage in approximate optimisation with symmetric amplitude functions; in the authors' simulations simulated annealing beats the local-decoder bound on every degree pair tested. A quantum advantage on these instances would need an efficient nonlocal decoder working between \(\beta_d\) and \(\beta_c\), and the paper shows that implementing the optimal decoder coherently there is equivalent to preparing the Gibbs states themselves.

Limitations. The no-advantage conclusion for sampling rests on Conjecture 6.7, the cavity-method prediction for local Markov chains, which is supported numerically but not proved. Approximation bounds assume symmetric, offset-independent amplitude functions and reliable block decoding; for the block amplitude function of Shutty et al. the bound is proved on four degree pairs only. Exact-optimisation results concern ideal target states. The central correspondence was obtained independently and simultaneously by Jordan, Nguyen and Zhou. The authors state that the BPQM–reconstruction link was first pointed out by GPT-6 Sol, and that GPT-6.1 Sol and Claude Opus 5.5 developed much of the programme and the simulations, with all proofs checked by the authors.

Description based on the PDF of v1 (no HTML version available), read 2026-11-10: Sections 1 and 2.1, Sections 3.2–3.3 on the decoding problem and BPQM, Section 4.6, the AI methodology statement and Tables 5, 7, 8 and 9 of Appendix A. The proofs of Sections 5–7 and Appendices B–H were not checked. The unit conversions, the Holevo limit for rate 1/2, the erasure-decoder threshold and the conversions between Tables 5, 7 and 9 were recomputed.