Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40345

Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry

Leo Zhou, Noah Shutty, Mark Sellke, Stephen P. Jordan

quant-phcond-mat.dis-nncs.CCcs.DSmath.PRSubmitted Sep 30, 2026• Announced Oct 1, 2026• 3 citations
arXivHTMLPDF

Abstract

We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task of Gibbs sampling for classical Ising $k$-spin glasses (or Max-$k$-XORSAT) on random Erdős-Rényi hypergraphs with average degree $D\ge k$. In a temperature range beginning asymptotically at the predicted dynamical phase transition, $β_{\rm dyn}(k,D) = \sqrt{(2\ln k)/D}\times [1+o_{k\to\infty}(1)]$, we show that shattering and disorder chaos form a topological barrier that obstructs many algorithms, including Glauber dynamics and any algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical algorithm based on Prange's method, and by DQI equipped with a quantum decoder. For example, when $D=αk$ with fixed $α>1$, both Prange's algorithm and DQI can sample at any inverse temperature $β< \tanh^{-1}(1/α)$ for sufficiently large $k$, well beyond the dynamical threshold $β_{\rm dyn} \sim \sqrt{2\ln k / (αk)}$. Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.

AI Summary

Can decoded quantum interferometry (DQI) sample classical spin-glass Gibbs measures beyond barriers for stable algorithms? This paper reduces Gibbs sampling for Ising parity Hamiltonians with random signs to decoding a linear code under coherent bit-flip noise, with inverse temperature $\beta$ corresponding to error rate $\gamma=(1-\operatorname{sech}\beta)/2$. For random Erdős–Rényi Max-$k$-XORSAT with average degree $D\ge k$ and sufficiently large fixed $k$, it proves shattering, single-clause disorder chaos, failure of stable samplers in normalized Wasserstein distance, and exponential Glauber mixing time throughout $(1+\varepsilon)\sqrt{2\ln k/D}\le\beta\le\sqrt{k/(2D)}$. The proof establishes annealed free energy and a soft overlap gap in a planted model, transfers these properties to the original ensemble, and derives clustering and sensitivity to clause perturbations. DQI with an unambiguous-state-discrimination decoder achieves polynomial-time sampling with vanishing expected total-variation error whenever $D\tanh\beta<K_*(k)$, where $K_*(k)$ is a random-matrix full-row-rank threshold satisfying $K_*(k)/k\to1$. The decoder converts coherent noise into erasures recovered by Gaussian elimination. For $D=\alpha k$, $\alpha>1$, the achievable inverse-temperature threshold tends to $\operatorname{arctanh}(1/\alpha)$, while the dynamical threshold tends to zero. There is no demonstrated quantum advantage: a classical Prange-type sampler—independently retaining clauses with probability $\tanh\beta$ and sampling their linear-system solutions—achieves the identical bound. The separation concerns stable algorithms, not all algorithms. Guarantees are average-case; efficient sampling beyond replica symmetry breaking, improved decoders, and an ensemble exhibiting quantum advantage remain open.

No sign of AI-generated textAI use disclosed
Claude Fable 5.1 was used to implement Python code that generated the numerical data in Tables~\ref{tab:dense-betas}, \ref{tab:xorsat-grid}, and \ref{tab:xorsat-grid-reg}.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
44 pages, 1 figure, 3 tables

Related papers

Gibbs state preparation through quantum decoding

Christophe Piveteau, Yihui Quek, M. Isabel Franco Garrido

