In this paper
AbstractIntroductionSummary of ResultsRegev's ReductionBelief Propagation with Quantum MessagesQuantum Density EvolutionFrom Tree Decoding to Coherent Gibbs SamplingThe Reconstruction ThresholdProof of the Main TheoremComputational ExperimentsAcknowledgmentsReferencesWorksPhysics 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 -regular max--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 -regular max--XORSAT and its larger-alphabet generalization to -regular max--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 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 -regular max--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 -regular max--LINSAT. An instance of -regular max--LINSAT consists of variables from , contained in constraints. For a given assignment to the variables we can assign a corresponding energy , equal to the number of violated constraints. Given an inverse temperature this defines a Gibbs distribution
Here, we use Regev’s reduction together with BPQM to prepare the state
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 tending to zero with high probability as , for each fixed strictly below the decoding threshold.
Measuring the state in the computational basis yields classical Gibbs sampling (to within total variation distance) at inverse temperature . At low temperature the expected energy 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 is a more powerful primitive than classical Gibbs sampling at inverse temperature [7, 20, 17], which in turn is a more powerful primitive than finding an individual solution at energy [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 in the associated statistical physics model of random max--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 , 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 case, however, existing fast-mixing guarantees for Glauber dynamics only apply at inverse temperatures far smaller than 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 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 be a finite field and let . For each let be an arbitrary subset of which yields a corresponding constraint . Given and , the max-LINSAT problem is to find satisfying as many as possible of these constraints.
For simplicity, we restrict to be prime in this work. In the case of and , one recovers max-XORSAT. An instance of max-LINSAT corresponds to the energy function given by
This in turn defines a classical Gibbs distribution via (1) and a coherent Gibbs sampling problem via (2). At , the energy function (3) is equivalent to the classical Ising model.
The special case of max-LINSAT where each constraint contains exactly variables is called max--LINSAT. That is, in max--LINSAT each row of the matrix contains exactly nonzero coefficients. If each variable is contained in exactly constraints, i.e., each column of contains exactly nonzero coefficients, then the instance is said to be -regular. When and , the problem is equivalent to max--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 are nonzero, what values in these nonzero entries take, and what subsets of we take as our targets . We address these in turn.
To generate an instance of -regular max--LINSAT we start by choosing a matrix uniformly at random from all -valued matrices with exactly ones in each column and ones in each row. The ones represent the locations of nonzero entries in our final matrix . We can visualize by a corresponding bipartite graph with one part of vertices that correspond to the constraints in our max-LINSAT instance and a second part of vertices that correspond to the variables. A constraint vertex in the first part is connected by an edge to a variable vertex in the second part if and only if , i.e., constraint contains variable . Following the terminology from coding theory, we refer to this as the Tanner graph. Given , we next construct by filling in each nonzero entry with a choice from , followed by choosing target sets .
Definition 2 (Random regular max-LINSAT). Fix a prime , integers , a nonempty proper subset , and an exchangeable probability law on . Hold these parameters fixed as along values for which is an integer. Then a max-LINSAT instance is drawn from the random regular ensemble as follows. First choose as above; then is constructed by taking and filling the nonzero entries in each column one tuple drawn from the law . To obtain , we first choose offsets independently and uniformly at random from , and set .
Requiring to be exchangeable, which means the probability law is invariant under permuting the variables, is a proof convenience. Examples of exchangeable include:
: Choose each coefficient independently and uniformly at random from .
: Fix a primitive element , and choose the coefficients to be a uniformly random permutation of .
In particular, the choice 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 . The associated infinite tree has variable degree and constraint degree . Its free-boundary Gibbs distribution can be generated by a broadcast: choose the root symbol uniformly from , then at each constraint jointly generate its child symbols from the conditional Gibbs distribution given the parent. Satisfying assignments to that constraint receive weight , and violating assignments receive weight . 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 , even as . At high temperature, this distant boundary loses all information about the root. At sufficiently low temperature, information may survive. Writing for the root, for the boundary, and for the known tree data, we define the reconstruction threshold in inverse temperature as
The notation 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 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 with the LDPC code . Its symbols have degree and its checks have degree , 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 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 and :
Theorem 1 (Regev+BPQM reaches reconstruction, informal). Fix any choice of as in Definition 2. Then the reconstruction threshold on the associated tree equals the BPQM decoding threshold on the dual tree:
For every , 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 , with vanishing trace-distance error with high probability as .
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 , 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 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 -regular max--LINSAT over an alphabet of size with and target set . We perform our experiments on random instances with variables, across an exhaustive grid of ensemble parameters for all with ranging across all primes up to 13 and . Among its 525 settings, density evolution detects finite thresholds at 252, which we subsequently use for simulated annealing experiments. On this region of the four-dimensional parameter space defined by 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 ( sweeps) and long anneals ( 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 () for all max-LINSAT ensembles? This would give a matching classical polynomial-time sampling guarantee below .
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 for the special case of max-XORSAT, but those algorithms underperform compared to Regev+BPQM for the small regime we consider here. A quantum algorithm that Gibbs samples at over wider regimes of 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 defines two codes:
Their normalized code states are
It is easy to verify that and , where QFT denotes the unitary Fourier transform over .
Now suppose that, for an envelope function , we wish to construct the state
where
The Fourier convolution theorem gives
where
is the unitary Fourier transform of . The ideal form of Regev’s reduction proceeds as follows; § 6 gives the agreement test and error bound for an approximate decoder.
Prepare
where . The first register is efficiently preparable for any linear code , while the second is normalized by Parseval’s identity. For , its amplitudes factorize over the coordinates, so it is a product state and hence easy to prepare.
Reversibly add the content of the first register to the content of the second register.
From the content of the second register, coherently infer the content of the first register. This is the quantum decoding problem: given the state
which we interpret as a codeword corrupted with a coherent superposition of errors , infer . The aim is to erase the first register and uncompute the decoder’s work registers. The normalized target of this step is
Discard the register and perform an inverse quantum Fourier transform. By (8) and (10) this yields the desired final state.
We next observe how this applies to coherent Gibbs sampling. Every has exactly preimages, all with the same energy. Consequently, the normalized code state corresponding to (2) is
Gaussian elimination gives a particular preimage of each codeword and a basis for . Preparing a uniform superposition over that kernel implements the isometry
A reversible linear-algebra circuit extends this map to the full registers. Applying it to (17) gives . Thus no full-column-rank assumption is needed; when , the map reduces to the inverse encoding .
By (1) and (6) we can rewrite (17) as
where, for and ,
Counting the preimages of each codeword gives . Thus (10) specializes to
where is the unitary Fourier transform of . Since (20) factorizes, applying (11) gets
where the individual components (21) are Fourier transformed to yield
The amplitudes in (24) define the error model for the quantum decoding problem that we must solve, where the -th codeword symbol is sent through the noise channel
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 from the quantum state in (14)
BPQM recovers by estimating each code symbol. It estimates a code symbol 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 -ary pure-state channel formulation of [21], Sec. II-C, Eq. (1), with normalized eigenvalues and a fixed change from their Fourier basis to the computational basis. Let . A message about a symbol has a classical component specified by a probability vector and a quantum component in the state
The Gram matrix of these states has Fourier eigenvalues [21 Lemmas 5–7]. The normalized eigenvalues specify the overlaps among the possible states; for example, uniform gives mutually orthogonal states and perfect distinguishability.
We now show how the quantum message (26) arises in Regev’s reduction. For fixed , the received state in Regev’s reduction (22) is a product of the normalized single-symbol received states
Define the probability vector by normalizing the squared amplitudes of . Using (21), we obtain
Applying the inverse Fourier transform to the received state then gives the message state in (26) with and :
Equality rule. Suppose two incoming messages concern the same unknown symbol . The goal of the equality rule1 is to compress their two quantum systems into one qudit without losing any information about . This is possible because, conditioned on the classical messages and , the possible joint pure states span a subspace of dimension at most inside the -dimensional two-qudit space. A unitary can therefore put all dependence on into one qudit while leaving the other in a fixed state.
To see the compression explicitly, expand the product state and group terms by :
The vectors are independent of and have disjoint computational-basis supports for distinct , so they are mutually orthogonal. Their squared norms give the circular-convolution update of [21 Lemma 13], expressed in normalized eigenvalues:
We can therefore choose a unitary, depending only on and , that maps each normalized vector to . Equivalently,
Applying this unitary to the expanded input state gives
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 . The classical update is deterministic.
Parity rule. Suppose two incoming messages concern unknown symbols and , respectively. The goal of the parity rule is to combine them into a message about their sum , which is their parity when . 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 . Apply modular subtraction, , which is a CNOT for . Writing , the resulting state is
Measuring the second qudit now selects a value of . For each fixed input pair , the factor is then only a global phase, and the first qudit has exactly the form of a message about . The probability of outcome and the normalized classical description of this message are
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 . Although the outcome probabilities are independent of the input symbols, we retain because it specifies which classical description 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 in (6), the Tanner graph has symbol nodes and check nodes enforcing . Symbols have degree and checks have degree . 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 has its own received quantum system, i.e., a message 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 whose parent is symbol , the child messages concern the other symbols in that check. The check equation expresses the parent symbol as
To apply the parity rule repeatedly to obtain one message about , we first relabel each child’s message to describe its term in this sum: For , a relabeling is implemented by and .
At a symbol node , 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 child-check messages and sends the result to its parent check; the root combines all 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]).

