betaFeedback

WorksPhysics and Astronomy

Regev's Reduction Reaches Reconstruction

Abstract

Regev's reduction uses a quantum Fourier transform to carry out reductions between various problems related to lattices and codes. We apply it to the problem of sampling from Gibbs distributions of certain classical spin glass Hamiltonians, which can equivalently be thought of as cost functions for average-case instances of an optimization problem called DD-regular max-kk-LINSAT. This problem becomes hard at low temperature. Here, we use a quantum decoding algorithm called Belief Propagation with Quantum Messages (BPQM) to solve the decoding problem arising from Regev's reduction. Our main contribution is a proof that the minimum temperature reachable using Regev+BPQM is exactly equal to the reconstruction threshold temperature for noisy channels transmitting signals on a tree network. This equality can be understood via Renes' duality between classical and quantum channels, which we use to show that quantum decoding is possible exactly when classical reconstruction on the dual problem is impossible. M{é}zard and Montanari identified this reconstruction temperature with a dynamical glass transition predicted by the one-step replica-symmetry breaking (1RSB) cavity equation. It is conjectured that local samplers such as Metropolis Monte Carlo and Glauber dynamics cannot equilibrate efficiently below this reconstruction temperature but may do so above it; our large numerical experiments show close agreement with this prediction across hundreds of different problem parameters. Therefore, our results rigorously show that Regev+BPQM reaches a temperature for which, to our knowledge, there is no matching classical guarantee, and brings Regev+BPQM to the conjectured limit of efficient Gibbs sampling by classical local dynamics.

Introduction

In the early 2000s it was shown by Regev, Aharonov, and Ta-Shma [7, 29, 6, 30] that the quantum Fourier transform can be used to efficiently realize reductions between various difficult computational problems regarding high dimensional lattices. However, at the time, these reductions did not lead to any quantum algorithms achieving advantage. Recently, a quantum algorithm called Decoded Quantum Interferometry (DQI) [14] was introduced which in polynomial time finds approximate solutions to a problem called Optimal Polynomial Intersection. No polynomial time classical algorithms are currently known that can find these approximate optima. DQI is closely related to Regev’s reduction. In fact, as later shown in [SMR+26], when applied to the same problems using the same decoders, Regev’s reduction efficiently achieves the same asymptotic approximate optima as DQI, although DQI outperforms at finite instance sizes. The key new element in [14] to achieving quantum advantage was considering optimization problems with algebraic structure and using decoders that exploited that algebraic structure.

It was also proposed in [14] to consider optimization problems with sparsity structure, such as DD-regular max-kk-XORSAT and its larger-alphabet generalization to DD-regular max-kk-LINSAT. Via the quantum Fourier transform, these are reduced to problems of decoding Low-Density Parity-Check (LDPC) codes. The low density (i.e., sparsity) of the parity check matrices makes the decoding problem much easier. Known classical algorithms such as belief propagation can efficiently decode LDPC codes of blocklength mm even when a (sufficiently small) constant fraction of the bits have been corrupted by bit flips. In contrast, for general dense parity check matrices, no polynomial time classical decoding algorithm is known beyond logarithmically many bit flips. Unfortunately, sparsity also makes the original optimization problem easier. Using classical belief propagation as the decoding algorithm in DQI appears insufficient to achieve quantum advantage on DD-regular max-kk-LINSAT over simulated annealing.

In this manuscript, we analyze the performance of Regev’s reduction when combined with an intrinsically quantum decoding method called Belief Propagation with Quantum Messages (BPQM) introduced in [31] and further developed in [28, 8, 21]. In [27] this combination was used to prepare Gibbs states of quantum Hamiltonians, including for dilute Ising spin glasses. Here, we apply Regev+BPQM to a classical optimization problem called average-case DD-regular max-kk-LINSAT. An instance of DD-regular max-kk-LINSAT consists of nn variables from Fp\mathbb{F}_p, contained in mm constraints. For a given assignment x∈Fpn\mathbf{x} \in\mathbb{F}_p^n to the variables we can assign a corresponding energy E(x)E(\mathbf{x}), equal to the number of violated constraints. Given an inverse temperature β≥0\beta\ge0 this defines a Gibbs distribution

Pr⁡β(x)=1Ze−βE(x)whereZ=∑x∈Fpne−βE(x).(1)\Pr_\beta(\mathbf{x}) = \frac{1}{Z}e^{-\beta E(\mathbf{x})} \quad\text{where} \quad Z = \sum_{\mathbf{x}\in\mathbb{F}_p^n} e^{-\beta E(\mathbf{x})}. \tag*{(1)}

Here, we use Regev’s reduction together with BPQM to prepare the state

∣ψβ⟩=∑x∈FpnPr⁡β(x)∣x⟩.(2)\lvert\psi_\beta\rangle= \sum_{\mathbf{x}\in\mathbb{F}_p^n} \sqrt{\Pr_\beta(\mathbf{x})}\lvert\mathbf{x}\rangle. \tag*{(2)}

That is, we use it to achieve coherent Gibbs sampling. For the random regular ensemble defined in Definition 2, our algorithm (Corollary 3) prepares this state with trace distance ε\varepsilon tending to zero with high probability as n→∞n \to\infty, for each fixed β\beta strictly below the decoding threshold.

Measuring the state ∣ψβ⟩\lvert\psi_\beta\rangle in the computational basis yields classical Gibbs sampling (to within ε\varepsilon total variation distance) at inverse temperature β\beta. At low temperature the expected energy ⟨E⟩β\langle E\rangle_\beta of the sampled symbol strings is low, and hence the Gibbs sampler can be used as an optimization algorithm. We remark that coherent Gibbs sampling at inverse temperature β\beta is a more powerful primitive than classical Gibbs sampling at inverse temperature β\beta [7, 20, 17], which in turn is a more powerful primitive than finding an individual solution at energy ⟨E⟩β\langle E\rangle_\beta [15].

As our main result, we prove that the BPQM tree-decoding threshold is exactly equal to the reconstruction threshold for a noisy channel on the dual tree network (Theorem 1). The latter is known to correspond to the dynamical glass transition temperature βdyn\beta_{\mathrm{dyn}} in the associated statistical physics model of random max-kk-LINSAT Hamiltonians [19], beyond which Gibbs sampling is conjectured to be difficult (see e.g., [18, 11, 25 EM5?25]). This equality also has a nice information-theoretic interpretation: Renes’ channel duality relates the quantum messages used for decoding to classical noisy observations used for reconstructing the root symbol. In our setting, the quantum messages become perfectly distinguishable precisely when the dual classical observations lose all information about the root.

Our result guarantees coherent Gibbs sampling by Regev+BPQM all fixed β<βdyn\beta< \beta_{\mathrm{dyn}}, reaching the conjectured limit for classical local dynamics [25]. Although it is a folklore belief that Glauber dynamics and other local Markov chains can reach this limit, we are not aware of a matching classical sampling theorem for the general sparse max-LINSAT ensembles considered here. For example, it was only very recently shown that simulated annealing samples up to criticality for the Sherrington-Kirkpatrick model (i.e., random weighted max-2-XORSAT on dense graphs) [12 DHMR26]. In the more general k≥3k \ge3 case, however, existing fast-mixing guarantees for Glauber dynamics only apply at inverse temperatures far smaller than βdyn\beta_{\mathrm{dyn}} of the related dense models [4, 1, 10]. Therefore, our result constitutes the first rigorous proof of a polynomial-time algorithm to produce (coherent) Gibbs samples for all β∈[0,βdyn)\beta\in[0,\beta_{\mathrm{dyn}}) for these broad families of spin glass Hamiltonians.

Summary of Results

We begin by giving a formal definition of the max-LINSAT problem, which follows [14]:

Definition 1. Let Fp\mathbb{F}_p be a finite field and let B∈Fpm×nB \in\mathbb{F}_p^{m \times n}. For each i=1,…,mi = 1,\ldots,m let Fi⊂FpF_i \subset\mathbb{F}_p be an arbitrary subset of Fp\mathbb{F}_p which yields a corresponding constraint ∑j=1nBijxj∈Fi\sum_{j=1}^{n} B_{ij}x_j \in F_i. Given BB and F=(F1,…,Fm)F = (F_1,\ldots,F_m), the max-LINSAT problem is to find x∈Fpnx \in\mathbb{F}_p^n satisfying as many as possible of these mm constraints.

For simplicity, we restrict pp to be prime in this work. In the case of p=2p = 2 and ∣Fi∣=1|F_i| = 1, one recovers max-XORSAT. An instance of max-LINSAT corresponds to the energy function E:Fpn→ZE:\mathbb{F}_p^n \to\mathbb{Z} given by

E(x)=∣{i:∑j=1nBijxj∉Fi}∣.(3)E(\mathbf{x}) = \left|\left\{i:\sum_{j=1}^{n}B_{ij}x_j \notin F_i\right\}\right|. \tag*{(3)}

This in turn defines a classical Gibbs distribution via (1) and a coherent Gibbs sampling problem via (2). At p=2p = 2, the energy function (3) is equivalent to the classical Ising model.

The special case of max-LINSAT where each constraint contains exactly kk variables is called max-kk-LINSAT. That is, in max-kk-LINSAT each row of the matrix BB contains exactly kk nonzero coefficients. If each variable is contained in exactly DD constraints, i.e., each column of BB contains exactly DD nonzero coefficients, then the instance is said to be DD-regular. When k=2k = 2 and Fi=Fp∖{0}F_i = \mathbb{F}_p \setminus\{0\}, the problem is equivalent to max-pp-cut or the antiferromagnetic Potts model.

Our Ensemble of Instances. To fully specify an instance of max-LINSAT we need to make three choices: which entries of BB are nonzero, what values in Fp×\mathbb{F}_p^\times these nonzero entries take, and what subsets of Fp\mathbb{F}_p we take as our targets F1,…,FmF_1,\ldots,F_m. We address these in turn.

To generate an instance of DD-regular max-kk-LINSAT we start by choosing a matrix Bˉ\bar{B} uniformly at random from all {0,1}\{0,1\}-valued m×nm \times n matrices with exactly DD ones in each column and kk ones in each row. The ones represent the locations of nonzero entries in our final matrix B∈Fpm×nB \in\mathbb{F}_p^{m \times n}. We can visualize Bˉ\bar{B} by a corresponding bipartite graph with one part of mm vertices that correspond to the constraints in our max-LINSAT instance and a second part of nn vertices that correspond to the variables. A constraint vertex ii in the first part is connected by an edge to a variable vertex jj in the second part if and only if Bˉij=1\bar{B}_{ij}=1, i.e., constraint ii contains variable jj. Following the terminology from coding theory, we refer to this as the Tanner graph. Given Bˉ\bar{B}, we next construct BB by filling in each nonzero entry with a choice from Fp×\mathbb{F}_p^{\times}, followed by choosing target sets F1,…,FmF_1,\ldots,F_m.

Definition 2 (Random regular max-LINSAT). Fix a prime pp, integers 3≤k<D3 \leq k < D, a nonempty proper subset S⊊FpS \subsetneq\mathbb{F}_p, and an exchangeable probability law Λ\Lambda on (Fp×)D(\mathbb{F}_p^{\times})^D. Hold these parameters fixed as n→∞n \to\infty along values for which m=nD/km=nD/k is an integer. Then a max-LINSAT instance (B,F)(B,\mathbf{F}) is drawn from the random regular ensemble Greg(n,k,D,p,S,Λ)\mathsf{G}_{\mathrm{reg}}(n,k,D,p,S,\Lambda) as follows. First choose Bˉ∈{0,1}m×n\bar{B}\in\{0,1\}^{m\times n} as above; then BB is constructed by taking Bˉ\bar{B} and filling the DD nonzero entries in each column one tuple drawn from the law Λ\Lambda. To obtain F=(Fi)i=1m\mathbf{F}=(F_i)_{i=1}^m, we first choose offsets τ1,…,τm\tau_1,\ldots,\tau_m independently and uniformly at random from Fp\mathbb{F}_p, and set Fi=τi+SF_i=\tau_i+S.

Requiring Λ\Lambda to be exchangeable, which means the probability law is invariant under permuting the DD variables, is a proof convenience. Examples of exchangeable Λ\Lambda include:

  1. Λiid\Lambda_{\mathrm{iid}}: Choose each coefficient independently and uniformly at random from Fp×\mathbb{F}_p^{\times}.

  1. Λperm\Lambda_{\mathrm{perm}}: Fix a primitive element g∈Fp×g\in\mathbb{F}_p^{\times}, and choose the coefficients to be a uniformly random permutation of (1,g,g2,…,gD−1)(1,g,g^2,\ldots,g^{D-1}).

In particular, the choice Λiid\Lambda_{\mathrm{iid}} gives the coefficient law in [22 Theorem 30]; our Proposition 2 extends its argument to any general exchangeable law and conditions the graph to be simple. Separately, the uniform offsets supply the random shifts required by the coherent-state error bound [SMR+26, Lemma 4].

Reconstruction and the Main Result. The neighborhood of a uniformly chosen vertex in a random regular Tanner graph is a tree at any fixed radius, with probability tending to one as n→∞n\to\infty. The associated infinite tree has variable degree DD and constraint degree kk. Its free-boundary Gibbs distribution can be generated by a broadcast: choose the root symbol uniformly from Fp\mathbb{F}_p, then at each constraint jointly generate its k−1k-1 child symbols from the conditional Gibbs distribution given the parent. Satisfying assignments to that constraint receive weight 11, and violating assignments receive weight e−βe^{-\beta}. This procedure is specified in § 7.

The reconstruction problem asks an observer who knows the tree, coefficients, and target offsets to infer the root from the symbols at generation ℓ\ell, even as ℓ→∞\ell\to\infty. At high temperature, this distant boundary loses all information about the root. At sufficiently low temperature, information may survive. Writing X0X_0 for the root, X∂TℓX_{\partial T_\ell} for the boundary, and T\mathcal{T} for the known tree data, we define the reconstruction threshold in inverse temperature as

βdyn:=inf⁡{β>0:lim⁡ℓ→∞I(X0;X∂Tℓ∣T)>0}.(4)\beta_{\mathrm{dyn}} := \inf\left\{\beta>0:\lim_{\ell\to\infty} I(X_0;X_{\partial T_\ell}\mid\mathcal{T})>0\right\}. \tag*{(4)}

The notation βdyn\beta_{\mathrm{dyn}} reflects its relation to the dynamical transition in spin glass theory, as shown in [19]. This equivalence is made explicit by examining the distribution of the root’s posterior probabilities as the observed boundary moves farther away. If these probabilities approach the uniform distribution, the boundary loses all information about the root; if they retain a nonzero bias, reconstruction remains possible. Mézard and Montanari show that the recursive equation tracking the local posterior probabilities is also the m=1m = 1 one-step replica-symmetry-breaking (1RSB) equation used to locate the dynamical glass transition [19 Proposition 1 and Section 7]. A nontrivial solution to the equation describes persistent information on a distant boundary on the tree. On finite random graphs, this translates to a physical picture where the Gibbs measure is decomposed into regions between which local dynamics move slowly.