We propose a Gibbs state preparation algorithm that exploits algebraic structure in the Hamiltonian. Our starting point is Hamiltonian Decoded Quantum Interferometry (HDQI), a recent algorithm that reduces Gibbs state preparation for Pauli Hamiltonians to decoding error-correcting codes. We introduce quantum decoding HDQI (QD-HDQI), replacing HDQI's coherent classical decoder by a quantum decoder that can exploit interference between different errors. For commuting Pauli Hamiltonians, our reduction is efficient and the associated quantum decoding problem corresponds to transmitting the associated symplectic code over i.i.d. pure-state classical-quantum channels. For uniformly random Hamiltonian signs, the vanishing-error threshold of an efficient decoder directly determines the lowest temperature that our algorithm can reach. Even using only classical decoders, this improves upon HDQI's achievable inverse temperature from linear to square-root in the correctable error fraction; quantum decoders can improve further by tolerating still stronger noise. A similar picture extends to the noncommuting regime previously handled by HDQI, where now the noise is correlated within small, independent blocks. We study two such quantum decoders in our QD-HDQI Gibbs sampling framework. The first, based on unambiguous state discrimination, works efficiently for arbitrary binary linear codes. However, we "dequantize" this strategy for commuting Hamiltonians, contributing a classical rejection sampler that matches its temperature threshold. The second is belief propagation with quantum messages (BPQM), a quantum generalization of classical belief propagation. We show that for certain dilute spin glasses, BPQM's decoding threshold exceeds the Shannon limit for classical decoding, reaching temperatures inaccessible to any classical decoder within our framework.

quant-pharXiv:2610.03566•Oct 5, 2026•3 citations

Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods

Elies Gil-Fuster, Matan Ninio, Lennart Bittel +4 more

Optimization problems are among the leading candidates for industrially relevant quantum advantage. Decoded quantum interferometry (DQI) has been proposed to tackle approximate optimization, establishing a connection to classical decoding problems. While previous work has primarily focused on the theoretical complexity of DQI, comparatively little is known about its empirical performance relative to classical algorithms. In this work, we shed further light on the complexity of DQI and investigate numerically whether classical sampling methods can emulate the optimization capabilities of DQI. We first present a simplified analytical characterization of DQI that connects its expected performance to binomial statistics, and we identify concrete obstacles in further studying the complexity of DQI. Exploiting the fact that DQI output probabilities are efficiently computable, we apply Markov chain Monte Carlo (MCMC) techniques, particularly block-Gibbs sampling, to sample from the induced distribution. We study the runtime scaling of these methods for two optimization problems called max-XORSAT, where we reach beyond $1000$ effective qubits; and OPI, where we reach beyond $150$ effective qubits. Our results show that MCMC algorithms can reliably attain the approximation ratios expected from DQI across a broad range of problem sizes. In OPI, in the regime where a super-polynomial advantage is claimed for DQI, we observe an empirical runtime for MCMC that scales approximately as $1.1^{n}$, indicating exponential growth with a comparatively small base. Our findings do not refute existing quantum advantage claims but provide new empirical evidence that classical sampling algorithms can closely match DQI's optimization performance, offering a more nuanced perspective on the practical advantage of DQI.

quant-pharXiv:2607.28120•Jul 31, 2026•5 citations

Hamiltonian Decoded Quantum Interferometry

Alexander Schmidhuber, Jonathan Z. Lu, Noah Shutty +3 more

We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm that utilizes coherent Bell measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian optimization to classical decoding. For a signed Pauli Hamiltonian $H$ and any degree-$\ell$ polynomial ${P}$, HDQI prepares a purification of the density matrix $ρ_{P}(H) \propto {P}^2(H)$ by solving a combination of two tasks: decoding $\ell$ errors on a classical code defined by $H$, and preparing a pilot state that encodes the anti-commutation structure of $H$. Choosing $P(x)$ to approximate $\exp(-βx/2)$ yields Gibbs states at inverse temperature $β$; other choices prepare approximate ground states, microcanonical ensembles, and other spectral filters. For local Hamiltonians, the corresponding decoding problem is that of LDPC codes. Preparing the pilot state is always efficient for commuting Hamiltonians, but highly non-trivial for non-commuting Hamiltonians. Nevertheless, we prove that this state admits an efficient matrix product state representation for Hamiltonians whose anti-commutation graph decomposes into connected components of logarithmic size. We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians -- including the toric code and Haah's cubic code -- but we also develop a matching efficient classical algorithm for this task. For a non-commuting semiclassical spin glass and commuting stabilizer Hamiltonians with quantum defects, HDQI prepares Gibbs states up to a constant inverse-temperature threshold using polynomial quantum resources and quasi-polynomial classical pre-processing. These results position HDQI as a versatile algorithmic primitive and the first extension of Regev's reduction to non-abelian groups.