Figure 1. BPQM updates toward the root. (Top) At a symbol node, equality rules combine child-check messages with the symbol’s own noise channel output . (Bottom) At a check node, parity rules combine 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 , together with the classical message . The probability vector is known from the classical outcome record and describes the possible states of this final qudit. To estimate , apply the pretty good measurement, which achieves error probability [21 Sec. II-E and Lemma 9]
Averaging over the classical outcomes, the minimum error for this local decoding problem is therefore
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 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 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 index rounds toward the root. Write and 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.

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 may vary between symbols, as in (28). We suppress node and edge indices in the local recursions below: 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
For a check constraint , relabel each incoming message as in § 4, setting . Conditional on these incoming vectors, repeated application of the parity rule (32) gives a distribution over outgoing vector . In particular, we set and sample the string with probability
then the associated outgoing vector is
We initialize
Since , each initial symbol message has classical part , using that symbol’s physical channel vector. Let denote the distribution of the classical part of a check-to-symbol message under this ensemble. So the initialization gives .
At the root, the equality rule combines the physical channel with all check messages. The classical part of the resulting message and the average decoding error are
Here is given by (33), and the expectation averages over parity outcomes and, when applicable, the ensemble. The decoding threshold concerns whether as . 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 and check degree . 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 , the radius- neighborhood of all but 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 [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 such symbols, while the code’s minimum distance is linear in , 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 be drawn from the ensemble of Definition 2. At any fixed , let be the channel vector in (28) for the common target set . Suppose the recurrence in § 5 satisfies . Then, for a suitable , the BPQM decoder with erasure recovery of [22 Theorem 30] runs in polynomial time and decodes a uniformly chosen codeword of with ensemble-average error probability tending to zero as increases.
Proof. The result follows from [22 Theorem 30] with two differences to address: we allow a more general coefficient distribution , and we disallow parallel edges. Their code has symbols, symbol degree , check degree , and alphabet size in our notation.
Coefficient distribution. First use the random graph of [22], generated by uniformly matching the edge ends on each side of the bipartite Tanner graph, and independently assign a coefficient tuple with law to the 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- decay of the tree decoding error, under the assumption .
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 symbols with this property reaches at most checks. We take a union bound over the choice of the symbols and of checks containing all their neighbors; the probability that all edge ends of these symbols are matched into those checks is at most . For sufficiently small fixed , this gives
where the second inequality uses and . Hence the minimum distance exceeds 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 denote the decoder’s block-error probability for a graph drawn by the matching construction of [22 Sec. 4.1], with coefficient law as above. These arguments give at a suitable .
No parallel edges. Let be the event that the matched graph has no parallel edges. Each labeled simple -regular bipartite graph arises from exactly matchings, since the edge ends at each vertex can be assigned to its incident edges in any order. Conditional on , the support is therefore uniform among the graphs in Definition 2. The column tuples remain independent because depends only on the matching, and exchangeability preserves their law when ordered by neighboring symbols. This gives precisely our ensemble, including both and .
For fixed , , [13 Theorem 5.1]. Writing for the decoder’s block-error probability on our ensemble, we conclude
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 is a random translate of a fixed set . We use the same decoder for every choice of shifts: it decodes the channel associated with , while the shifts are implemented by phase gates in Regev’s reduction. According to (28), the unshifted channel has parameters
We will apply Proposition 2 to solve the quantum decoding problem associated to this channel. The random shifts allow us to apply [SMR+26, Lemma 4] to convert quantum decoding error to Regev’s reduction error.
Corollary 3 (Coherent Gibbs sampling). Let as in Definition 2. Fix an inverse temperature . Suppose the check-to-symbol messages of the density evolution in § 5, for this law and the channel (41), satisfy , where . Then, with probability over , Regev’s reduction with the decoder of Proposition 2 prepares a state within trace distance of the coherent Gibbs state in (2), in polynomial time and with failure probability , as . This applies to both and .
Proof. The hypothesis and (35) imply . By Proposition 2, the decoder’s block-error probability satisfies .
Let be the normalized received state (14) with every target set equal to . Write the coherent decoder’s action as
where each unnormalized contains the received system and all other decoder registers. Following [SMR+26, Sec. 7.2], apply the phase , apply the decoding unitary , and test whether the estimate agrees with register . Report failure otherwise. The test accepts with probability . On the accepting branch, subtracting the estimate from the codeword register gives
Now reverse , apply to the received register, and apply the inverse Fourier transform. To see what these steps do, consider an ideal decoder, , for which reversing maps back to . Write for the envelope (20) with every replaced by , so that . Since , (11) gives
Omitting the work registers,
Up to normalization, this is in (22), so the inverse Fourier transform gives the target state . For nonzero , denote the normalized output, including all work registers, by . The error analysis of [SMR+26, Lemma 4] gives
The left-hand side is the expected squared trace distance between these pure states. Averaging over and applying Markov’s inequality gives trace-distance error and failure probability , with probability over .
In § 8, we will show that the convergence condition in Corollary 3 corresponds precisely to the reconstruction threshold on the inverse temperature .
The Reconstruction Threshold
In many random optimization problems, spin glass theory predicts a dynamical transition that occurs at a critical inverse temperature , which is determined by when there exists a nontrivial solution to the one-step replica-symmetry-breaking (1RSB) equation with Parisi parameter [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 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 and sends it through noisy channels to its children. Each child then transmits to the next generation in the same way. After 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 , the observer can still guess the root with a success probability that exceeds 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 constraints, and each constraint contains variables. A constraint acts as a channel from one parent variable to 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 .
We now specify the channel for which the broadcast generates our desired Gibbs distribution. Fix a nonempty proper accepting set , let , and write
For a constraint with parent variable and children , the probability of the child values, given the parent, is
To sample it, draw a residual , then choose the children uniformly subject to . All coefficients are nonzero, so there are exactly 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 ; 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 are fixed.
Definition 3 (Reconstruction threshold). For the broadcast (44), let be the uniform root symbol and the symbols observed at generation . The conditional mutual information retained about the root is
Reconstruction is possible at if . For a fixed accepting set and coefficient law, the reconstruction threshold is
with .
At , the children are uniform and independent of the parent, so the boundary carries no information about the root. Increasing makes the constraints more informative. Thus reconstruction fails below and succeeds above it.

Figure 3. The reconstruction problem. Each of the child constraints jointly generates child spins using (44). After broadcasting to depth , reveal the boundary and compute the posterior of by passing messages inward. The full-root problem includes all 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 , and in turn provide a more explicit definition of . The recursion is performed on a probability vector on , which we call a reconstruction message, whose entry denotes the posterior probability that the root differs from its “planted value” by , after rescaling by the coefficient on its parent constraint. More precisely, we draw a reference configuration from the Gibbs broadcast so that is the planted value at the root node ; if the inferred root variable is and its parent constraint is , then the error coordinate is . For its child constraints , write , with .
Let , the point mass at , corresponding to zero error at the generation. For each , draw one -tuple of coefficients from the given law and compute the coefficient ratios of the children relative to their parent. Here, for each , we choose the noise residual from (43), and independently draw the copies of as the child messages to obtain
where is the circular convolution in (29). The interpretation here is that the convolution 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 . Then the posterior message distribution at generation is
where is a normalization fixed by . To measure the information in the posterior about the root variable, we compare it against the uniform random guess by defining
Note is the excess success probability of guessing the root correctly by sampling from the posterior; in particular, .
Since a farther boundary is obtained by continuing the broadcast from a nearer one, is nonincreasing in due to the data processing inequality. As noted in [19], the limit exists and vanishes exactly when the mutual information vanishes. Thus, the reconstruction threshold (46) can be equivalently written as
Remarks.
We remark that the reconstruction information is nondecreasing in , making a genuine threshold. This enables us to locate the transition by scanning and bisecting. In Corollary 5 of § 8, we give a proof of this monotonicity using channel duality.
The formulation above recovers known recursions for Ising model/max-XORSAT as a special case (see e.g., [36]). At , write for the posterior magnetization. Then (48) reduces to the max-XORSAT recursion in [36 Appendix D.2]:
Here , the children are independent copies of , and are independent signs with . In particular, .
When the accepting set size is or , the threshold is in fact independent of . This is because on the tree, a change of variables exists, via , so that each constraint becomes either or , when or respectively. For other accepting-set sizes, however, may depend on the choice of .
If instead of , one is interested in the Erdős–Rényi ensemble of -uniform hypergraphs with average degree , the corresponding tree recursion replaces in (48) by an independently random offspring count . Then one needs to specify a family of exchangeable, degree-dependent coefficient law , and draw 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 and a coefficient law for both recursions. Let be the BPQM check-to-symbol message law in § 5, using the unshifted physical channel of (41), and let be its ensemble-average terminal error from (39). Define
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 , integers , and a nonempty proper subset . At each optimization variable, independently draw its incident nonzero coefficients from an exchangeable law on . Use this same law for reconstruction and BPQM recursions. For a probability vector over , define its random posterior lift vector by
Let , , and be as in (48). Then, for every finite and depth ,
where . Their thresholds satisfy
For the finite-graph ensemble of Definition 2, every fixed 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 , 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 for the BPQM message channel in (26). Its dual is equivalent, up to a fixed basis change and relabeling, to the classical additive channel
where is the input whose prior distribution we will take to be uniform on . Renes’ duality theorem exchanges equality and parity combinations for binary-alphabet channels [32 Theorem 1]. For our channel family over , the same exchange follows from the posterior representation that we verify below.
With the uniform prior , the posterior after observing has entries . Sampling observations conditional on the transmitted value , such that , gives precisely the random posterior lift 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 and on , and let be their parity output as in (32): draw with probability and set . Accordingly,
These are identities of joint vector distributions, with independent input lifts on each right-hand side. For the first, use independent noises and and add them. For the second, set . Its probability and the conditional distribution of are exactly the branch probability and outgoing vector in (32). Evaluating the outgoing vector at gives the normalized product in (58). For the coefficient relabeling in § 5, write ; then . 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 , for a fixed probability vector and uniform input, the quantum Holevo information of and the classical mutual information of satisfy
Indeed, the outputs of are pure and their average is , while adds to a uniform input independent noise of entropy . Here is the Holevo information of the BPQM message, which bounds how much information about the code symbol can be extracted from . It attains its maximum only at the uniform distribution, , where the states are orthogonal and . On the other side, is the information that the output of the dual classical channel carries about its input . The proof below identifies this classical dual with the Gibbs reconstruction posterior law in § 7. Since , 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 at depth . At both sides equal , since . Assume . 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 and a BPQM check is a max-LINSAT variable , 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 . By (35), , where the are independent copies of coming from disjoint subtrees. By (57), is the convolution of the independent lifts of and of the . By the inductive hypothesis, the convolution of the last lifts has the law of in (47), while with . Using the convolution convention of (29) and from (43),
where the last step uses . Up to the constant , this is the likelihood contributed by constraint in the reconstruction recursion.
Parity update at the parent check. The parent check is a variable with parent constraint and child constraints . Its parity condition reads with . Equations (36) and (37) relabel each input as and then apply the parity rule times. By the relabeling identity after (58), , and by (58) the parity updates lift to a normalized product:
Substituting (60) with , the constants cancel and each factor becomes . The and are independent across , and the are the coefficient ratios drawn from , exactly as in (48). Hence , which completes the induction.
To show the second identity in (54), we apply (49) and the first identity, averaging over given ,
and gives .
We now prove the threshold equality (55). Write and .
Parseval’s identity, the root convolution (39), and independence of its inputs give
For , each , , is nonzero: it is a positive multiple of , which cannot vanish for prime and a nonempty proper . Indeed, the minimal polynomial of is , whereas is not a multiple of it. The two nonnegative finite sums therefore vanish together as . The error function (33) is continuous and vanishes only at , so the compactness of the probability simplex gives
At , and both conditions hold directly. This proves the threshold equality (55). Finally, for any fixed , we have , which by the second identity in (54) is exactly the hypothesis of Corollary 3. That corollary yields the polynomial-time coherent Gibbs sampling statement.
Corollary 5 (Information monotonicity in inverse temperature). Fix as in Definition 2. For every depth , the reconstruction information in (45) is nondecreasing in . The same holds for its limit as .
Proof. Write for the uniform distribution on , and for the uniform distribution on . The physical channel vector in (43) satisfies
Since increases with , for we may set and . Convolution with gives , so
The equality rule (30) therefore gives
Thus, given the physical output at , we can append , apply , and discard the second system to obtain exactly the output at , without knowing the codeword symbol .
Consider the quantum combining tree dual to the depth- reconstruction observation, and let 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 into the observation at . 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 . By the finite-depth posterior correspondence proved above and (59), averaging over the herald labels and known tree data gives
Hence . Taking proves the limiting statement.
Example: Binary case. For with , the physical channel and its overlap are
In this case the posterior magnetization, meaning its probability of 0 minus its probability of 1, is
Averaging this magnetization is therefore equivalent to tracking the mean-square quantum overlap. The factor of two in (63) follows from our convention that multiplies the number of violated constraints; the spin-coupling convention uses .
By Eqs. (54) and (64), . With , (61) and the binary specialization of (33) yield
To obtain these bounds, use for 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 for average-case -regular max--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 . This conjecture suggests that widely-used optimization methods such as simulated annealing and Glauber dynamics should fail efficiently reach temperatures below . 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 was mathematically rigorous. Everything in this section, regarding the equivalence between the lowest energy efficiently reachable by simulated annealing and the expected energy at is purely empirical.
Note that should not be regarded as a computational hardness threshold in all parameter regimes. In [36] it was shown that for sufficiently large and , a variant of Prange’s algorithm can sample at temperatures below in polynomial time. Nevertheless, at small and , simulated annealing is difficult to beat in practice and we are not aware of any counterexample disproving the notion that does represent the classical computational hardness barrier at sufficiently small and .
In what follows, we report on computational experiments for -regular max--LINSAT over an alphabet of size with target sets of size . Thus, we explore instances across a four-dimensional parameter space. For a given choice of , we can compute the corresponding value of 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 , with independent uniform offsets and targets . Thus row is satisfied when
The Tanner graph is sampled uniformly from the simple -regular ensemble. For each variable, we choose its coefficients for the incident constraints according to the law . The parameter grid is
which contains 525 settings. All finite-graph calculations use optimization variables. For an assignment , write
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 -th constraint follows the distribution in (43). At , the expected fraction of violated constraints on the tree is thus
which is also the equilibrium energy of finite random instances at any temperature in the replica-symmetric phase.
Numerical method for determining . We use the operational definition in (50) in terms of the reconstruction distributional recursion. In practice, we determine via the following planted density evolution algorithm:
Initialize a pool of samples at the planted value, i.e., set . By default, take .
For each step of the recursion (48), replace the pool by fresh samples as follows: For each sample, draw one -tuple from and form all child-to-parent ratios ; then per constraint draw children uniformly from the current pool and a noise . Convolve the children by multiplying length- FFTs, and accumulate the logarithm of the bracket over the constraints before exponentiating and normalizing. One sweep costs .
Track the order parameter . Declare the trivial fixed point reached when it drops below , and a nontrivial one when the local slope , measured across geometric checkpoints , falls below twice in a row while . Locate the threshold by bisection in .
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, sweeps with a calibrated linear- 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 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 .
(a) (a) sweeps.
(b) (b) 144,000 sweeps.
Figure 4. Figure 4: Simulated-annealing violation fractions versus the tree-based reference 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 protocol | settings | median | mean | maximum |
| high-sweep-count SA | 252 | 0.273 | 0.582 | 2.815 |
| low-sweep-count SA | 252 | 0.873 | 0.920 | 2.158 |
Table 1. Absolute discrepancy between the reported simulated-annealing violation fraction and the tree-based reference , in percentage points of violated constraints. The two protocols use 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 . 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]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]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
- [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
- [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
- [6]Dorit Aharonov and Oded Regev. Lattice problems in NP ∩ coNP. Journal of the ACM (JACM), 52(5):749–765, 2005.
- [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
- [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
- [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
- [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
- [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
- [13]Svante Janson. The probability that a random multigraph is simple, II. arXiv:1307.6344, 2013.arxiv.org/abs/1307.6344
- [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
- [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
- [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
- [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
- [19]Marc Mézard and Andrea Montanari. Reconstruction on trees and spin glass transition. Journal of Statistical Physics, 124(6):1317–1350, 2006.
- [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
- [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
- [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
- [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
- [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
- [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.
- [27]Christophe Piveteau, Yihui Quek, and M. Franco Garrido. Gibbs state preparation through quantum decoding. arXiv:2610.03566, 2026.arxiv.org/abs/2610.03566
- [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
- [29]Oded Regev. Quantum computation and lattice problems. SIAM Journal on Computing, 33(3):738–760, 2004.
- [30]Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009.
- [31]Joseph M. Renes. Belief propagation decoding of quantum channels by passing quantum mes-sages. New Journal of Physics, 19(7):072001, 2017.
- [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
- [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
- [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
- [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