On the decoding side, Regev’s reduction associates the instance matrix BB with the LDPC code C⊥=ker⁡BTC^{\perp} = \ker B^{T}. Its symbols have degree kk and its checks have degree DD, interchanging the two roles in the reconstruction graph. We review Regev’s reduction for Gibbs sampling in § 3. To solve the associated decoding problem, BPQM, described in § 4, estimates a code symbol by combining quantum messages in a tree neighborhood of the symbol. The performance of BPQM decoding is classically analyzed by the framework of quantum density evolution (§ 5), which tracks the distributions of these messages and determines the limiting root-symbol error. We write βBPQM\beta_{\mathrm{BPQM}} for the inverse temperature at which this error ceases to vanish as the tree depth grows; its precise definition is given in (52). We note that this threshold is optimal for root-symbol decoding on tree Tanner graphs for the pure-state channels considered here, since BPQM minimizes the decoding error among all collective quantum measurements on the tree’s channel outputs [28, 22].

Our main result establishes a precise equality between βdyn\beta_{\mathrm{dyn}} and βBPQM\beta_{\mathrm{BPQM}}:

Theorem 1 (Regev+BPQM reaches reconstruction, informal). Fix any choice of (k,D,p,S,Λ)(k, D, p, S, \Lambda) as in Definition 2. Then the reconstruction threshold on the associated tree equals the BPQM decoding threshold on the dual tree:

βBPQM(k,D,p,S,Λ)=βdyn(k,D,p,S,Λ).(5)\beta_{\mathrm{BPQM}}(k,D,p,S,\Lambda) = \beta_{\mathrm{dyn}}(k,D,p,S,\Lambda). \tag*{(5)}

For every β∈[0,βdyn)\beta\in[0, \beta_{\mathrm{dyn}}), there is a polynomial-time quantum algorithm based on Regev’s reduction with BPQM that prepares the coherent Gibbs state (2) of an instance drawn from Greg(n,k,D,p,S,Λ)G_{\mathrm{reg}}(n,k,D,p,S,\Lambda), with vanishing trace-distance error with high probability as n→∞n \to\infty.

The main novelty of Theorem 1 is the equality (5), which identifies BPQM success exactly with non-reconstruction on the tree. For the finite-graph sampling conclusion from decoding (Corollary 3, § 6), our proof is a straightforward adaptation of recent works [22 SMR+26]. In particular, [22 Theorem 30] proves vanishing block error for BPQM with erasure recovery on random regular LDPC codes throughout the tree-decoding success region. Our adapted Proposition 2 makes two modest extensions: it allows any exchangeable coefficient law Λ\Lambda, with independent tuples at distinct checks, and conditions the Tanner graph to have no parallel edges. [SMR+26, Lemma 4] supplies the other ingredient: an average fidelity bound that converts decoding error into coherent-state preparation error in Regev’s reduction. The independent uniform offsets τj\tau_j in our ensemble provide the random shifts required by their bound.

Our proof of the threshold equality (5) can be understood through the lens of Renes’ channel duality [32] (see § 8). A BPQM message is a channel that maps a code symbol to a quantum state. By [32], this quantum message channel is dual to a classical channel that outputs a probability distribution. We then show that each round of BPQM message-combining operation in the dual classical channel is mathematically equivalent to a step in the reconstruction recursion on local posterior distributions. Renes’ entropic uncertainty relation then tells us that the quantum decoding has vanishing error (maximal information) in the infinite tree precisely when the classical dual reconstruction problem has vanishing information, which implies that the BPQM decoding threshold is equal to the reconstruction threshold.

Numerical Experiments. In the spin glass literature it has been conjectured that the Metropolis and Glauber Markov chains have slow mixing below the reconstruction threshold temperature (e.g., (KT87, MS06)). Hence, one expects that the energy efficiently reachable in practice by simulated annealing and Glauber methods may coincide, at least approximately, with the expected energy in the Gibbs distribution at the tree reconstruction threshold temperature. Prior computational experiments have provided evidence in support of this in several regimes (e.g., (MRT04, MS06, KMRT+07)). In § 9 we report our own computer experiments with simulated annealing specifically on our ensemble of DD-regular max-kk-LINSAT over an alphabet of size pp with Λ=Λperm\Lambda= \Lambda_{\mathrm{perm}} and target set Sr={0,…,r−1}S_r = \{0,\ldots,r - 1\}. We perform our experiments on random instances with n=6720n = 6720 variables, across an exhaustive grid of ensemble parameters for all 3≤k<D≤83 \le k < D \le8 with pp ranging across all primes up to 13 and 1≤r<p1 \le r < p. Among its 525 settings, density evolution detects finite βdyn\beta_{\mathrm{dyn}} thresholds at 252, which we subsequently use for simulated annealing experiments. On this region of the four-dimensional parameter space defined by (k,D,p,r)(k,D,p,r) we find that the energy reached by simulated annealing (normalized to lie between 0 and 1 as a satisfaction fraction) differs from this prediction by an average of 0.58 percentage points and at most 2.8 percentage points. This holds across short anneals (1.44×1051.44 \times10^5 sweeps) and long anneals (1.44×1071.44 \times10^7 sweeps). Thus, although such experiments cannot definitively prove or disprove the claim, we do find that this theory is remarkably predictive of practical performance in our simulated annealing experiments.

Outlook. Our work leaves open several future directions:

  • Can one rigorously prove that classical Glauber dynamics sample in polynomial time at all inverse temperatures below the reconstruction threshold (β<βdyn\beta< \beta_{\mathrm{dyn}}) for all max-LINSAT ensembles? This would give a matching classical polynomial-time sampling guarantee below βdyn\beta_{\mathrm{dyn}}.

  • Our quantum algorithm prepares a coherent Gibbs state, which is a more powerful primitive than classical Gibbs samples. In particular, coherent Gibbs sampling has led to several quadratic quantum speedups in optimization and estimating partition functions [20, 33, 35, 17 AHN+22]. Our algorithm might lead to similar speedups.

  • Can one Gibbs sample beyond the reconstruction threshold for these random max-LINSAT problems? The recent work [36] gave such classical and quantum algorithms in certain regimes of large (k,D)(k,D) for the special case of max-XORSAT, but those algorithms underperform compared to Regev+BPQM for the small (k,D)(k,D) regime we consider here. A quantum algorithm that Gibbs samples at β>βdyn\beta> \beta_{\mathrm{dyn}} over wider regimes of (k,D,p,S,Λ)(k,D,p,S,\Lambda) could lead to a quantum advantage in sampling and optimization for unstructured spin glass problems.

Concurrent Work. While we were preparing this manuscript, we learned that our main result, in particular the correspondence between Regev+BPQM and the reconstruction threshold, was independently and simultaneously obtained by the Global Technology Applied Research team at JPMorganChase [2].

Regev's Reduction

We now briefly review Regev’s reduction from a point of view suited to present purposes.

A matrix B∈Fpm×nB \in\mathbb{F}_p^{m \times n} defines two codes:

C={Bx:x∈Fpn}andC⊥={d∈Fpm:BTd=0}.(6)C = \{Bx : x \in\mathbb{F}_p^n\} \quad\text{and} \quad C^\perp= \{d \in\mathbb{F}_p^m : B^{\mathsf{T}}d = 0\}. \tag*{(6)}

Their normalized code states are

∣C⟩=1∣C∣∑c∈C∣c⟩,∣C⊥⟩=1∣C⊥∣∑d∈C⊥∣d⟩.(7)|C\rangle= \frac{1}{\sqrt{|C|}}\sum_{c\in C}|c\rangle,\qquad|C^\perp\rangle= \frac{1}{\sqrt{|C^\perp|}}\sum_{d\in C^\perp}|d\rangle. \tag*{(7)}

It is easy to verify that QFT⁡∣C⟩=∣C⊥⟩\operatorname{QFT}|C\rangle= |C^\perp\rangle and QFT⁡†∣C⟩=∣C⊥⟩\operatorname{QFT}^{\dagger}|C\rangle= |C^\perp\rangle, where QFT denotes the unitary Fourier transform over Fpm\mathbb{F}_p^m.

Now suppose that, for an envelope function P:Fpm→CP:\mathbb{F}_p^m \to\mathbb{C}, we wish to construct the state

∣ψ⟩=1ZC(P)∑c∈CP(c)∣c⟩,(8)|\psi\rangle= \frac{1}{\sqrt{Z_C(P)}}\sum_{c\in C}P(c)|c\rangle, \tag*{(8)}

where

ZC(P)=∑c∈C∣P(c)∣2.(9)Z_C(P)=\sum_{c\in C}|P(c)|^2. \tag*{(9)}

The Fourier convolution theorem gives

∣ψ~⟩:=QFT⁡∣ψ⟩=1∣C⊥∣ZC(P)∑d∈C⊥∑e∈FpmP~(e)∣d+e⟩,(10)|\widetilde{\psi}\rangle:= \operatorname{QFT}|\psi\rangle= \frac{1}{|C^\perp|\sqrt{Z_C(P)}}\sum_{d\in C^\perp}\sum_{e\in\mathbb{F}_p^m}\widetilde{P}(e)|d+e\rangle, \tag*{(10)}

where

P~(e)=1pm/2∑y∈Fpmexp⁡(2πi⟨e,y⟩p)P(y)(11)\widetilde{P}(e)=\frac{1}{p^{m/2}}\sum_{y\in\mathbb{F}_p^m}\exp\left(\frac{2\pi i\langle e,y\rangle}{p}\right)P(y) \tag*{(11)}

is the unitary Fourier transform of PP. The ideal form of Regev’s reduction proceeds as follows; § 6 gives the agreement test and error bound for an approximate decoder.

  1. Prepare

(1∣C⊥∣∑d∈C⊥∣d⟩)⊗(1∥P∥2∑e∈FpmP~(e)∣e⟩),(12)\left(\frac{1}{\sqrt{|C^\perp|}}\sum_{d\in C^\perp}|d\rangle\right)\otimes\left(\frac{1}{\|P\|_2}\sum_{e\in\mathbb{F}_p^m}\widetilde{P}(e)|e\rangle\right), \tag*{(12)}

where ∥P∥22=∑y∈Fpm∣P(y)∣2\|P\|_2^2=\sum_{y\in\mathbb{F}_p^m}|P(y)|^2. The first register is efficiently preparable for any linear code C⊥C^\perp, while the second is normalized by Parseval’s identity. For P=PβP=P_\beta, its amplitudes factorize over the mm coordinates, so it is a product state and hence easy to prepare.

  1. Reversibly add the content of the first register to the content of the second register.

⟶1∣C⊥∣∥P∥2∑d∈C⊥∑e∈FpmP~(e)∣d+e⟩.(13)\longrightarrow\frac{1}{\sqrt{|C^\perp|}\|P\|_2}\sum_{d\in C^\perp}\sum_{e\in\mathbb{F}_p^m}\widetilde{P}(e)|d+e\rangle. \tag*{(13)}
  1. From the content d+ed+e of the second register, coherently infer the content dd of the first register. This is the quantum decoding problem: given the state

1∥P∥2∑e∈FpmP~(e)∣d+e⟩,(14)\frac{1}{\|P\|_2}\sum_{e\in\mathbb{F}_p^m}\widetilde{P}(e)|d+e\rangle, \tag*{(14)}

which we interpret as a codeword d∈C⊥\mathbf{d} \in C^\perp corrupted with a coherent superposition of errors e\mathbf{e}, infer d\mathbf{d}. The aim is to erase the first register and uncompute the decoder’s work registers. The normalized target of this step is

→∣0⟩⊗1∣C⊥∣ZC(P~)∑d∈C⊥∑e∈FpmP~(e)∣d+e⟩=∣0⟩⊗∣ψ~⟩.(15)\to\lvert0\rangle\otimes\frac{1}{\lvert C^\perp\rvert\sqrt{Z_C(\widetilde{P})}} \sum_{\mathbf{d}\in C^\perp} \sum_{\mathbf{e}\in\mathbb{F}_p^m} \widetilde{P}(\mathbf{e})\lvert\mathbf{d}+\mathbf{e}\rangle= \lvert0\rangle\otimes\lvert\widetilde{\psi}\rangle. \tag*{(15)}
  1. Discard the ∣0⟩\lvert0\rangle register and perform an inverse quantum Fourier transform. By (8) and (10) this yields the desired final state.

→1ZC(P)∑c∈CP(c)∣c⟩=∣ψ⟩.(16)\to\frac{1}{\sqrt{Z_C(P)}} \sum_{\mathbf{c}\in C} P(\mathbf{c})\lvert\mathbf{c}\rangle= \lvert\psi\rangle. \tag*{(16)}

We next observe how this applies to coherent Gibbs sampling. Every c∈C\mathbf{c}\in C has exactly ∣ker⁡B∣\lvert\ker B\rvert preimages, all with the same energy. Consequently, the normalized code state corresponding to (2) is

∣Cβ⟩=1∣ker⁡B∣∑x∈FpnPr⁡β(x)∣Bx⟩.(17)\lvert C_\beta\rangle= \frac{1}{\sqrt{\lvert\ker B\rvert}} \sum_{\mathbf{x}\in\mathbb{F}_p^n} \sqrt{\Pr_\beta(\mathbf{x})}\lvert B\mathbf{x}\rangle. \tag*{(17)}

Gaussian elimination gives a particular preimage of each codeword and a basis for ker⁡B\ker B. Preparing a uniform superposition over that kernel implements the isometry

∣c⟩∣0⟩⟼∣0⟩1∣ker⁡B∣∑x:Bx=c∣x⟩,c∈C.(18)\lvert\mathbf{c}\rangle\lvert0\rangle\longmapsto\lvert0\rangle\frac{1}{\sqrt{\lvert\ker B\rvert}} \sum_{\mathbf{x}:B\mathbf{x}=\mathbf{c}}\lvert\mathbf{x}\rangle,\qquad\mathbf{c}\in C. \tag*{(18)}

A reversible linear-algebra circuit extends this map to the full registers. Applying it to (17) gives ∣0⟩∣ψβ⟩\lvert0\rangle\lvert\psi_\beta\rangle. Thus no full-column-rank assumption is needed; when ker⁡B={0}\ker B=\{0\}, the map reduces to the inverse encoding c↦x\mathbf{c}\mapsto\mathbf{x}.

By (1) and (6) we can rewrite (17) as

∣Cβ⟩=∑c∈CPβ(c)∣c⟩,(19)\lvert C_\beta\rangle= \sum_{\mathbf{c}\in C} P_\beta(\mathbf{c})\lvert\mathbf{c}\rangle, \tag*{(19)}

where, for y∈Fpm\mathbf{y}\in\mathbb{F}_p^m and a∈Fpa\in\mathbb{F}_p,