arXiv:2510.07913•Oct 9, 2025•22 citations

No Exponential Quantum Advantage for Decoded Quantum Interferometry with Local Quantum Decoders

Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana +5 more

Decoded quantum interferometry (DQI) reduces optimization of sparse linear constraint problems, and sampling from their Gibbs measures, to decoding a linear code from a quantum state. We study DQI on random $D$-regular $k$-sparse instances with $k\ge3$, for which local decoders such as belief propagation with quantum messages (BPQM) are commonly used. Such decoders estimate a typical codeword symbol using only the qudits within logarithmic distance of it. Our main insight is that the thresholds of the decoding problem induced by DQI correspond to phase transitions of the Gibbs measure that are well studied in statistical physics: tree reconstruction for local decoders and, for Max-$k$-XORSAT, condensation for the optimal decoder. This insight allows us to prove two main results. First, we prove an information-theoretic obstruction: no local decoder can recover the codeword with high probability above the tree reconstruction threshold. Conversely, we show that a decoder based on BPQM reaches this threshold. Since the cavity method predicts that local Markov chains equilibrate rapidly up to the same threshold, we expect DQI with local decoders to give no exponential speedup for sampling and no advantage in approximate optimization with amplitude functions that depend only on the number of violated constraints. Second, we consider the optimal decoder (the pretty-good measurement, for which no efficient implementation is known) and show that it succeeds exactly below the condensation threshold. The condensation threshold thus provides a tight upper bound on the performance of DQI with these amplitude functions, providing a strict refinement of the limit that Jordan et al.\ derived from the Holevo bound. Our results point to efficient nonlocal decoders that succeed between the two thresholds as the only viable path to a quantum advantage with DQI on these instances.

arXiv:2611.12718•Nov 9, 2026•1 citation

Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry

Maximilian J. Kramer, Carsten Schubert, Jens Eisert

For general max-k-XORSAT with $k \geq 3$, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless $\mathsf{P} = \mathsf{NP}$: approximating beyond the random-assignment value of $1/2$ is $\mathsf{NP}$-hard. The picture changes when each variable appears in at most $D$ constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order $1/\sqrt{D}$. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-E$k$-LINSAT$(q,r)$ with bounded degree $D$ and over arbitrary finite fields $\mathbb{F}_q$, proving that it is $\mathsf{NP}$-hard to exceed $r/q + \mathcal{O}_{q,r}(1/\sqrt{D})$. These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on $(k,D)$-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic $1/\sqrt{D \log D}$ barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the $1/\sqrt{D}$ scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.

quant-pharXiv:2606.13570•Jun 12, 2026•3 citations

An (almost) efficient classical algorithm for sampling from typical Gibbs states

Saleh Naghdi, Eric R. Anschuetz

Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum $p$-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum $p$-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum $p$-spin model at temperatures below that for which classical algorithms are also (almost) efficient.

quant-pharXiv:2609.40250•Oct 1, 2026•0 citations
We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task of Gibbs sampling for classical Ising kkk-spin glasses (or Max-kkk-XORSAT) on random Erdős-Rényi hypergraphs with average degree D≥kD\ge kD≥k. In a temperature range beginning asymptotically at the predicted dynamical phase transition, βdyn(k,D)=(2ln⁡k)/D×[1+ok→∞(1)]β_{\rm dyn}(k,D) = \sqrt{(2\ln k)/D}\times [1+o_{k\to\infty}(1)]βdyn​(k,D)=(2lnk)/D​×[1+ok→∞​(1)], we show that shattering and disorder chaos form a topological barrier that obstructs many algorithms, including Glauber dynamics and any algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical algorithm based on Prange's method, and by DQI equipped with a quantum decoder. For example, when D=αkD=αkD=αk with fixed α>1α>1α>1, both Prange's algorithm and DQI can sample at any inverse temperature β<tanh⁡−1(1/α)β< \tanh^{-1}(1/α)β<tanh−1(1/α) for sufficiently large kkk, well beyond the dynamical threshold βdyn∼2ln⁡k/(αk)β_{\rm dyn} \sim \sqrt{2\ln k / (αk)}βdyn​∼2lnk/(αk)​. Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.
Can decoded quantum interferometry (DQI) sample classical spin-glass Gibbs measures beyond barriers for stable algorithms? This paper reduces Gibbs sampling for Ising parity Hamiltonians with random signs to decoding a linear code under coherent bit-flip noise, with inverse temperature β\betaβ corresponding to error rate γ=(1−sech⁡β)/2\gamma=(1-\operatorname{sech}\beta)/2γ=(1−sechβ)/2.
For random Erdős–Rényi Max-kkk-XORSAT with average degree D≥kD\ge kD≥k and sufficiently large fixed kkk, it proves shattering, single-clause disorder chaos, failure of stable samplers in normalized Wasserstein distance, and exponential Glauber mixing time throughout (1+ε)2ln⁡k/D≤β≤k/(2D)(1+\varepsilon)\sqrt{2\ln k/D}\le\beta\le\sqrt{k/(2D)}(1+ε)2lnk/D​≤β≤k/(2D)​. The proof establishes annealed free energy and a soft overlap gap in a planted model, transfers these properties to the original ensemble, and derives clustering and sensitivity to clause perturbations.
DQI with an unambiguous-state-discrimination decoder achieves polynomial-time sampling with vanishing expected total-variation error whenever Dtanh⁡β<K∗(k)D\tanh\beta<K_*(k)Dtanhβ<K∗​(k), where K∗(k)K_*(k)K∗​(k) is a random-matrix full-row-rank threshold satisfying K∗(k)/k→1K_*(k)/k\to1K∗​(k)/k→1. The decoder converts coherent noise into erasures recovered by Gaussian elimination. For D=αkD=\alpha kD=αk, α>1\alpha>1α>1, the achievable inverse-temperature threshold tends to arctanh⁡(1/α)\operatorname{arctanh}(1/\alpha)arctanh(1/α), while the dynamical threshold tends to zero.
There is no demonstrated quantum advantage: a classical Prange-type sampler—independently retaining clauses with probability tanh⁡β\tanh\betatanhβ and sampling their linear-system solutions—achieves the identical bound. The separation concerns stable algorithms, not all algorithms. Guarantees are average-case; efficient sampling beyond replica symmetry breaking, improved decoders, and an ensemble exhibiting quantum advantage remain open.
We propose a Gibbs state preparation algorithm that exploits algebraic structure in the Hamiltonian. Our starting point is Hamiltonian Decoded Quantum Interferometry (HDQI), a recent algorithm that reduces Gibbs state preparation for Pauli Hamiltonians to decoding error-correcting codes. We introduce quantum decoding HDQI (QD-HDQI), replacing HDQI's coherent classical decoder by a quantum decoder that can exploit interference between different errors. For commuting Pauli Hamiltonians, our reduction is efficient and the associated quantum decoding problem corresponds to transmitting the associated symplectic code over i.i.d. pure-state classical-quantum channels. For uniformly random Hamiltonian signs, the vanishing-error threshold of an efficient decoder directly determines the lowest temperature that our algorithm can reach. Even using only classical decoders, this improves upon HDQI's achievable inverse temperature from linear to square-root in the correctable error fraction; quantum decoders can improve further by tolerating still stronger noise. A similar picture extends to the noncommuting regime previously handled by HDQI, where now the noise is correlated within small, independent blocks. We study two such quantum decoders in our QD-HDQI Gibbs sampling framework. The first, based on unambiguous state discrimination, works efficiently for arbitrary binary linear codes. However, we "dequantize" this strategy for commuting Hamiltonians, contributing a classical rejection sampler that matches its temperature threshold. The second is belief propagation with quantum messages (BPQM), a quantum generalization of classical belief propagation. We show that for certain dilute spin glasses, BPQM's decoding threshold exceeds the Shannon limit for classical decoding, reaching temperatures inaccessible to any classical decoder within our framework.
Optimization problems are among the leading candidates for industrially relevant quantum advantage. Decoded quantum interferometry (DQI) has been proposed to tackle approximate optimization, establishing a connection to classical decoding problems. While previous work has primarily focused on the theoretical complexity of DQI, comparatively little is known about its empirical performance relative to classical algorithms. In this work, we shed further light on the complexity of DQI and investigate numerically whether classical sampling methods can emulate the optimization capabilities of DQI. We first present a simplified analytical characterization of DQI that connects its expected performance to binomial statistics, and we identify concrete obstacles in further studying the complexity of DQI. Exploiting the fact that DQI output probabilities are efficiently computable, we apply Markov chain Monte Carlo (MCMC) techniques, particularly block-Gibbs sampling, to sample from the induced distribution. We study the runtime scaling of these methods for two optimization problems called max-XORSAT, where we reach beyond 100010001000 effective qubits; and OPI, where we reach beyond 150150150 effective qubits. Our results show that MCMC algorithms can reliably attain the approximation ratios expected from DQI across a broad range of problem sizes. In OPI, in the regime where a super-polynomial advantage is claimed for DQI, we observe an empirical runtime for MCMC that scales approximately as 1.1n1.1^{n}1.1n, indicating exponential growth with a comparatively small base. Our findings do not refute existing quantum advantage claims but provide new empirical evidence that classical sampling algorithms can closely match DQI's optimization performance, offering a more nuanced perspective on the practical advantage of DQI.
We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm that utilizes coherent Bell measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian optimization to classical decoding. For a signed Pauli Hamiltonian HHH and any degree-ℓ\ellℓ polynomial P{P}P, HDQI prepares a purification of the density matrix ρP(H)∝P2(H)ρ_{P}(H) \propto {P}^2(H)ρP​(H)∝P2(H) by solving a combination of two tasks: decoding ℓ\ellℓ errors on a classical code defined by HHH, and preparing a pilot state that encodes the anti-commutation structure of HHH. Choosing P(x)P(x)P(x) to approximate exp⁡(−βx/2)\exp(-βx/2)exp(−βx/2) yields Gibbs states at inverse temperature βββ; other choices prepare approximate ground states, microcanonical ensembles, and other spectral filters. For local Hamiltonians, the corresponding decoding problem is that of LDPC codes. Preparing the pilot state is always efficient for commuting Hamiltonians, but highly non-trivial for non-commuting Hamiltonians. Nevertheless, we prove that this state admits an efficient matrix product state representation for Hamiltonians whose anti-commutation graph decomposes into connected components of logarithmic size. We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians -- including the toric code and Haah's cubic code -- but we also develop a matching efficient classical algorithm for this task. For a non-commuting semiclassical spin glass and commuting stabilizer Hamiltonians with quantum defects, HDQI prepares Gibbs states up to a constant inverse-temperature threshold using polynomial quantum resources and quasi-polynomial classical pre-processing. These results position HDQI as a versatile algorithmic primitive and the first extension of Regev's reduction to non-abelian groups.
Decoded quantum interferometry (DQI) reduces optimization of sparse linear constraint problems, and sampling from their Gibbs measures, to decoding a linear code from a quantum state. We study DQI on random DDD-regular kkk-sparse instances with k≥3k\ge3k≥3, for which local decoders such as belief propagation with quantum messages (BPQM) are commonly used. Such decoders estimate a typical codeword symbol using only the qudits within logarithmic distance of it. Our main insight is that the thresholds of the decoding problem induced by DQI correspond to phase transitions of the Gibbs measure that are well studied in statistical physics: tree reconstruction for local decoders and, for Max-kkk-XORSAT, condensation for the optimal decoder. This insight allows us to prove two main results. First, we prove an information-theoretic obstruction: no local decoder can recover the codeword with high probability above the tree reconstruction threshold. Conversely, we show that a decoder based on BPQM reaches this threshold. Since the cavity method predicts that local Markov chains equilibrate rapidly up to the same threshold, we expect DQI with local decoders to give no exponential speedup for sampling and no advantage in approximate optimization with amplitude functions that depend only on the number of violated constraints. Second, we consider the optimal decoder (the pretty-good measurement, for which no efficient implementation is known) and show that it succeeds exactly below the condensation threshold. The condensation threshold thus provides a tight upper bound on the performance of DQI with these amplitude functions, providing a strict refinement of the limit that Jordan et al.\ derived from the Holevo bound. Our results point to efficient nonlocal decoders that succeed between the two thresholds as the only viable path to a quantum advantage with DQI on these instances.
For general max-k-XORSAT with k≥3k \geq 3k≥3, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless P=NP\mathsf{P} = \mathsf{NP}P=NP: approximating beyond the random-assignment value of 1/21/21/2 is NP\mathsf{NP}NP-hard. The picture changes when each variable appears in at most DDD constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order 1/D1/\sqrt{D}1/D​. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-Ekkk-LINSAT(q,r)(q,r)(q,r) with bounded degree DDD and over arbitrary finite fields Fq\mathbb{F}_qFq​, proving that it is NP\mathsf{NP}NP-hard to exceed r/q+Oq,r(1/D)r/q + \mathcal{O}_{q,r}(1/\sqrt{D})r/q+Oq,r​(1/D​). These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on (k,D)(k,D)(k,D)-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic 1/Dlog⁡D1/\sqrt{D \log D}1/DlogD​ barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the 1/D1/\sqrt{D}1/D​ scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.
Gibbs state preparation has emerged as a potential avenue for quantum advantage in the study of physical systems. Although there is known advantage for computing local properties of worst-case Gibbs states, recent results suggest a different picture for average-case local systems: at temperatures where their Gibbs states can be efficiently prepared quantumly, quasi-polynomial time classical algorithms can also compute local expectation values. Yet this leaves open the possibility of an advantage under a stronger notion of simulation: sampling. Gibbs sampling underlies Boltzmann machine-based quantum learning algorithms and quantum supremacy proposals, but its classical average-case complexity for physically relevant models remains unresolved. Here, we give strong evidence against an exponential quantum advantage in Gibbs sampling for an ensemble of local systems known as the quantum ppp-spin model. We describe a classical algorithm for sampling from the Gibbs state to any polynomially small error in total variation distance. Our algorithm is based on a meta-algorithm known as algorithmic stochastic localization (ASL). Our main technical result is a generalized convergence theorem for ASL which reduces approximate sampling from any distribution on the hypercube to estimating the mean of a related "tilted distribution" to sufficiently low additive error. We then extend known quasi-polynomial time algorithms for computing local expectation values of a related disordered model to compute these "tilted means" for the quantum ppp-spin model. Finally, we give a non-rigorous physics argument that this mean-estimation algorithm works down to the spin glass transition temperature. As efficient quantum algorithms also fail at this transition, this suggests they cannot Gibbs sample the quantum ppp-spin model at temperatures below that for which classical algorithms are also (almost) efficient.