Pβ(y)=∣ker⁡B∣Z∏j=1mPβ(j)(yj),(20)P_\beta(\mathbf{y})=\sqrt{\frac{\lvert\ker B\rvert}{Z}}\prod_{j=1}^{m}P_\beta^{(j)}(y_j), \tag*{(20)}
Pβ(j)(a)={1,a∈Fj,e−β/2,a∉Fj.(21)P_\beta^{(j)}(a)= \begin{cases} 1, & a\in F_j,\\ e^{-\beta/2}, & a\notin F_j. \end{cases} \tag*{(21)}

Counting the ∣ker⁡B∣\lvert\ker B\rvert preimages of each codeword gives ZC(Pβ)=1Z_C(P_\beta)=1. Thus (10) specializes to

∣C~β⟩:=QFT⁡∣Cβ⟩=1∣C⊥∣∑d∈C⊥∑e∈FpmP~β(e)∣d+e⟩,(22)\lvert\widetilde{C}_\beta\rangle:= \operatorname{QFT}\lvert C_\beta\rangle= \frac{1}{\lvert C^\perp\rvert}\sum_{\mathbf{d}\in C^\perp}\sum_{\mathbf{e}\in\mathbb{F}_p^m}\widetilde{P}_\beta(\mathbf{e})\lvert\mathbf{d}+\mathbf{e}\rangle, \tag*{(22)}

where P~β\widetilde{P}_\beta is the unitary Fourier transform of PβP_\beta. Since (20) factorizes, applying (11) gets

P~β(e)=∣ker⁡B∣Z∏j=1mP~β(j)(ej).(23)\widetilde{P}_\beta(\mathbf{e})=\sqrt{\frac{\lvert\ker B\rvert}{Z}}\prod_{j=1}^{m}\widetilde{P}_\beta^{(j)}(e_j). \tag*{(23)}

where the individual components (21) are Fourier transformed to yield

P~β(j)(ej)=1p{∣Fj∣+(p−∣Fj∣)e−β/2,ej=0,(1−e−β/2)∑a∈Fjexp⁡(2πiejap),ej≠0.(24)\widetilde{P}_{\beta}^{(j)}(e_j)=\frac{1}{\sqrt{p}}\begin{cases} |F_j|+(p-|F_j|)e^{-\beta/2}, & e_j=0,\\ (1-e^{-\beta/2})\sum_{a\in F_j}\exp\left(\frac{2\pi i e_j a}{p}\right), & e_j\ne0. \end{cases} \tag*{(24)}

The amplitudes in (24) define the error model for the quantum decoding problem that we must solve, where the jj-th codeword symbol is sent through the noise channel

∣dj⟩⟶1∥P~β(j)∥2∑eP~β(j)(e)∣dj+e⟩.|d_j\rangle\longrightarrow\frac{1}{\left\|\widetilde{P}_{\beta}^{(j)}\right\|_2}\sum_{e}\widetilde{P}_{\beta}^{(j)}(e)|d_j+e\rangle.

In the next section we recount a method for solving this problem called BPQM that was originally developed with quantum communication in mind. Here we find a new application for it in the context of quantum algorithms.

Belief Propagation with Quantum Messages

We solve the quantum decoding problem in step 3 of Regev’s reduction using Belief Propagation with Quantum Messages (BPQM) [31], in particular its extension to prime alphabets in [21]. The quantum decoding problem is to infer the codeword d∈C⊥\mathbf{d}\in C^\perp from the quantum state in (14)

∑e∈FpmP~(e)∣d+e⟩.(25)\sum_{e\in\mathbb{F}_p^m}\widetilde{P}(e)|\mathbf{d}+e\rangle. \tag*{(25)}

BPQM recovers d\mathbf{d} by estimating each code symbol. It estimates a code symbol dd by combining messages along a tree rooted at that symbol [31, 28]. Each message consists of a quantum system and a classical description of its possible states. There are two combining operations below. Given two input messages, a combining operation produces a single output message. Repeatedly applying the combining operations along the tree produces a single message at the root. A final measurement of the root message estimates the root symbol. Below we recall how BPQM works on a tree; in § 6 we show how to extend it to our code ensemble.

Messages. We use the pp-ary pure-state channel formulation of [21], Sec. II-C, Eq. (1), with normalized eigenvalues μa=λa/p\mu_a=\lambda_a/p and a fixed change from their Fourier basis to the computational basis. Let ω=e2πi/p\omega=e^{2\pi i/p}. A message about a symbol d∈Fpd\in\mathbb{F}_p has a classical component specified by a probability vector μ=(μa)a∈Fp\boldsymbol{\mu}=(\mu_a)_{a\in\mathbb{F}_p} and a quantum component in the state

∣ϕd(μ)⟩=∑a∈Fpμa ω−ad∣a⟩.(26)|\phi_d(\boldsymbol{\mu})\rangle=\sum_{a\in\mathbb{F}_p}\sqrt{\mu_a}\,\omega^{-ad}|a\rangle. \tag*{(26)}

The Gram matrix of these states has Fourier eigenvalues pμap\mu_a [21 Lemmas 5–7]. The normalized eigenvalues μ\boldsymbol{\mu} specify the overlaps among the possible states; for example, uniform μ\boldsymbol{\mu} gives mutually orthogonal states and perfect distinguishability.

We now show how the quantum message (26) arises in Regev’s reduction. For fixed d\mathbf{d}, the received state in Regev’s reduction (22) is a product of the normalized single-symbol received states

∣vdj(j)⟩:=∑e∈FpP~β(j)(e)∥Pβ(j)∥2∣dj+e⟩.(27)\lvert v_{d_j}^{(j)}\rangle:= \sum_{e\in\mathbb{F}_p} \frac{\widetilde{P}_{\beta}^{(j)}(e)}{\lVert P_{\beta}^{(j)}\rVert_2} \lvert d_j+e\rangle. \tag*{(27)}

Define the probability vector μj\boldsymbol{\mu}_j by normalizing the squared amplitudes of Pβ(j)P_{\beta}^{(j)}. Using (21), we obtain

μj,a=∣Pβ(j)(a)∣2∑b∈Fp∣Pβ(j)(b)∣2=1∣Fj∣+(p−∣Fj∣)e−β{1,a∈Fj,e−β,a∉Fj.(28)\mu_{j,a}=\frac{\lvert P_{\beta}^{(j)}(a)\rvert^2}{\sum_{b\in\mathbb{F}_p}\lvert P_{\beta}^{(j)}(b)\rvert^2}=\frac{1}{\lvert F_j\rvert+(p-\lvert F_j\rvert)e^{-\beta}}\begin{cases}1, & a\in F_j,\\ e^{-\beta}, & a\notin F_j.\end{cases} \tag*{(28)}

Applying the inverse Fourier transform to the received state then gives the message state in (26) with d=djd=d_j and μ=μj\boldsymbol{\mu}=\boldsymbol{\mu}_j:

QFT⁡†∣vdj(j)⟩=∑a∈Fpμj,a ω−adj∣a⟩=∣ϕdj(μj)⟩.\operatorname{QFT}^{\dagger}\lvert v_{d_j}^{(j)}\rangle=\sum_{a\in\mathbb{F}_p}\sqrt{\mu_{j,a}}\,\omega^{-ad_j}\lvert a\rangle=\lvert\phi_{d_j}(\boldsymbol{\mu}_j)\rangle.

Equality rule. Suppose two incoming messages concern the same unknown symbol dd. The goal of the equality rule1 is to compress their two quantum systems into one qudit without losing any information about dd. This is possible because, conditioned on the classical messages μ\boldsymbol{\mu} and ν\boldsymbol{\nu}, the pp possible joint pure states {∣ϕd(μ)⟩⊗∣ϕd(ν)⟩}d∈Fp\{\lvert\phi_d(\boldsymbol{\mu})\rangle\otimes\lvert\phi_d(\boldsymbol{\nu})\rangle\}_{d\in\mathbb{F}_p} span a subspace of dimension at most pp inside the p2p^2-dimensional two-qudit space. A unitary can therefore put all dependence on dd into one qudit while leaving the other in a fixed state.

To see the compression explicitly, expand the product state and group terms by a=b+ca=b+c:

∣ϕd(μ)⟩⊗∣ϕd(ν)⟩=∑b,c∈Fpμbνc ω−(b+c)d∣b,c⟩=∑a∈Fpω−ad(∑b∈Fpμbνa−b∣b,a−b⟩)=∑a∈Fpω−ad∣ga⟩.\lvert\phi_d(\boldsymbol{\mu})\rangle\otimes\lvert\phi_d(\boldsymbol{\nu})\rangle=\sum_{b,c\in\mathbb{F}_p}\sqrt{\mu_b\nu_c}\,\omega^{-(b+c)d}\lvert b,c\rangle=\sum_{a\in\mathbb{F}_p}\omega^{-ad}\left(\sum_{b\in\mathbb{F}_p}\sqrt{\mu_b\nu_{a-b}}\lvert b,a-b\rangle\right)=\sum_{a\in\mathbb{F}_p}\omega^{-ad}\lvert g_a\rangle.

The vectors ∣ga⟩\lvert g_a\rangle are independent of dd and have disjoint computational-basis supports for distinct aa, so they are mutually orthogonal. Their squared norms give the circular-convolution update of [21 Lemma 13], expressed in normalized eigenvalues:

(μ∗ν)a=⟨ga∣ga⟩=∑b∈Fpμbνa−b.(29)(\boldsymbol{\mu} * \boldsymbol{\nu})_a=\langle g_a\vert g_a\rangle=\sum_{b\in\mathbb{F}_p}\mu_b\nu_{a-b}. \tag*{(29)}

We can therefore choose a unitary, depending only on μ\boldsymbol{\mu} and ν\boldsymbol{\nu}, that maps each normalized vector to ∣a⟩⊗∣0⟩\lvert a\rangle\otimes\lvert0\rangle. Equivalently,

Veq(μ,ν)∣ga⟩=(μ∗ν)a ∣a⟩⊗∣0⟩.V_{\mathrm{eq}}(\boldsymbol{\mu},\boldsymbol{\nu})\lvert g_a\rangle=\sqrt{(\boldsymbol{\mu} * \boldsymbol{\nu})_a}\,\lvert a\rangle\otimes\lvert0\rangle.

Applying this unitary to the expanded input state gives

Veq(μ,ν)(∣ϕd(μ)⟩⊗∣ϕd(ν)⟩)=(∑a∈Fp(μ∗ν)a ω−ad∣a⟩)⊗∣0⟩=∣ϕd(μ∗ν)⟩⊗∣0⟩.(30)V_{\mathrm{eq}}(\boldsymbol{\mu},\boldsymbol{\nu})\left(\lvert\phi_d(\boldsymbol{\mu})\rangle\otimes\lvert\phi_d(\boldsymbol{\nu})\rangle\right)=\left(\sum_{a\in\mathbb{F}_p}\sqrt{(\boldsymbol{\mu} * \boldsymbol{\nu})_a}\,\omega^{-ad}\lvert a\rangle\right)\otimes\lvert0\rangle=\lvert\phi_d(\boldsymbol{\mu} * \boldsymbol{\nu})\rangle\otimes\lvert0\rangle. \tag*{(30)}

This implements the bit-node compression specified in [21 Sec. III-A, Eq. (3), and Remark 14] in our message basis. The second output is fixed and can be discarded without loss of information about dd. The classical update is deterministic.

Parity rule. Suppose two incoming messages concern unknown symbols d1d_1 and d2d_2, respectively. The goal of the parity rule is to combine them into a message about their sum d=d1+d2d=d_1+d_2, which is their parity when p=2p=2. The two input symbols can vary independently, so their joint states may span the full two-qudit space. We will obtain a message consisting of one qudit together with a classical measurement outcome that specifies its state description.

The idea is to rearrange the input amplitudes so that the phase on the first qudit depends only on d1+d2d_1+d_2. Apply modular subtraction, Vpar∣a,b⟩=∣a,b−a⟩V_{\mathrm{par}}\lvert a,b\rangle=\lvert a,b-a\rangle, which is a CNOT for p=2p=2. Writing s=b−as=b-a, the resulting state is

Vpar(∣ϕd1(μ)⟩⊗∣ϕd2(ν)⟩)=∑s∈Fpω−sd2(∑a∈Fpμaνa+s ω−a(d1+d2)∣a⟩)∣s⟩.(31)V_{\mathrm{par}}\left(\lvert\phi_{d_1}(\mu)\rangle\otimes\lvert\phi_{d_2}(\nu)\rangle\right) = \sum_{s\in\mathbb{F}_p}\omega^{-sd_2} \left(\sum_{a\in\mathbb{F}_p}\sqrt{\mu_a\nu_{a+s}}\,\omega^{-a(d_1+d_2)}\lvert a\rangle\right)\lvert s\rangle. \tag*{(31)}

Measuring the second qudit now selects a value of ss. For each fixed input pair (d1,d2)(d_1,d_2), the factor ω−sd2\omega^{-sd_2} is then only a global phase, and the first qudit has exactly the form of a message about d1+d2d_1+d_2. The probability of outcome ss and the normalized classical description of this message are

πs=∑a∈Fpμaνa+s,μa(s)=μaνa+sπs(πs>0).(32)\pi_s=\sum_{a\in\mathbb{F}_p}\mu_a\nu_{a+s},\qquad \mu_a^{(s)}=\frac{\mu_a\nu_{a+s}}{\pi_s}\quad(\pi_s>0). \tag*{(32)}

These formulas are the sum-convention form of the check-node calculation in [21 Lemma 12 and Appendix E-A].2 Thus the outgoing quantum state is ∣ϕd1+d2(μ(s))⟩\lvert\phi_{d_1+d_2}(\mu^{(s)})\rangle. Although the outcome probabilities are independent of the input symbols, we retain ss because it specifies which classical description μ(s)\mu^{(s)} to use in subsequent combining operations [21 Remark 15]. The classical update therefore depends on the measurement outcome. An ensemble of pure-state messages accompanied by such a known classical label is called a heralded mixture [21 Definition 24].

BPQM decoding on a tree. For the code C⊥C^\perp in (6), the Tanner graph has symbol nodes djd_j and check nodes enforcing ∑jBjidj=0\sum_j B_{ji}d_j=0. Symbols have degree kk and checks have degree DD. Choose a finite tree neighborhood rooted at the symbol to be decoded (non-tree neighborhoods will be considered in § 6). The goal is to estimate the root symbol by combining the quantum information available throughout a tree. Each symbol djd_j has its own received quantum system, i.e., a message ∣ϕdj(μj)⟩\lvert\phi_{d_j}(\mu_j)\rangle as above. Starting at the leaf symbols, pass messages toward the root. A leaf sends its own message to its parent check. Internal nodes combine the messages received from their children, using the parity rule at checks and the equality rule at symbols, as follows.

At a check node ii whose parent is symbol djd_j, the child messages concern the other symbols in that check. The check equation expresses the parent symbol as

dj=∑h≠jBhi≠0(−Bji−1Bhi)dh.d_j=\sum_{\substack{h\ne j\\B_{hi}\ne0}}\left(-B_{ji}^{-1}B_{hi}\right)d_h .

To apply the parity rule repeatedly to obtain one message about djd_j, we first relabel each child’s message to describe its term in this sum: For α∈Fp×\alpha\in\mathbb{F}_p^\times, a relabeling dh↦αdhd_h\mapsto\alpha d_h is implemented by ∣a⟩↦∣α−1a⟩\lvert a\rangle\mapsto\lvert\alpha^{-1}a\rangle and μa↦μαa\mu_a\mapsto\mu_{\alpha a}.

At a symbol node djd_j, all messages from its child checks concern the same symbol. Combine them with the symbol’s own received message by repeated applications of the equality rule. A non-root internal symbol combines its k−1k-1 child-check messages and sends the result to its parent check; the root combines all kk check messages with its own received message. Thus the computation proceeds from the leaves to the root, with each outgoing message summarizing the information in the subtree below it. Nodes with several children simply apply the pairwise rules successively, as illustrated in Figure 1 (see also [28 Sec. 3.1.1]).

BPQM updates toward the root

Figure 1. BPQM updates toward the root. (Top) At a symbol node, equality rules combine k−1k-1 child-check messages with the symbol’s own noise channel output ∣ϕd(μ)⟩|\phi_d(\boldsymbol{\mu})\rangle. (Bottom) At a check node, parity rules combine D−1D-1 child-symbol messages into a message about the parent symbol, with coefficient relabelings understood. Each arrow carries a quantum system and its classical description. The right panels show successive pairwise applications of the rules.

At the root, the procedure leaves a single qudit in the state ∣ϕdroot(μroot)⟩|\phi_{d_{\mathrm{root}}}(\boldsymbol{\mu}_{\mathrm{root}})\rangle, together with the classical message μroot\boldsymbol{\mu}_{\mathrm{root}}. The probability vector μroot\boldsymbol{\mu}_{\mathrm{root}} is known from the classical outcome record and describes the possible states of this final qudit. To estimate drootd_{\mathrm{root}}, apply the pretty good measurement, which achieves error probability [21 Sec. II-E and Lemma 9]

Perr(μroot)=1−1p(∑a∈Fpμroot,a)2.(33)P_{\mathrm{err}}(\boldsymbol{\mu}_{\mathrm{root}})=1-\frac{1}{p}\left(\sum_{a\in\mathbb{F}_p}\sqrt{\mu_{\mathrm{root},a}}\right)^2. \tag*{(33)}

Averaging over the classical outcomes, the minimum error for this local decoding problem is therefore

Perr=E[Perr(μroot)].(34)P_{\mathrm{err}}=\mathbb{E}[P_{\mathrm{err}}(\boldsymbol{\mu}_{\mathrm{root}})]. \tag*{(34)}

The entire procedure is optimal for decoding the root symbol when the assignment is chosen uniformly from those satisfying the tree’s checks [22 Theorem 19].

There are a few more ingredients to turn the above tree BPQM decoder into a global codeword decoder. First, for usage in Regev’s reduction, we must keep the outcome registers in parity rules unmeasured and perform the classical updates of μ\mu and conditional gates coherently. This coherent implementation follows [28 Sec. 5.2] and [22].3 Retaining these registers and the other work systems allows the combining circuit to be reversed after extracting the symbol estimate. Second, decoding symbols in overlapping tree neighborhoods requires an analysis of the resulting disturbance of the quantum state. Third, the Tanner graph is not a tree, so we must analyze the effect of cycles on the decoding performance. All these subtleties were recently addressed in [22]; we will describe this and apply it to Gibbs sampling in § 6.

Finally, we need a classical algorithm to predict the decoding performance and threshold of BPQM. The random outcomes make μ\mu a random probability vector. This can be achieved by recursively tracking the classical laws determined by Eqs. (29) and (32). This is called quantum density evolution [8, 21, 22], which we describe in the next section.

Quantum Density Evolution

Quantum density evolution is a classical algorithm that applies the equality and parity update rules of § 4 to track the distributions of the classical parts of the BPQM messages toward the root [8, 21, 22]. Here we record the resulting recursion and fix notation for its comparison with tree reconstruction in § 8.

Let ℓ=0,1,2,…\ell= 0, 1, 2, \ldots index rounds toward the root. Write v(ℓ)v^{(\ell)} and q(ℓ)q^{(\ell)} for the classical parts of the symbol-to-check and check-to-symbol BPQM messages, respectively. One round is an equality update at the symbols followed by a parity update at their parent checks, as shown in Figure 2.

One round of BPQM updates toward the root

Figure 2. One round of BPQM updates toward the root. Arrow labels give the classical parts of the messages; other children are omitted.

The physical channel vector μj\mu_j may vary between symbols, as in (28). We suppress node and edge indices in the local recursions below: μ\mu denotes the channel vector at the symbol being updated.

Numbering the incoming check messages, repeated application of the equality rule (29) gives the deterministic update

v(ℓ)=μ∗q1(ℓ)∗⋯∗qk−1(ℓ).(35)v^{(\ell)} = \mu* q_1^{(\ell)} * \cdots* q_{k-1}^{(\ell)}. \tag*{(35)}

For a check constraint d=∑t=1D−1αtdtd=\sum_{t=1}^{D-1}\alpha_t d_t, relabel each incoming message as in § 4, setting νt,a(ℓ)=vt,αta(ℓ)\nu_{t,a}^{(\ell)}=v_{t,\alpha_t a}^{(\ell)}. Conditional on these incoming vectors, repeated application of the parity rule (32) gives a distribution over outgoing vector q(ℓ+1)\mathbf{q}^{(\ell+1)}. In particular, we set s1=0s_1=0 and sample the string s=(s2,…,sD−1)∈FpD−2\mathbf{s}=(s_2,\ldots,s_{D-1})\in\mathbb{F}_p^{D-2} with probability

Pr⁡(s)=Zs(ℓ):=∑a∈Fp∏t=1D−1νt,a+st(ℓ),(36)\Pr(\mathbf{s})=Z_{\mathbf{s}}^{(\ell)}:=\sum_{a\in\mathbb{F}_p}\prod_{t=1}^{D-1}\nu_{t,a+s_t}^{(\ell)}, \tag*{(36)}

then the associated outgoing vector q(ℓ+1)\mathbf{q}^{(\ell+1)} is

qa(ℓ+1)=∏t=1D−1νt,a+st(ℓ)Zs(ℓ),Zs(ℓ)>0.(37)q_a^{(\ell+1)}=\frac{\prod_{t=1}^{D-1}\nu_{t,a+s_t}^{(\ell)}}{Z_{\mathbf{s}}^{(\ell)}},\qquad Z_{\mathbf{s}}^{(\ell)}>0. \tag*{(37)}

We initialize

q(0)=(1,0,…,0).(38)\mathbf{q}^{(0)}=(1,0,\ldots,0). \tag*{(38)}

Since μ∗q(0)=μ\mu\ast\mathbf{q}^{(0)}=\mu, each initial symbol message has classical part v(0)=μv^{(0)}=\mu, using that symbol’s physical channel vector. Let QℓQ_\ell denote the distribution of the classical part of a check-to-symbol message q(ℓ)\mathbf{q}^{(\ell)} under this ensemble. So the initialization gives Q0=δe0Q_0=\delta_{e_0}.

At the root, the equality rule combines the physical channel with all kk check messages. The classical part of the resulting message and the average decoding error are

μroot(ℓ)=μ∗q1(ℓ)∗⋯∗qk(ℓ),Perr(ℓ)=E[Perr(μroot(ℓ))].(39)\mu_{\mathrm{root}}^{(\ell)}=\mu\ast q_1^{(\ell)}\ast\cdots\ast q_k^{(\ell)},\qquad P_{\mathrm{err}}^{(\ell)}=\mathbb{E}\left[P_{\mathrm{err}}\left(\mu_{\mathrm{root}}^{(\ell)}\right)\right]. \tag*{(39)}

Here PerrP_{\mathrm{err}} is given by (33), and the expectation averages over parity outcomes and, when applicable, the ensemble. The decoding threshold concerns whether Perr(ℓ)→0P_{\mathrm{err}}^{(\ell)}\to0 as ℓ→∞\ell\to\infty. In our numerical experiments, to determine the decoding threshold, we approximate the message distributions by collections of sampled vectors, apply these same updates, and average the root error.

From Tree Decoding to Coherent Gibbs Sampling

In § 4, we described how BPQM estimates the root symbol on a tree, and § 5 recorded the recursion determining its error. This section describes how to decode the entire codeword on a finite Tanner graph, then uses that decoder in Regev’s reduction to prepare the coherent Gibbs state.

Decoding the entire codeword. The lifting from tree BPQM decoding to global codeword decoding of random regular LDPC codes was established by Mandal, Piveteau, Renes, and Pfister [22]. They consider a random bipartite graph with symbol degree kk and check degree DD. Their ensemble allows parallel edges, unlike our ensemble in Definition 2. Below, we for completeness briefly overview how the global codeword decoding algorithm works, and then adapt the result of [22] to our ensemble.

The lifting to global decoding [22] relies on the following well-known fact: up to any ℓ=Θ(log⁡log⁡m)\ell=\Theta(\log\log m), the radius-ℓ\ell neighborhood of all but o(m)o(m) symbols is a tree, with high probability over the graph ensemble. Their decoder applies BPQM sequentially on these trees, records each root-symbol estimate, and reverses the BPQM unitaries. Recall that for use in Regev’s reduction, the measurement outcomes are retained coherently. A quantum union bound controls the accumulated measurement disturbance, and because the tree BPQM decoding error, if converging to zero, can be shown to decay doubly exponentially with the tree depth ℓ\ell [22], the total error of the BPQM stage vanishes. Symbols with non-tree neighborhoods are then treated as erasures and recovered by Gaussian elimination. There are only o(m)o(m) such symbols, while the code’s minimum distance is linear in mm, so erasure recovery succeeds provided the BPQM estimates are correct. Erasure correction is done by Gaussian elimination, implemented reversibly.

We now specialize this result to our code ensemble and to the physical channel of (26).

Proposition 2 (Global decoding from tree decoding [22]). Let (B,F)(B,F) be drawn from the ensemble Greg(n,k,D,p,S,Λ)\mathcal{G}_{\mathrm{reg}}(n,k,D,p,S,\Lambda) of Definition 2. At any fixed β≥0\beta\ge0, let μ\mu be the channel vector in (28) for the common target set SS. Suppose the recurrence in § 5 satisfies E[Perr(v(ℓ))]→0\mathbb{E}[P_{\mathrm{err}}(v^{(\ell)})] \to0. Then, for a suitable ℓ=Θ(log⁡log⁡m)\ell= \Theta(\log\log m), the BPQM decoder with erasure recovery of [22 Theorem 30] runs in polynomial time and decodes a uniformly chosen codeword of C⊥=ker⁡BTC^\perp= \ker B^{T} with ensemble-average error probability tending to zero as mm increases.

Proof. The result follows from [22 Theorem 30] with two differences to address: we allow a more general coefficient distribution Λ\Lambda, and we disallow parallel edges. Their code has mm symbols, symbol degree kk, check degree DD, and alphabet size pp in our notation.

Coefficient distribution. First use the random graph of [22], generated by uniformly matching the mk=nDmk = nD edge ends on each side of the bipartite Tanner graph, and independently assign a coefficient tuple with law Λ\Lambda to the DD ends at each check. Although the coefficients in [22] are independent and uniform, the combining bounds in their Lemmas 24–25 hold for every choice of nonzero coefficients, with right-hand sides independent of those coefficients. Condition on a check’s entire tuple: its incoming messages depend on disjoint descendant subtrees, which use independent column tuples and are independent of the conditioned tuple. Thus correlations within a column do not affect the averaging step in their proof of Theorem 26. Together with their Lemma 18, that argument still gives doubly-exponential-in-ℓ\ell decay of the tree decoding error, under the assumption E[Perr(v(ℓ))]⟶0\mathbb{E}[P_{\mathrm{err}}(v^{(\ell)})] \longrightarrow0.

The linear code distance input to their Theorem 30 also holds for our coefficient law. A nonzero codeword’s support has no check incident to exactly one of its edges. A set of ss symbols with this property reaches at most ⌊ks/2⌋\lfloor ks/2\rfloor checks. We take a union bound over the choice of the ss symbols and of ⌊ks/2⌋\lfloor ks/2\rfloor checks containing all their neighbors; the probability that all ksks edge ends of these symbols are matched into those checks is at most (⌊ks/2⌋/n)ks(\lfloor ks/2\rfloor/n)^{ks}. For sufficiently small fixed δ>0\delta> 0, this gives

Pr⁡{some nonempty such set has size at most δm}≤∑s=1⌊δm⌋(ms)(n⌊ks/2⌋)(⌊ks/2⌋DnD)ks≤∑s=1⌊δm⌋[e(eD2)k/2(sm)k/2−1]s=o(1),\begin{aligned} \Pr\{\text{some nonempty such set has size at most }\delta m\} \le\sum_{s=1}^{\lfloor\delta m\rfloor} \binom{m}{s} \binom{n}{\lfloor ks/2\rfloor} \left(\frac{\lfloor ks/2\rfloor D}{nD}\right)^{ks} \\ &\le\sum_{s=1}^{\lfloor\delta m\rfloor} \left[e\left(\frac{eD}{2}\right)^{k/2} \left(\frac{s}{m}\right)^{k/2-1}\right]^{s} = o(1), \end{aligned}

where the second inequality uses (Ni)≤(eN/i)i\binom{N}{i} \le(eN/i)^i and n=mk/Dn = mk/D. Hence the minimum distance exceeds δm\delta m with high probability, regardless of the nonzero coefficients. The local decoding, cycle counting, and erasure-recovery arguments in their Lemmas 21, 27–28 and Theorem 30 now apply unchanged. In particular, let ϵ(G)\epsilon(G) denote the decoder’s block-error probability for a graph GG drawn by the matching construction of [22 Sec. 4.1], with coefficient law Λ\Lambda as above. These arguments give EG[ε(G)]→0\mathbb{E}_{G}[\varepsilon(G)] \to0 at a suitable ℓ=Θ(log⁡log⁡m)\ell= \Theta(\log\log m).

No parallel edges. Let A\mathcal{A} be the event that the matched graph has no parallel edges. Each labeled simple (k,D)(k,D)-regular bipartite graph arises from exactly (k!)m(D!)n(k!)^{m}(D!)^{n} matchings, since the edge ends at each vertex can be assigned to its incident edges in any order. Conditional on A\mathcal{A}, the support is therefore uniform among the graphs in Definition 2. The column tuples remain independent because A\mathcal{A} depends only on the matching, and exchangeability preserves their law Λ\Lambda when ordered by neighboring symbols. This gives precisely our ensemble, including both Λiid\Lambda_{\mathrm{iid}} and Λperm\Lambda_{\mathrm{perm}}.

For fixed kk, DD, lim inf⁡m→∞Pr⁡(A)>0\liminf_{m\to\infty}\Pr(\mathcal{A}) > 0 [13 Theorem 5.1]. Writing εB\varepsilon_{B} for the decoder’s block-error probability on our ensemble, we conclude

EB[εB]=EG[ε(G)∣A]≤EG[ε(G)]Pr⁡(A)⟶0.(40)\mathbb{E}_{B}[\varepsilon_{B}] = \mathbb{E}_{G}[\varepsilon(G)\mid\mathcal{A}] \le\frac{\mathbb{E}_{G}[\varepsilon(G)]}{\Pr(\mathcal{A})} \longrightarrow0. \tag*{(40)}

Coherent Gibbs sampling. We now combine the global quantum decoder and Regev’s reduction to perform coherent Gibbs sampling for the ensemble of Definition 2. Recall that each target set Fj=τj+SF_j=\tau_j+S is a random translate of a fixed set SS. We use the same decoder for every choice of shifts: it decodes the channel associated with SS, while the shifts τj\tau_j are implemented by phase gates in Regev’s reduction. According to (28), the unshifted channel has parameters

μa=1r+(p−r)e−β{1,a∈S,e−β,a∉S,r=∣S∣.(41)\mu_a = \frac{1}{r+(p-r)e^{-\beta}} \begin{cases} 1, & a\in S,\\ e^{-\beta}, & a\notin S, \end{cases} \qquad r=|S|. \tag*{(41)}

We will apply Proposition 2 to solve the quantum decoding problem associated to this channel. The random shifts τj\tau_j allow us to apply [SMR+26, Lemma 4] to convert quantum decoding error to Regev’s reduction error.

Corollary 3 (Coherent Gibbs sampling). Let (B,F)∼Greg(n,k,D,p,S,Λ)(B,F)\sim G_{\mathrm{reg}}(n,k,D,p,S,\Lambda) as in Definition 2. Fix an inverse temperature β≥0\beta\ge0. Suppose the check-to-symbol messages q(ℓ)q^{(\ell)} of the density evolution in § 5, for this law and the channel (41), satisfy E[∥q(ℓ)−u∥22]→0\mathbb{E}[\lVert q^{(\ell)}-u\rVert_2^2]\to0, where u=(1/p,…,1/p)u=(1/p,\ldots,1/p). Then, with probability 1−o(1)1-o(1) over (B,τ)(B,\tau), Regev’s reduction with the decoder of Proposition 2 prepares a state within o(1)o(1) trace distance of the coherent Gibbs state ∣ψβ⟩|\psi_\beta\rangle in (2), in polynomial time and with failure probability o(1)o(1), as n→∞n\to\infty. This applies to both Λiid\Lambda_{\mathrm{iid}} and Λperm\Lambda_{\mathrm{perm}}.

Proof. The hypothesis and (35) imply E[Perr(v(ℓ))]→0\mathbb{E}[P_{\mathrm{err}}(v^{(\ell)})]\to0. By Proposition 2, the decoder’s block-error probability εB\varepsilon_B satisfies EB[εB]→0\mathbb{E}_B[\varepsilon_B]\to0.

Let ∣vd⟩|v_d\rangle be the normalized received state (14) with every target set equal to SS. Write the coherent decoder’s action as

Udec(∣vd⟩∣0⟩)=∑d^∈Fpm∣ηd^,d⟩∣d^⟩.U_{\mathrm{dec}}(|v_d\rangle|0\rangle)=\sum_{\widehat{d}\in F_p^m}|\eta_{\widehat{d},d}\rangle|\widehat{d}\rangle.

where each unnormalized ∣ηd^,d⟩|\eta_{\widehat{d},d}\rangle contains the received system and all other decoder registers. Following [SMR+26, Sec. 7.2], apply the phase ω−⟨τ,d⟩\omega^{-\langle\tau,d\rangle}, apply the decoding unitary UdecU_{\mathrm{dec}}, and test whether the estimate d^\widehat{d} agrees with register dd. Report failure otherwise. The test accepts with probability 1−εB1-\varepsilon_B. On the accepting branch, subtracting the estimate from the codeword register gives

1∣C⊥∣∑d∈C⊥ω−⟨τ,d⟩∣d⟩∣vd⟩∣0⟩→decode, test, subtract∣0⟩⊗∑d∈C⊥ω−⟨τ,d⟩∣ηd,d⟩∣d⟩∣C⊥∣(1−εB).\frac{1}{\sqrt{|C^\perp|}}\sum_{d\in C^\perp}\omega^{-\langle\tau,d\rangle}|d\rangle|v_d\rangle|0\rangle\xrightarrow{\text{decode, test, subtract}} |0\rangle\otimes\frac{\sum_{d\in C^\perp}\omega^{-\langle\tau,d\rangle}|\eta_{d,d}\rangle|d\rangle}{\sqrt{|C^\perp|(1-\varepsilon_B)}}.

Now reverse UdecU_{\mathrm{dec}}, apply Zτ∣y⟩=ω⟨τ,y⟩∣y⟩Z_\tau|y\rangle=\omega^{\langle\tau,y\rangle}|y\rangle to the received register, and apply the inverse Fourier transform. To see what these steps do, consider an ideal decoder, εB=0\varepsilon_B=0, for which reversing UdecU_{\mathrm{dec}} maps ∣ηd,d⟩∣d⟩|\eta_{d,d}\rangle|d\rangle back to ∣vd⟩∣0⟩|v_d\rangle|0\rangle. Write P~βS\widetilde{P}_\beta^S for the envelope (20) with every FjF_j replaced by SS, so that ∣vd⟩=∥PβS∥2−1∑eP~βS(e)∣d+e⟩|v_d\rangle=\|P_\beta^S\|_2^{-1}\sum_e\widetilde{P}_\beta^S(e)|d+e\rangle. Since Fj=τj+SF_j=\tau_j+S, (11) gives

P~β(e)∥Pβ∥2=ω⟨τ,e⟩P~βS(e)∥PβS∥2.\frac{\widetilde{P}_\beta(e)}{\|P_\beta\|_2}=\omega^{\langle\tau,e\rangle}\frac{\widetilde{P}_\beta^S(e)}{\|P_\beta^S\|_2}.

Omitting the work registers,

1∣C⊥∣∑d∈C⊥ω−⟨τ,d⟩Zτ∣vd⟩=1∣C⊥∣∥PβS∥2∑d∈C⊥∑e∈Fpmω⟨τ,d+e⟩−⟨τ,d⟩P~βS(e)∣d+e⟩=1∣C⊥∣∥Pβ∥2∑d∈C⊥∑e∈FpmP~β(e)∣d+e⟩.\begin{aligned} \frac{1}{\sqrt{|C^\perp|}}\sum_{d\in C^\perp}\omega^{-\langle\tau,d\rangle}Z_\tau|v_d\rangle = \frac{1}{\sqrt{|C^\perp|}\|P_\beta^S\|_2}\sum_{d\in C^\perp}\sum_{e\in\mathbb{F}_p^m}\omega^{\langle\tau,d+e\rangle-\langle\tau,d\rangle}\widetilde{P}_\beta^S(e)|d+e\rangle\\ &= \frac{1}{\sqrt{|C^\perp|}\|P_\beta\|_2}\sum_{d\in C^\perp}\sum_{e\in\mathbb{F}_p^m}\widetilde{P}_\beta(e)|d+e\rangle. \end{aligned}

Up to normalization, this is ∣C~β⟩|\widetilde{C}_\beta\rangle in (22), so the inverse Fourier transform gives the target state ∣ψβ⟩|\psi_\beta\rangle. For nonzero εB\varepsilon_B, denote the normalized output, including all work registers, by ∣ΨB,τ⟩|\Psi_{B,\tau}\rangle. The error analysis of [SMR+26, Lemma 4] gives

Eτ[1−∣⟨ψβ∣⊗⟨0∣work∣ΨB,τ⟩∣2]≤εB.(42)\mathbb{E}_\tau\left[1-\left|\langle\psi_\beta|\otimes\langle0|_{\mathrm{work}}|\Psi_{B,\tau}\rangle\right|^2\right]\leq\varepsilon_B. \tag*{(42)}

The left-hand side is the expected squared trace distance between these pure states. Averaging over BB and applying Markov’s inequality gives trace-distance error and failure probability o(1)o(1), with probability 1−o(1)1-o(1) over (B,τ)(B,\tau).

In § 8, we will show that the convergence condition in Corollary 3 corresponds precisely to the reconstruction threshold on the inverse temperature β\beta.

The Reconstruction Threshold

In many random optimization problems, spin glass theory predicts a dynamical transition that occurs at a critical inverse temperature βdyn\beta_{\mathrm{dyn}}, which is determined by when there exists a nontrivial solution to the one-step replica-symmetry-breaking (1RSB) equation with Parisi parameter m=1m=1 [23, 19]. According to Mézard and Montanari [19], these equations can be mapped to a reconstruction problem on the infinite tree. We use this reconstruction problem to define βdyn\beta_{\mathrm{dyn}} below.

The Reconstruction Problem. Following [19], we introduce the reconstruction problem as a communication problem on a tree. A source at the root chooses a symbol uniformly from Fp\mathbb{F}_p and sends it through noisy channels to its children. Each child then transmits to the next generation in the same way. After ℓ\ell generations, an observer sees only the symbols at that last generation. The task is to infer the original root symbol from these observations. Reconstruction is possible if, as ℓ→∞\ell\to\infty, the observer can still guess the root with a success probability that exceeds 1/p1/p by a fixed positive amount.

For our spin model, the tree has variable nodes and constraint nodes, just as in the Tanner graph of Definition 2. Each variable belongs to DD constraints, and each constraint contains kk variables. A constraint acts as a channel from one parent variable to k−1k-1 child variables, whose values are generated jointly. This is the one-to-many broadcast considered in [19 Section 7]. One generation passes through a constraint to its child variables. The observer knows the tree, its coefficients, and its target offsets; we denote this information by T\mathcal{T}.

We now specify the channel for which the broadcast generates our desired Gibbs distribution. Fix a nonempty proper accepting set S⊊FpS \subsetneq\mathbb{F}_p, let r=∣S∣r=|S|, and write

wβ(u)=e−β+(1−e−β)1{u∈S},cβ=r+(p−r)e−β,μa=wβ(a)cβ.(43)w_\beta(u)=e^{-\beta}+(1-e^{-\beta})\mathbf{1}\{u\in S\},\qquad c_\beta=r+(p-r)e^{-\beta},\qquad\mu_a=\frac{w_\beta(a)}{c_\beta}. \tag*{(43)}

For a constraint jj with parent variable ii and children i1,…,ik−1i_1,\ldots,i_{k-1}, the probability of the child values, given the parent, is

Kj(xi1,…,xik−1∣xi)=wβ(Bjixi+∑h=1k−1Bjihxih−τj)pk−2cβ.(44)K_j(x_{i_1},\ldots,x_{i_{k-1}}\mid x_i)=\frac{w_\beta\left(B_{ji}x_i+\sum_{h=1}^{k-1}B_{jih}x_{i_h}-\tau_j\right)}{p^{k-2}c_\beta}. \tag*{(44)}

To sample it, draw a residual Uj∼μU_j\sim\mu, then choose the k−1k-1 children uniformly subject to Bjixi+∑hBjihxih−τj=UjB_{ji}x_i+\sum_h B_{jih}x_{i_h}-\tau_j=U_j. All coefficients are nonzero, so there are exactly pk−2p^{k-2} choices. Start with a uniform root and apply this rule at each constraint, using independent randomness at different constraints. The probability of a complete assignment is then proportional to e−βE(x)e^{-\beta E(x)}; it is precisely the Gibbs distribution on the finite tree, with no spins fixed at the boundary. This is called the free-boundary Gibbs measure. Continuing the broadcast defines it on the infinite tree as well. Note that children of one constraint can be correlated, but their subsequent broadcasts are independent once their values and T\mathcal{T} are fixed.

Definition 3 (Reconstruction threshold). For the broadcast (44), let X0X_0 be the uniform root symbol and X∂TℓX_{\partial T_\ell} the symbols observed at generation ℓ\ell. The conditional mutual information retained about the root is

Iℓ(β):=I(X0;X∂Tℓ∣T).(45)I_\ell(\beta):=I(X_0;X_{\partial T_\ell}\mid\mathcal{T}). \tag*{(45)}

Reconstruction is possible at β\beta if lim⁡ℓ→∞Iℓ(β)>0\lim_{\ell\to\infty}I_\ell(\beta)>0. For a fixed accepting set and coefficient law, the reconstruction threshold is

βdyn:=inf⁡{β>0:lim⁡ℓ→∞Iℓ(β)>0},(46)\beta_{\mathrm{dyn}}:=\inf\left\{\beta>0:\lim_{\ell\to\infty}I_\ell(\beta)>0\right\}, \tag*{(46)}

with inf⁡∅=∞\inf\varnothing=\infty.

At β=0\beta=0, the children are uniform and independent of the parent, so the boundary carries no information about the root. Increasing β\beta makes the constraints more informative. Thus reconstruction fails below βdyn\beta_{\mathrm{dyn}} and succeeds above it.

The reconstruction problem

Figure 3. The reconstruction problem. Each of the D−1D-1 child constraints jointly generates k−1k-1 child spins using (44). After broadcasting to depth ℓ\ell, reveal the boundary and compute the posterior of XiX_i by passing messages inward. The full-root problem includes all DD constraints. Under transposition to the decoding graph, circles become parity checks and squares become code symbols with physical channel outputs.

Reconstruction threshold from posterior distributional recursion. We now describe the recursion equation for the posterior distribution for any specified (k,D,p,S,Λ)(k,D,p,S,\Lambda), and in turn provide a more explicit definition of βdyn\beta_{\mathrm{dyn}}. The recursion is performed on a probability vector η~\widetilde{\eta} on Fp\mathbb{F}_p, which we call a reconstruction message, whose entry η~(z)\widetilde{\eta}(z) denotes the posterior probability that the root differs from its “planted value” by zz, after rescaling by the coefficient on its parent constraint. More precisely, we draw a reference configuration x∗\boldsymbol{x}^{*} from the Gibbs broadcast so that xi∗x_i^{*} is the planted value at the root node ii; if the inferred root variable is xix_i and its parent constraint is j0j_0, then the error coordinate is z=Bj0i(xi−xi∗)z=B_{j_0i}(x_i-x_i^{*}). For its child constraints jtj_t, write γt=Bjti/Bj0i∈Fp×\gamma_t=B_{j_ti}/B_{j_0i}\in\mathbb{F}_p^{\times}, with t=1,…,D−1t=1,\ldots,D-1.

Let η~(0)=e0\widetilde{\eta}^{(0)}=e_0, the point mass at z=0z=0, corresponding to zero error at the ℓ=0\ell=0 generation. For each ℓ≥0\ell\geq0, draw one DD-tuple of coefficients from the given law Λ\Lambda and compute the coefficient ratios γ1,…,γD−1\gamma_1,\ldots,\gamma_{D-1} of the D−1D-1 children relative to their parent. Here, for each t∈[D−1]t\in[D-1], we choose the noise residual Ut∼i.i.d.μU_t\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\mu from (43), and independently draw the k−1k-1 copies of η~(ℓ)\widetilde{\eta}^{(\ell)} as the child messages to obtain

Gt:=η~t,1(ℓ)∗⋯∗η~t,k−1(ℓ),andΓt(s):=Pr⁡Z∼Gt[Z+s∈S]=∑v∈SGt(v−s).(47)G_t:=\widetilde{\eta}_{t,1}^{(\ell)}*\cdots*\widetilde{\eta}_{t,k-1}^{(\ell)},\qquad\text{and}\qquad\Gamma_t(s):=\Pr_{Z\sim G_t}[Z+s\in S]=\sum_{v\in S}G_t(v-s). \tag*{(47)}

where ∗* is the circular convolution in (29). The interpretation here is that the convolution GG is the distribution of the sum of the child errors in the constraint’s coordinates; summing the Gibbs weight over these errors gives the likelihood ∑wGt(w)wβ(Ut+γtz+w)=e−β+(1−e−β)Γt(Ut+γtz)\sum_w G_t(w)w_\beta(U_t+\gamma_tz+w)=e^{-\beta}+(1-e^{-\beta})\Gamma_t(U_t+\gamma_tz). Then the posterior message distribution at generation ℓ+1\ell+1 is

η~(ℓ+1)(z)∝d1N∏t=1D−1[e−β+(1−e−β)Γt(Ut+γtz)],z∈Fp.(48)\widetilde{\eta}^{(\ell+1)}(z)\mathrel{\mathop{\propto}^{d}}\frac{1}{\mathcal{N}}\prod_{t=1}^{D-1}\left[e^{-\beta}+(1-e^{-\beta})\Gamma_t(U_t+\gamma_tz)\right],\qquad z\in\mathbb{F}_p. \tag*{(48)}

where N\mathcal{N} is a normalization fixed by ∑zη~(ℓ+1)(z)=1\sum_z\widetilde{\eta}^{(\ell+1)}(z)=1. To measure the information in the posterior about the root variable, we compare it against the uniform random guess by defining

Ψℓ:=E[η~(ℓ)(0)]−1p,Ψ∞(β;k,D,p,S,Λ):=lim⁡ℓ→∞Ψℓ.(49)\Psi_\ell:= \mathbb{E}[\tilde{\eta}^{(\ell)}(0)]-\frac{1}{p}, \qquad\Psi_\infty(\beta;k,D,p,S,\Lambda):=\lim_{\ell\to\infty}\Psi_\ell. \tag*{(49)}

Note Ψℓ\Psi_\ell is the excess success probability of guessing the root correctly by sampling from the posterior; in particular, Ψ0=1−1/p\Psi_0=1-1/p.

Since a farther boundary is obtained by continuing the broadcast from a nearer one, Ψℓ\Psi_\ell is nonincreasing in ℓ\ell due to the data processing inequality. As noted in [19], the limit Ψ∞\Psi_\infty exists and vanishes exactly when the mutual information vanishes. Thus, the reconstruction threshold (46) can be equivalently written as

βdyn(k,D,p,S,Λ):=inf⁡{β>0:Ψ∞(β;k,D,p,S,Λ)>0}.(50)\beta_{\mathrm{dyn}}(k,D,p,S,\Lambda):=\inf\{\beta>0:\Psi_\infty(\beta;k,D,p,S,\Lambda)>0\}. \tag*{(50)}

Remarks.

  1. We remark that the reconstruction information Ψℓ(β)\Psi_\ell(\beta) is nondecreasing in β\beta, making βdyn\beta_{\mathrm{dyn}} a genuine threshold. This enables us to locate the transition βdyn\beta_{\mathrm{dyn}} by scanning β\beta and bisecting. In Corollary 5 of § 8, we give a proof of this monotonicity using channel duality.

  1. The formulation above recovers known recursions for Ising model/max-XORSAT as a special case (see e.g., [36]). At (p,r)=(2,1)(p,r)=(2,1), write Mℓ=η~(ℓ)(0)−η~(ℓ)(1)M_\ell=\tilde{\eta}^{(\ell)}(0)-\tilde{\eta}^{(\ell)}(1) for the posterior magnetization. Then (48) reduces to the max-XORSAT recursion in [36 Appendix D.2]:

Mℓ+1=dtanh⁡[∑t=1D−1artanh⁡(ησt∏j=1k−1Mℓ,t,j)].(51)M_{\ell+1}\overset{\mathrm{d}}{=}\tanh\left[\sum_{t=1}^{D-1}\operatorname{artanh}\left(\eta\sigma_t\prod_{j=1}^{k-1}M_{\ell,t,j}\right)\right]. \tag*{(51)}

Here η=tanh⁡(β/2)\eta=\tanh(\beta/2), the children are independent copies of MℓM_\ell, and σt=(−1)Ut\sigma_t=(-1)^{U_t} are independent signs with Pr⁡(σt=s)=(1+sη)/2\Pr(\sigma_t=s)=(1+s\eta)/2. In particular, Ψℓ=E[Mℓ]/2\Psi_\ell=\mathbb{E}[M_\ell]/2.

  1. When the accepting set size is ∣S∣=1|S|=1 or p−1p-1, the threshold βdyn(k,D,p,S,Λ)\beta_{\mathrm{dyn}}(k,D,p,S,\Lambda) is in fact independent of Λ\Lambda. This is because on the tree, a change of variables exists, via xi=aiyi+bix_i=a_i y_i+b_i, so that each constraint ∑iBjixi−τj∈S\sum_{i}B_{ji}x_i-\tau_j\in S becomes either ∑i∈∂jyi=0\sum_{i\in\partial j}y_i=0 or ∑i∈∂jyi≠0\sum_{i\in\partial j}y_i\ne0, when ∣S∣=1|S|=1 or p−1p-1 respectively. For other accepting-set sizes, however, βdyn\beta_{\mathrm{dyn}} may depend on the choice of Λ\Lambda.

  1. If instead of Greg\mathcal{G}_{\mathrm{reg}}, one is interested in the Erdős–Rényi ensemble of kk-uniform hypergraphs with average degree DD, the corresponding tree recursion replaces D−1D-1 in (48) by an independently random offspring count d∼Poisson⁡(D)d\sim\operatorname{Poisson}(D). Then one needs to specify a family of exchangeable, degree-dependent coefficient law Λ\Lambda, and draw d+1d+1 coefficients for the clauses incident to every variable node.

Connection to BPQM. The reconstruction distributional recursion resembles quantum density evolution in § 5, as both pass probability vectors inward on the same tree. Their information meanings are reversed, however: a uniform classical posterior means that the root cannot be inferred, whereas a uniform BPQM vector describes orthogonal quantum states and permits perfect decoding. The next section explains this correspondence and proves the two thresholds coincide.

Proof of the Main Theorem

This section proves our main theorem: the BPQM decoding threshold coincides with the reconstruction threshold. The resemblance between the BPQM and reconstruction recursions on the infinite tree becomes an exact correspondence after a random translation and reflection of each BPQM vector. The correspondence can be understood via Renes’ channel duality [32], which explains why impossibility of reconstruction coincides with decodability with vanishing error. For our channels, this duality reduces to simple identities for sums and conditional probabilities which we verify directly, after which we relate the message convergence to the root decoding error. Combining this coincidence with Corollary 3, we also show Regev+BPQM can coherently Gibbs sample the corresponding max-LINSAT Hamiltonian up to the reconstruction threshold, which is the conjectured limit on classical local dynamics from the dynamical glass transition.

Fix any nonempty proper accepting set S⊊FpS \subsetneq\mathbb{F}_p and a coefficient law Λ\Lambda for both recursions. Let Qℓ\mathcal{Q}_{\ell} be the BPQM check-to-symbol message law in § 5, using the unshifted physical channel μ\mu of (41), and let Perr(ℓ)P_{\mathrm{err}}^{(\ell)} be its ensemble-average terminal error from (39). Define

βBPQM(k,D,p,S,Λ):=inf⁡{β>0:lim⁡ℓ→∞Perr(ℓ)>0}.(52)\beta_{\mathrm{BPQM}}(k,D,p,S,\Lambda) := \inf\left\{ \beta> 0 : \lim_{\ell\to\infty} P_{\mathrm{err}}^{(\ell)} > 0 \right\}. \tag*{(52)}

Note the error limit exists because increasing the tree depth supplies more channel outputs and BPQM achieves the minimum root error on each tree [28]. We restate Theorem 1 formally:

Theorem 4 (Regev+BPQM reaches reconstruction threshold). Fix a prime pp, integers 3≤k<D3 \le k < D, and a nonempty proper subset S⊊FpS \subsetneq\mathbb{F}_p. At each optimization variable, independently draw its incident nonzero coefficients from an exchangeable law Λ\Lambda on (Fp×)D(\mathbb{F}_p^\times)^D. Use this same law for reconstruction and BPQM recursions. For a probability vector q\mathbf{q} over Fp\mathbb{F}_p, define its random posterior lift vector by

L(q)z:=qA−z,with A∼q.(53)\mathcal{L}(\mathbf{q})_z := q_{A-z}, \qquad\text{with } A \sim\mathbf{q}. \tag*{(53)}

Let q(0)=η~(0)=e0\mathbf{q}^{(0)} = \widetilde{\boldsymbol{\eta}}^{(0)} = \mathbf{e}_0, q(ℓ)∼Qℓ\mathbf{q}^{(\ell)} \sim\mathcal{Q}_{\ell}, and η~(ℓ)\widetilde{\boldsymbol{\eta}}^{(\ell)} be as in (48). Then, for every finite β≥0\beta\ge0 and depth ℓ≥0\ell\ge0,

η~(ℓ)=dL(q(ℓ)),Ψℓ=E[∥q(ℓ)−u∥22],(54)\widetilde{\boldsymbol{\eta}}^{(\ell)} \mathrel{\overset{d}{=}} \mathcal{L}\left(\mathbf{q}^{(\ell)}\right), \qquad\Psi_{\ell} = \mathbb{E}\left[\left\|\mathbf{q}^{(\ell)}-\mathbf{u}\right\|_2^2\right], \tag*{(54)}

where u=(1/p,…,1/p)\mathbf{u} = (1/p,\ldots,1/p). Their thresholds satisfy

βBPQM(k,D,p,S,Λ)=βdyn(k,D,p,S,Λ).(55)\beta_{\mathrm{BPQM}}(k,D,p,S,\Lambda) = \beta_{\mathrm{dyn}}(k,D,p,S,\Lambda). \tag*{(55)}

For the finite-graph ensemble of Definition 2, every fixed 0≤β<βdyn0 \le\beta< \beta_{\mathrm{dyn}} admits polynomial-time coherent Gibbs sampling by Regev+BPQM, with the error and failure guarantees of Corollary 3.

We remark that the threshold equality (55) concerns the ideal infinite tree recursions. The result does not establish any shattering or provable hardness of sampling on finite graphs at β>βdyn\beta> \beta_{\mathrm{dyn}}, which requires additional arguments (see e.g., [10, 5, 36]).

Channel duality. To prepare for the proof, we first establish two identities (57) and (58) arising from Renes’ channel duality [32], which we will use to connect the update rules for two recursions. This channel duality will also explain the apparent reversal in the meaning of information in the two settings: Near-perfect BPQM decoding is possible if and only if reconstruction is impossible.

Write WqW_q for the BPQM message channel d↦∣ϕd(q)⟩d \mapsto\lvert\phi_d(\mathbf{q})\rangle in (26). Its dual is equivalent, up to a fixed basis change and relabeling, to the classical additive channel

Wq⊥(y∣x)=qy−x,i.e.,Y=X+A,A∼q,(56)W_q^\perp(y \mid x) = q_{y-x}, \qquad\text{i.e.,} \quad Y = X + A, \quad A \sim q, \tag*{(56)}

where XX is the input whose prior distribution we will take to be uniform on Fp\mathbb{F}_p. Renes’ duality theorem exchanges equality and parity combinations for binary-alphabet channels [32 Theorem 1]. For our channel family over Fp\mathbb{F}_p, the same exchange follows from the posterior representation that we verify below.

With the uniform prior X∼FpX \sim\mathbb{F}_p, the posterior after observing Y=yY=y has entries Pr⁡(X=x∣Y=y)=qy−x\Pr(X=x \mid Y=y)=q_{y-x}. Sampling observations conditional on the transmitted value X=0X=0, such that Y=AY=A, gives precisely the random posterior lift L(q)x=qA−x\mathcal{L}(\mathbf{q})_x=q_{A-x} defined in (53). Two independent such posteriors combine by convolution when estimating the sum of their symbols, and by normalized component-wise multiplication when they are independent observations of the same symbol. Specifically, consider any two probability vectors q\mathbf{q} and r\mathbf{r} on Fp\mathbb{F}_p, and let w\mathbf{w} be their parity output as in (32): draw ss with probability πs=∑aqara+s\pi_s=\sum_a q_a r_{a+s} and set wa=qara+s/πsw_a=q_a r_{a+s}/\pi_s. Accordingly,

L(q∗r)=dL(q)∗L(r),(57)\mathcal{L}(\mathbf{q} \ast\mathbf{r}) \mathrel{\stackrel{d}{=}} \mathcal{L}(\mathbf{q}) \ast\mathcal{L}(\mathbf{r}), \tag*{(57)}
L(w)x=dL(q)xL(r)x∑y∈FpL(q)yL(r)y.(58)\mathcal{L}(\mathbf{w})_x \mathrel{\stackrel{d}{=}} \frac{\mathcal{L}(\mathbf{q})_x\mathcal{L}(\mathbf{r})_x}{\sum_{y\in\mathbb{F}_p}\mathcal{L}(\mathbf{q})_y\mathcal{L}(\mathbf{r})_y}. \tag*{(58)}

These are identities of joint vector distributions, with independent input lifts on each right-hand side. For the first, use independent noises A1∼qA_1\sim\mathbf{q} and A2∼rA_2\sim\mathbf{r} and add them. For the second, set s=A2−A1s=A_2-A_1. Its probability and the conditional distribution of A1A_1 are exactly the branch probability and outgoing vector in (32). Evaluating the outgoing vector at a=A1−xa=A_1-x gives the normalized product in (58). For the coefficient relabeling in § 5, write (Rαq)a=qαa(R_\alpha\mathbf{q})_a=q_{\alpha a}; then L(Rαq)x=dL(q)αx\mathcal{L}(R_\alpha\mathbf{q})_x\mathrel{\stackrel{d}{=}}\mathcal{L}(\mathbf{q})_{\alpha x}. Thus quantum symbol updates become classical check updates, and quantum check updates become classical symbol updates under Renes’ channel duality.

Furthermore, we remark that Renes’ tight entropic uncertainty relation for Fourier-conjugate inputs gives complementary information quantities [32 Theorem 2 and Corollary 4], making the information reversal between the two recursions quantitative. With H(q)=−∑aqalog⁡qaH(\mathbf{q})=-\sum_a q_a\log q_a, for a fixed probability vector q\mathbf{q} and uniform input, the quantum Holevo information χ\chi of WqW_{\mathbf{q}} and the classical mutual information II of Wq⊥W_{\mathbf{q}}^\perp satisfy

χ(Wq)=H(q),I(Wq⊥)=log⁡p−H(q),χ(Wq)+I(Wq⊥)=log⁡p.(59)\chi(W_{\mathbf{q}})=H(\mathbf{q}), \qquad I(W_{\mathbf{q}}^\perp)=\log p-H(\mathbf{q}), \qquad\chi(W_{\mathbf{q}})+I(W_{\mathbf{q}}^\perp)=\log p. \tag*{(59)}

Indeed, the outputs of WqW_{\mathbf{q}} are pure and their average is 1p∑d∣ϕd(q)⟩⟨ϕd(q)∣=diag⁡(q)\frac{1}{p}\sum_d\lvert\phi_d(\mathbf{q})\rangle\langle\phi_d(\mathbf{q})\rvert=\operatorname{diag}(\mathbf{q}), while Wq⊥W_{\mathbf{q}}^\perp adds to a uniform input independent noise of entropy H(q)H(\mathbf{q}). Here χ(Wq)\chi(W_{\mathbf{q}}) is the Holevo information of the BPQM message, which bounds how much information about the code symbol dd can be extracted from ∣ϕd(q)⟩\lvert\phi_d(\mathbf{q})\rangle. It attains its maximum log⁡p\log p only at the uniform distribution, q=u\mathbf{q}=\mathbf{u}, where the states are orthogonal and Perr(q)=0P_{\mathrm{err}}(\mathbf{q})=0. On the other side, I(Wq⊥)I(W_{\mathbf{q}}^\perp) is the information that the output Y=X+AY=X+A of the dual classical channel carries about its input XX. The proof below identifies this classical dual Wq⊥≡L(q)W_{\mathbf{q}}^\perp\equiv\mathcal{L}(\mathbf{q}) with the Gibbs reconstruction posterior law in § 7. Since χ+I=log⁡p\chi+I=\log p, the quantum message is fully informative exactly when the dual classical observation is uninformative: BPQM decodes the root with vanishing error precisely when tree reconstruction is impossible.

Proof of Theorem 4. To prove (54), we establish an algebraic equivalence between the BPQM message recursion defined in Eqs. (35) to (37) of § 5 and the reconstruction posterior distributional recursion defined in Eqs. (47) and (48) of § 7.

We prove the first identity in (54) by induction, using the identities (57) and (58) established above. Suppose the inductive hypothesis L(q(ℓ))=dη~(ℓ)\mathcal{L}(q^{(\ell)}) \mathrel{\mathop{=}\limits^{d}} \widetilde{\eta}^{(\ell)} at depth ℓ\ell. At ℓ=0\ell= 0 both sides equal e0e_0, since L(e0)=e0\mathcal{L}(e_0) = e_0. Assume L(q(ℓ))=dη~(ℓ)\mathcal{L}(q^{(\ell)}) \mathrel{\mathop{=}\limits^{d}} \widetilde{\eta}^{(\ell)}. One BPQM round (Figure 2) is an equality update at each child symbol followed by a parity update at the parent check. A BPQM symbol is a max-LINSAT constraint jtj_t and a BPQM check is a max-LINSAT variable ii, so these two updates should become the constraint stage and the variable stage of the reconstruction recursion, respectively. We verify this by lifting each update.

Equality update at symbol tt. By (35), vt(ℓ)=μ∗qt,1(ℓ)∗⋯∗qt,k−1(ℓ)v_t^{(\ell)} = \mu* q_{t,1}^{(\ell)} * \cdots* q_{t,k-1}^{(\ell)}, where the qt,h(ℓ)q_{t,h}^{(\ell)} are independent copies of q(ℓ)q^{(\ell)} coming from disjoint subtrees. By (57), L(vt(ℓ))\mathcal{L}(v_t^{(\ell)}) is the convolution of the independent lifts of μ\mu and of the qt,h(ℓ)q_{t,h}^{(\ell)}. By the inductive hypothesis, the convolution of the last k−1k-1 lifts has the law of GtG_t in (47), while L(μ)x=μUt−x\mathcal{L}(\mu)_x = \mu_{U_t-x} with Ut∼μU_t \sim\mu. Using the convolution convention of (29) and μa=wβ(a)/cβ\mu_a = w_\beta(a)/c_\beta from (43),

L(vt(ℓ))x=d∑w∈FpGt(w)μUt−x+w=e−β+(1−e−β)Γt(Ut−x)cβ,(60)\mathcal{L}(v_t^{(\ell)})_x \mathrel{\mathop{=}\limits^{d}} \sum_{w \in\mathbb{F}_p} G_t(w)\mu_{U_t-x+w} = \frac{e^{-\beta} + (1-e^{-\beta})\Gamma_t(U_t-x)}{c_\beta}, \tag*{(60)}

where the last step uses ∑wGt(w)1{s+w∈S}=Γt(s)\sum_w G_t(w)1\{s+w \in S\} = \Gamma_t(s). Up to the constant 1/cβ1/c_\beta, this is the likelihood contributed by constraint jtj_t in the reconstruction recursion.

Parity update at the parent check. The parent check is a variable ii with parent constraint j0j_0 and child constraints j1,…,jD−1j_1,\ldots,j_{D-1}. Its parity condition ∑jBjidj=0\sum_j B_{ji}d_j = 0 reads dj0=∑tαtdjtd_{j_0} = \sum_t \alpha_t d_{j_t} with αt=−Bjti/Bj0i=−γt\alpha_t = -B_{j_ti}/B_{j_0i} = -\gamma_t. Equations (36) and (37) relabel each input as νt=Rαtvt(ℓ)\nu_t = \mathcal{R}_{\alpha_t}v_t^{(\ell)} and then apply the parity rule D−2D-2 times. By the relabeling identity after (58), L(νt)z=L(vt(ℓ))−γtz\mathcal{L}(\nu_t)_z = \mathcal{L}(v_t^{(\ell)})_{-\gamma_t z}, and by (58) the parity updates lift to a normalized product:

L(q(ℓ+1))z=d∏t=1D−1L(vt(ℓ))−γtz∑y∈Fp∏t=1D−1L(vt(ℓ))−γty.\mathcal{L}(q^{(\ell+1)})_z \mathrel{\mathop{=}\limits^{d}} \frac{\prod_{t=1}^{D-1}\mathcal{L}(v_t^{(\ell)})_{-\gamma_t z}}{\sum_{y\in\mathbb{F}_p}\prod_{t=1}^{D-1}\mathcal{L}(v_t^{(\ell)})_{-\gamma_t y}}.

Substituting (60) with x=−γtzx=-\gamma_t z, the constants 1/cβ1/c_\beta cancel and each factor becomes e−β+(1−e−β)Γt(Ut+γtz)e^{-\beta}+(1-e^{-\beta})\Gamma_t(U_t+\gamma_t z). The UtU_t and GtG_t are independent across tt, and the γt\gamma_t are the coefficient ratios drawn from Λ\Lambda, exactly as in (48). Hence L(q(ℓ+1))=dη~(ℓ+1)\mathcal{L}(q^{(\ell+1)}) \mathrel{\mathop{=}\limits^{d}} \widetilde{\eta}^{(\ell+1)}, which completes the induction.

To show the second identity in (54), we apply (49) and the first identity, averaging over Λ∼q(ℓ)\Lambda\sim q^{(\ell)} given q(ℓ)q^{(\ell)},

Ψℓ+1p=E[L(q(ℓ))0]=E[qA(ℓ)]=E[∑a(qa(ℓ))2].\Psi_\ell+\frac{1}{p}=\mathbb{E}\left[\mathcal{L}(q^{(\ell)})_0\right]=\mathbb{E}\left[q_A^{(\ell)}\right]=\mathbb{E}\left[\sum_a\left(q_a^{(\ell)}\right)^2\right].

and ∑a(qa−1/p)2=∑aqa2−1/p\sum_a(q_a-1/p)^2=\sum_a q_a^2-1/p gives Ψℓ=E[∥q(ℓ)−u∥22]\Psi_\ell=\mathbb{E}\left[\lVert q^{(\ell)}-u\rVert_2^2\right].

We now prove the threshold equality (55). Write q^(b)=∑aqaωab\widehat{q}(b)=\sum_a q_a\omega^{ab} and mℓ(b)=E[∣q^(ℓ)(b)∣2]m_\ell(b)=\mathbb{E}[|\widehat{q}^{(\ell)}(b)|^2].

Parseval’s identity, the root convolution (39), and independence of its kk inputs give

Ψℓ=1p∑b≠0mℓ(b),E[∥μroot(ℓ)−u∥22]=1p∑b≠0∣μ^(b)∣2mℓ(b)k.(61)\begin{aligned} \Psi_{\ell} &= \frac{1}{p}\sum_{b\ne0}m_{\ell}(b),\\ \mathbb{E}\left[\left\|\mu_{\mathrm{root}}^{(\ell)}-u\right\|_2^2\right] &= \frac{1}{p}\sum_{b\ne0}\left|\widehat{\mu}(b)\right|^2m_{\ell}(b)^k. \tag*{(61)} \end{aligned}

For β>0\beta>0, each μ^(b)\widehat{\mu}(b), b≠0b\ne0, is nonzero: it is a positive multiple of ∑a∈Sωab\sum_{a\in S}\omega^{ab}, which cannot vanish for prime pp and a nonempty proper SS. Indeed, the minimal polynomial of ωb\omega^b is 1+X+⋯+Xp−11+X+\cdots+X^{p-1}, whereas ∑a∈SXa\sum_{a\in S}X^a is not a multiple of it. The two nonnegative finite sums therefore vanish together as ℓ→∞\ell\to\infty. The error function (33) is continuous and vanishes only at uu, so the compactness of the probability simplex gives

lim⁡ℓ→∞Perr(ℓ)=0⟺Ψ∞=0.(62)\lim_{\ell\to\infty}\mathcal{P}_{\mathrm{err}}^{(\ell)}=0 \quad\Longleftrightarrow\quad\Psi_{\infty}=0. \tag*{(62)}

At β=0\beta=0, μ=u\mu=u and both conditions hold directly. This proves the threshold equality (55). Finally, for any fixed β<βdyn\beta<\beta_{\mathrm{dyn}}, we have Ψ∞=0\Psi_{\infty}=0, which by the second identity in (54) is exactly the hypothesis E∥q(ℓ)−u∥22→0\mathbb{E}\left\|q^{(\ell)}-u\right\|_2^2\to0 of Corollary 3. That corollary yields the polynomial-time coherent Gibbs sampling statement.

Corollary 5 (Information monotonicity in inverse temperature). Fix (k,D,p,S,Λ)(k,D,p,S,\Lambda) as in Definition 2. For every depth ℓ≥0\ell\ge0, the reconstruction information Iℓ(β)I_{\ell}(\beta) in (45) is nondecreasing in β≥0\beta\ge0. The same holds for its limit as ℓ→∞\ell\to\infty.

Proof. Write ss for the uniform distribution on SS, and uu for the uniform distribution on Fp\mathbb{F}_p. The physical channel vector in (43) satisfies

μβ=(1−tβ)u+tβs,tβ=r(1−e−β)r+(p−r)e−β,r=∣S∣.\mu_{\beta}=(1-t_{\beta})u+t_{\beta}s,\qquad t_{\beta}=\frac{r(1-e^{-\beta})}{r+(p-r)e^{-\beta}},\qquad r=|S|.

Since tβt_{\beta} increases with β\beta, for 0≤β1<β20\le\beta_1<\beta_2 we may set a=tβ1/tβ2∈[0,1]a=t_{\beta_1}/t_{\beta_2}\in[0,1] and ν=ae0+(1−a)u\nu=ae_0+(1-a)u. Convolution with uu gives uu, so

μβ1=μβ2∗ν.\mu_{\beta_1}=\mu_{\beta_2}*\nu.

The equality rule (30) therefore gives

Veq(∣ϕd(μβ2)⟩⊗∣ϕd(ν)⟩)=∣ϕd(μβ1)⟩⊗∣0⟩.V_{\mathrm{eq}}\left(\lvert\phi_d(\mu_{\beta_2})\rangle\otimes\lvert\phi_d(\nu)\rangle\right) =\lvert\phi_d(\mu_{\beta_1})\rangle\otimes\lvert0\rangle.

Thus, given the physical output at β1\beta_1, we can append ∣0⟩\lvert0\rangle, apply Veq†V_{\mathrm{eq}}^\dagger, and discard the second system to obtain exactly the output at β2\beta_2, without knowing the codeword symbol dd.

Consider the quantum combining tree dual to the depth-ℓ\ell reconstruction observation, and let χℓ(β)\chi_{\ell}(\beta) denote its Holevo information, including the heralded labels. Apply the above operation to each physical output, keeping the code constraints fixed. This converts the entire quantum observation at β1\beta_1 into the observation at β2\beta_2. The BPQM representation retains all information about its input: equality combining is a unitary compression, while at a parity node averaging the child symbols with fixed sum removes coherences between distinct herald outcomes, so retaining the herald label loses no information. Applying the data processing inequality therefore gives χℓ(β1)≥χℓ(β2)\chi_{\ell}(\beta_1)\ge\chi_{\ell}(\beta_2). By the finite-depth posterior correspondence proved above and (59), averaging over the herald labels and known tree data gives

Iℓ(β)=log⁡p−χℓ(β).I_{\ell}(\beta)=\log p-\chi_{\ell}(\beta).

Hence Iℓ(β1)≤Iℓ(β2)I_{\ell}(\beta_1)\le I_{\ell}(\beta_2). Taking ℓ→∞\ell\to\infty proves the limiting statement.

Example: Binary case. For p=2p=2 with S={0}S=\{0\}, the physical channel and its overlap are

μj=(1,e−β)1+e−β,η=μj,0−μj,1=tanh⁡(β/2).(63)\boldsymbol{\mu}_j=\frac{(1,e^{-\beta})}{1+e^{-\beta}},\qquad\eta=\mu_{j,0}-\mu_{j,1}=\tanh(\beta/2). \tag*{(63)}

In this case the posterior magnetization, meaning its probability of 0 minus its probability of 1, is

M=L(q)0−L(q)1=(−1)A(q0−q1),E[M∣q]=(q0−q1)2.(64)M=\mathcal{L}(\mathbf{q})_0-\mathcal{L}(\mathbf{q})_1=(-1)^A(q_0-q_1),\qquad\mathbb{E}[M\mid q]=(q_0-q_1)^2. \tag*{(64)}

Averaging this magnetization is therefore equivalent to tracking the mean-square quantum overlap. The factor of two in (63) follows from our convention that β\beta multiplies the number of violated constraints; the spin-coupling convention uses β/2\beta/2.

By Eqs. (54) and (64), 2Ψℓ=E[(q0(ℓ)−q1(ℓ))2]2\Psi_{\ell}=\mathbb{E}[(q_0^{(\ell)}-q_1^{(\ell)})^2]. With η=tanh⁡(β/2)\eta=\tanh(\beta/2), (61) and the binary specialization of (33) yield

η24(2Ψℓ)k≤Perr(ℓ)≤η22(2Ψℓ)k.(65)\frac{\eta^2}{4}(2\Psi_{\ell})^k\le P_{\mathrm{err}}^{(\ell)}\le\frac{\eta^2}{2}(2\Psi_{\ell})^k. \tag*{(65)}

To obtain these bounds, use u/2≤1−1−u≤uu/2\le1-\sqrt{1-u}\le u for 0≤u≤10\le u\le1 on the squared root overlap.

Computational Experiments

In the preceding sections we have obtained a rigorous proof that Regev+BPQM efficiently produces coherent Gibbs samples for every β<βdyn\beta<\beta_{\mathrm{dyn}} for average-case DD-regular max-kk-LINSAT. It has been conjectured [18, 25, 10, 36] that classical Markov chain methods using single-symbol updates to sample the Gibbs distribution encounter slow mixing at inverse temperatures above the reconstruction threshold βdyn\beta_{\mathrm{dyn}}. This conjecture suggests that widely-used optimization methods such as simulated annealing and Glauber dynamics should fail efficiently reach temperatures below 1/βdyn1/\beta_{\mathrm{dyn}}. In this section, we perform some computer experiments to test this conjecture. Everything reported in the preceding sections, showing the equivalence between the lowest temperature reachable by Regev+BPQM and βdyn\beta_{\mathrm{dyn}} was mathematically rigorous. Everything in this section, regarding the equivalence between the lowest energy efficiently reachable by simulated annealing and the expected energy at βdyn\beta_{\mathrm{dyn}} is purely empirical.

Note that βdyn\beta_{\mathrm{dyn}} should not be regarded as a computational hardness threshold in all parameter regimes. In [36] it was shown that for sufficiently large kk and DD, a variant of Prange’s algorithm can sample at temperatures below 1/βdyn1/\beta_{\mathrm{dyn}} in polynomial time. Nevertheless, at small kk and DD, simulated annealing is difficult to beat in practice and we are not aware of any counterexample disproving the notion that βdyn\beta_{\mathrm{dyn}} does represent the classical computational hardness barrier at sufficiently small kk and DD.

In what follows, we report on computational experiments for DD-regular max-kk-LINSAT over an alphabet of size pp with target sets of size rr. Thus, we explore instances across a four-dimensional parameter space. For a given choice of (k,D,p,r)(k,D,p,r), we can compute the corresponding value of βdyn\beta_{\mathrm{dyn}} and the resulting expected fraction of constraints satisfied in the Gibbs distribution. We then compare this against the satisfaction fraction achieved by simulated annealing with a large number of sweeps and optimized hyperparameters. Remarkably, we find that throughout the entire four-dimensional parameter region we study, the discrepancy between these two numbers is on average only 0.58 percentage points and at most 2.8 percentage points. Being subject to finite-size effects and statistical error bars, our computer experiments cannot be definitive. Nevertheless, we consider it unlikely that the consistently close agreement of these satisfaction fractions, as they trace out a complicated function on a four dimensional space, is coincidental. In [26] and [22], it was previously observed that Regev+BPQM closely matches the performance of simulated annealing. However, the reason behind this remained a mystery prior to the present work.

Instance ensemble. For the computational experiments, take the common target set in Definition 2 to be Sr={0,1,…,r−1}S_r = \{0,1,\ldots,r-1\}, with independent uniform offsets τa\tau_a and targets Fa=τa+SrF_a = \tau_a + S_r. Thus row aa is satisfied when

(Bx−τ)a∈Sr.(66)(Bx-\tau)_a \in S_r. \tag*{(66)}

The Tanner graph is sampled uniformly from the simple (k,D)(k,D)-regular ensemble. For each variable, we choose its coefficients for the DD incident constraints according to the law Λperm\Lambda_{\mathrm{perm}}. The parameter grid is

p∈{2,3,5,7,11,13},3≤k<D≤8,1≤r<p,(67)p \in\{2,3,5,7,11,13\}, \qquad3 \le k < D \le8, \qquad1 \le r < p, \tag*{(67)}

which contains 525 settings. All finite-graph calculations use n=6720n = 6720 optimization variables. For an assignment x\mathbf{x}, write

e(x)=E(x)m(68)e(\mathbf{x}) = \frac{E(\mathbf{x})}{m} \tag*{(68)}

for its fraction of violated constraints. We restrict the comparison to the 252 settings for which the density-evolution calculation detected a finite reconstruction threshold. Note that on the tree, the residual for the jj-th constraint Uj=(Bx−τ)jU_j = (B\mathbf{x}-\boldsymbol{\tau})_j follows the distribution μ\mu in (43). At β=βdyn\beta= \beta_{\mathrm{dyn}}, the expected fraction of violated constraints on the tree is thus

edyn=(p−r)e−βdynr+(p−r)e−βdyn,(69)e_{\mathrm{dyn}} = \frac{(p-r)e^{-\beta_{\mathrm{dyn}}}}{r+(p-r)e^{-\beta_{\mathrm{dyn}}}}, \tag*{(69)}

which is also the equilibrium energy of finite random instances at any temperature in the replica-symmetric phase.

Numerical method for determining βdyn\beta_{\mathrm{dyn}}. We use the operational definition βdyn\beta_{\mathrm{dyn}} in (50) in terms of the reconstruction distributional recursion. In practice, we determine βdyn(k,D,q,Sr,Λperm)\beta_{\mathrm{dyn}}(k,D,q,S_r,\Lambda_{\mathrm{perm}}) via the following planted density evolution algorithm:

  1. Initialize a pool of MM samples at the planted value, i.e., set {η~μ(0)=e0:μ=1,2,…,M}\{\widetilde{\eta}^{(0)}_\mu= e_0 : \mu= 1,2,\ldots,M\}. By default, take M=104M = 10^4.

  1. For each step of the recursion (48), replace the pool by MM fresh samples as follows: For each sample, draw one DD-tuple from Λperm\Lambda_{\mathrm{perm}} and form all D−1D-1 child-to-parent ratios γt\gamma_t; then per constraint draw k−1k-1 children uniformly from the current pool and a noise UtU_t. Convolve the children by multiplying length-pp FFTs, and accumulate the logarithm of the bracket over the D−1D-1 constraints before exponentiating and normalizing. One sweep costs O(MDkplog⁡p)O(MDkp\log p).

  1. Track the order parameter Ψℓ\Psi_\ell. Declare the trivial fixed point reached when it drops below 0.01(1−1/p)0.01\left(1-1/p\right), and a nontrivial one when the local slope sj=−log⁡(Ψℓj/Ψℓj−1)/log⁡(ℓj/ℓj−1)s_j=-\log\left(\Psi_{\ell_j}/\Psi_{\ell_{j-1}}\right)/\log\left(\ell_j/\ell_{j-1}\right), measured across geometric checkpoints ℓj≈24⋅2j/2\ell_j\approx24\cdot2^{j/2}, falls below 0.050.05 twice in a row while Ψℓ>0.05(1−1/p)\Psi_\ell>0.05\left(1-1/p\right). Locate the threshold by bisection in β\beta.

Annealing experiments and comparison with reconstruction prediction. We ran two sets of simulated annealing experiments, with different sweep counts. The high-sweep-count simulated-annealing calculation uses 32 graph instances per setting, one restart, 14.4×10614.4\times10^6 sweeps with a calibrated linear-β\beta schedule, and greedy coordinate updates to a one-coordinate local optimum. The low-sweep-count calculation uses 144,000 sweeps and reports the best state encountered. These two budgets differ by a factor of 100.

In both simulated-annealing protocols, the reported violation fraction closely follows edyne_{\mathrm{dyn}} across the comparison grid; see Figure 4. The absolute discrepancies are summarized in Table 1. Every setting in both calculations is within three percentage points of edyne_{\mathrm{dyn}}.

(a) (a) 14.4×10614.4\times10^6 sweeps.

(b) (b) 144,000 sweeps.

Figure 4. Figure 4: Simulated-annealing violation fractions versus the tree-based reference edyne_{\mathrm{dyn}} in (69). (a) Violation fraction reached by the high-sweep-count protocol. (b) Best violation fraction found by the low-sweep-count protocol. Both panels show the same 252 parameter settings with detected finite reconstruction thresholds; in panel (a), each point is a mean over 32 graph instances. The dashed line is equality; dotted and dash-dotted lines mark one- and two-percentage-point discrepancies. Reducing the sweep count by a factor of 100 shifts the typical result upward by about one percentage point but preserves its dependence on the reconstruction prediction.

annealing protocolsettingsmedianmeanmaximum
high-sweep-count SA2520.2730.5822.815
low-sweep-count SA2520.8730.9202.158

Table 1. Absolute discrepancy between the reported simulated-annealing violation fraction and the tree-based reference edyne_{\mathrm{dyn}}, in percentage points of violated constraints. The two protocols use 14.4×10614.4 \times10^{6} and 144,000 sweeps, respectively.

The agreement is more specific than a high correlation between two nearly monotone quantities. The discrepancies remain small in absolute units across the four-dimensional grid (k,D,p,r)(k,D,p,r). The high-sweep-count calculation is within two percentage points at 233 of the 252 settings; the low-sweep-count calculation is within two points at 249 settings.

Interpretation. Across the settings with a detected finite threshold, the reconstruction-based energy scale closely predicts the energies reached by simulated annealing at both tested budgets. This empirical agreement complements the tree-threshold identity in Theorem 4. The finite-size optimization measurements do not establish convergence to the Gibbs distribution or a limit on what longer runs or other classical algorithms can achieve.

Acknowledgments

We thank Christophe Piveteau and Ruslan Shaydulin for sharing quantum density evolution data which provided some of the first hints from which this paper grew. We thank Mark Sellke and Noah Shutty for useful discussions. LZ is supported by Department of Navy Award No. N000142612399 issued by the Office of Naval Research.

AI Disclosure: We used Claude, Gemini, and ChatGPT to write code, analyze data, develop proofs from our sketches, and assist with drafting and editing the manuscript. All aspects of the project were overseen by the authors, and we take responsibility for the correctness of all claims.

References

  1. [1]Arka Adhikari, Christian Brennecke, Changji Xu, and Horng-Tzer Yau. Spectral gap estimates for mixed p-spin models at high temperature. Probability Theory and Related Fields, 189(3-4):879–907, March 2024. doi:10.1007/s00440-024-01261-9.DOI
  2. [2]Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana, Dylan Herman, Guneykan Ozgul, Ruslan Shaydulin, Shreehari Sureshbabu, and Jacob Watkins. No exponential quantum advantage for decoded quantum interferometry with local quantum decoders, 2026. In preparation.arxiv.org/abs/2611.12718
  3. [4]Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. Universality of spectral independence with applications to fast mixing in spin glasses. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 5029–5056. Society for Industrial and Applied Mathematics, January 2024. doi:10.1137/1.9781611977912.181.DOI
  4. [5]Ahmed El Alaoui. Near-optimal shattering in the Ising pure p-spin and rarity of solutions returned by stable algorithms. Stochastic Processes and their Applications, 192:104792, 2026. doi:10.1016/j.spa.2025.104792.DOI
  5. [6]Dorit Aharonov and Oded Regev. Lattice problems in NP ∩ coNP. Journal of the ACM (JACM), 52(5):749–765, 2005.
  6. [7]Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 20–29, 2003. arXiv:quant-ph/0301023.DOI
  7. [8]S. Brandsen, Avijit Mandal, and Henry D. Pfister. Belief propagation with quantum messages for symmetric classical-quantum channels. arXiv:2207.04984, 2022. arXiv:2207.04984.arxiv.org/abs/2207.04984
  8. [10]Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Sampling from mean-field gibbs measures via diffusion processes. Probability and Mathematical Physics, 6(3):961–1022, 2025. doi:10.2140/pmp.2025.6.961.DOI
  9. [11]Silvio Franz and Giorgio Parisi. Recipes for metastable states in spin glasses. Journal de Physique I, 5(11):1401–1415, 1995. doi:10.1051/jp1:1995201.DOI
  10. [12]Zhe Hou, Jingcheng Liu, and Yixiao Yu. Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model. arXiv:2610.09882, 2026. arXiv:2610.09882.arxiv.org/abs/2610.09882
  11. [13]Svante Janson. The probability that a random multigraph is simple, II. arXiv:1307.6344, 2013.arxiv.org/abs/1307.6344
  12. [14]Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, and Ryan Babbush. Optimization by decoded quantum interferometry. Nature, 646(8086):831–836, 2025. arXiv:2408.08292.DOI
  13. [15]Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169–188, 1986. doi:10.1016/0304-3975(86)90174-X.DOI
  14. [17]Robin Kothari and Ryan O’Donnell. Mean estimation when you have the source code; or, quantum Monte Carlo methods. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 1186–1215. Society for Industrial and Applied Mathematics, January 2023. doi:10.1137/1.9781611977554.ch44.DOI
  15. [18]T. R. Kirkpatrick and D. Thirumalai. Dynamics of the structural glass transition and the p-spin—interaction spin-glass model. Phys. Rev. Lett., 58:2091–2094, May 1987. doi:10.1103/PhysRevLett.58.2091.DOI
  16. [19]Marc Mézard and Andrea Montanari. Reconstruction on trees and spin glass transition. Journal of Statistical Physics, 124(6):1317–1350, 2006.
  17. [20]Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A, 471(2181):20150301, 2015. doi:10.1098/rspa.2015.0301.DOI
  18. [21]Avijit Mandal and Henry D. Pfister. Belief propagation with quantum messages for symmetric q-ary pure-state channels. arXiv:2601.21330, 2026.arxiv.org/abs/2601.21330
  19. [22]Avijit Mandal, Christophe Piveteau, Joseph M. Renes, and Henry D. Pfister. Quantum message passing convergence and vanishing block-error probability for random LDPC codes. arXiv:2609.05857v2, 2026.arxiv.org/abs/2609.05857
  20. [23]Andrea Montanari and Federico Ricci-Tersenghi. On the nature of the low-temperature phase in discontinuous mean-field spin glasses. The European Physical Journal B, 33(3):339–346, 2003. arXiv:cond-mat/0301591. doi:10.1140/epjb/e2003-00174-7.DOI
  21. [25]Andrea Montanari and Guilhem Semerjian. On the dynamics of the glass transition on Bethe lattices. Journal of Statistical Physics, 124:103–189, 2006. doi:10.1007/s10955-006-9103-1.DOI
  22. [26]Christophe Piveteau. Comment on ”optimization using locally-quantum decoders”. SciRate, May 2026. Comment on arXiv:2604.24633. URL: https://scirate.com/arxiv/2604.24633#3084.
  23. [27]Christophe Piveteau, Yihui Quek, and M. Franco Garrido. Gibbs state preparation through quantum decoding. arXiv:2610.03566, 2026.arxiv.org/abs/2610.03566
  24. [28]Christophe Piveteau and Joseph M. Renes. Quantum message-passing algorithm for optimal and efficient decoding. Quantum, 6:784, 2022. doi:10.22331/q-2022-08-23-784.DOI
  25. [29]Oded Regev. Quantum computation and lattice problems. SIAM Journal on Computing, 33(3):738–760, 2004.
  26. [30]Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009.
  27. [31]Joseph M. Renes. Belief propagation decoding of quantum channels by passing quantum mes-sages. New Journal of Physics, 19(7):072001, 2017.
  28. [32]Joseph M. Renes. Duality of channels and codes. IEEE Transactions on Information Theory, 64(1):577–592, 2018. arXiv:1701.05583. doi:10.1109/TIT.2017.2754921.DOI
  29. [33]Rolando D. Somma, Sergio Boixo, Howard Barnum, and Emanuel Knill. Quantum simulations of classical annealing processes. Physical Review Letters, 101(13):130504, 2008. doi:10.1103/PhysRevLett.101.130504.DOI
  30. [35]Pawel Wocjan, Chen-Fu Chiang, Daniel Nagaj, and Anura Abeyesinghe. Quantum algorithm for approximating partition functions. Physical Review A, 80(2):022340, 2009. doi:10.1103/PhysRevA.80.022340.DOI
  31. [36]Leo Zhou, Noah Shutty, Mark Sellke, and Stephen P. Jordan. Gibbs sampling in the shattered phase by decoded quantum interferometry. arXiv:2609.40345, 2026. arXiv:2609.40345.arxiv.org/abs/2609.40345

Paper details

vlnc:W_x9sams7n
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Claude, Gemini (multiple versions), ChatGPT

View statement
Looking for related papers…
Contents