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:1906.10705 · Journal of Physics Complexity

Computational phase transition signature in Gibbs sampling

Hariphan Philathong, V. Akshay, Igor Zacharov, Jacob Biamonte

Published Dec 1, 2023• 4 citations
arXivHTMLPDF

Abstract

Abstract Gibbs sampling is fundamental to a wide range of computer algorithms. Such algorithms are set to be replaced by physics based processors—be it quantum or stochastic annealing devices—which embed problem instances and evolve a physical system into a low-energy ensemble to recover a probability distribution. At a critical constraint to variable ratio, satisfiability (SAT) problem instances exhibit a SAT-UNSAT transition (frustrated to frustration free). Algorithms require increasing computational resources from this critical point. This is a so called, algorithmic or computational phase transition and has extensively been studied. In this paper we consider the complexity in sampling and recovering ground states from resultant distributions of a physics based processor. In particular, we first consider the ideal Gibbs distributions at some fixed inverse temperature and observe that the success probability in sampling and recovering ground states decrease for instances starting at the critical density. Furthermore, simulating the Gibbs distribution, we employ Ising spin dynamics, which play a crucial role in understanding of non-equilibrium statistical physics, to find their steady states of 2-SAT Hamiltonians. We observe that beyond the critical density, the probability of sampling ground states decreases. Our results apply to several contemporary devices and provide a means to experimentally probe a signature of the computational phase transition.

DOI
10.1088/2632-072x/ad1410

Related papers

Computational phase transitions: benchmarking Ising machines and quantum optimisers

Hariphan Philathong, Vishwa Akshay, Ksenia Samburskaya +1 more

Abstract While there are various approaches to benchmark physical processors, recent findings have focused on computational phase transitions. This is due to several factors. Importantly, the hardest instances appear to be well-concentrated in a narrow region, with a control parameter allowing uniform random distributions of problem instances with similar computational challenge. It has been established that one could observe a computational phase transition in a distribution produced from coherent Ising machine(s). In terms of quantum approximate optimisation, the ability for the quantum algorithm to function depends critically on the ratio of a problems constraint to variable ratio (called density). The critical density dependence on performance resulted in what was called, reachability deficits. In this perspective we recall the background needed to understand how to apply computational phase transitions in various bench-marking tasks and we survey several such contemporary findings.

arXiv:2009.05579•Journal of Physics Complexity•Jan 14, 2021•4 citations

Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry

Leo Zhou, Noah Shutty, Mark Sellke +1 more

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.

quant-pharXiv:2609.40345•Oct 1, 2026•3 citations

Quantum sampling algorithms, phase transitions, and computational complexity

Dominik S. Wild, Dries Sels, Hannes Pichler +2 more

Drawing independent samples from a probability distribution is an important computational problem with applications in Monte Carlo algorithms, machine learning, and statistical physics. The problem can be solved in principle on a quantum computer by preparing a quantum state that encodes the entire probability distribution followed by a projective measurement. We investigate the complexity of adiabatically preparing such quantum states for the Gibbs distributions of various classical models including the Ising chain, hard-sphere models on different graphs, and a model encoding the unstructured search problem. By constructing a parent Hamiltonian, whose ground state is the desired quantum state, we relate the asymptotic scaling of the state preparation time to the nature of transitions between distinct quantum phases. These insights enable us to identify adiabatic paths that achieve a quantum speedup over classical Markov chain algorithms. In addition, we show that parent Hamiltonians for the problem of sampling from independent sets on certain graphs can be naturally realized with neutral atoms interacting via highly excited Rydberg states.

arXiv:2109.03007•Physical Review A•Sep 2, 2021•19 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

Quantum Sampling Algorithms for Near-Term Devices

Dominik S. Wild, Dries Sels, Hannes Pichler +2 more

Efficient sampling from a classical Gibbs distribution is an important computational problem with applications ranging from statistical physics over Monte Carlo and optimization algorithms to machine learning. We introduce a family of quantum algorithms that provide unbiased samples by preparing a state encoding the entire Gibbs distribution. We show that this approach leads to a speedup over a classical Markov chain algorithm for several examples, including the Ising model and sampling from weighted independent sets of two different graphs. Our approach connects computational complexity with phase transitions, providing a physical interpretation of quantum speedup. Moreover, it opens the door to exploring potentially useful sampling algorithms on near-term quantum devices, as the algorithm for sampling from independent sets on certain graphs can be naturally implemented using Rydberg atom arrays.

arXiv:2005.14059•Physical Review Letters•Sep 2, 2021•33 citations

Boltzmann Sampling of Frustrated J1 - J2 Ising Models with Programmable Quantum Annealers

Elijah Pelofske

One of the surprising, and potentially very useful, capabilities of analog quantum computers, such as D-Wave quantum annealers, is sampling from the Boltzmann, or Gibbs, distribution defined by a classical Hamiltonian. In this study, we thoroughly examine the ability of D-Wave quantum annealers to sample from the Boltzmann distribution defined by a canonical type of competing magnetic frustration $J_1$-$J_2$ model; the 1-dimensional ANNNI (axial next-nearest-neighbor Ising) model. Boltzmann sampling error rate is quantified for standard linear-ramp anneals ranging from $5$ nanosecond annealing times up to $2000$ microseconds on two different D-Wave quantum annealing processors. Interestingly, we find some analog hardware parameters which result in a very high accuracy (down to a TVD of $0.0003$) and low temperature sampling (down to $β=32.2$) in a frustrated region of the ANNNI model magnetic phase diagram. This bolsters the viability of current analog quantum computers for thermodynamic sampling applications of highly frustrated magnetic spin systems.

quant-pharXiv:2511.03796•Physical Review Research•Nov 7, 2025•1 citation
Abstract Gibbs sampling is fundamental to a wide range of computer algorithms. Such algorithms are set to be replaced by physics based processors—be it quantum or stochastic annealing devices—which embed problem instances and evolve a physical system into a low-energy ensemble to recover a probability distribution. At a critical constraint to variable ratio, satisfiability (SAT) problem instances exhibit a SAT-UNSAT transition (frustrated to frustration free). Algorithms require increasing computational resources from this critical point. This is a so called, algorithmic or computational phase transition and has extensively been studied. In this paper we consider the complexity in sampling and recovering ground states from resultant distributions of a physics based processor. In particular, we first consider the ideal Gibbs distributions at some fixed inverse temperature and observe that the success probability in sampling and recovering ground states decrease for instances starting at the critical density. Furthermore, simulating the Gibbs distribution, we employ Ising spin dynamics, which play a crucial role in understanding of non-equilibrium statistical physics, to find their steady states of 2-SAT Hamiltonians. We observe that beyond the critical density, the probability of sampling ground states decreases. Our results apply to several contemporary devices and provide a means to experimentally probe a signature of the computational phase transition.
Abstract While there are various approaches to benchmark physical processors, recent findings have focused on computational phase transitions. This is due to several factors. Importantly, the hardest instances appear to be well-concentrated in a narrow region, with a control parameter allowing uniform random distributions of problem instances with similar computational challenge. It has been established that one could observe a computational phase transition in a distribution produced from coherent Ising machine(s). In terms of quantum approximate optimisation, the ability for the quantum algorithm to function depends critically on the ratio of a problems constraint to variable ratio (called density). The critical density dependence on performance resulted in what was called, reachability deficits. In this perspective we recall the background needed to understand how to apply computational phase transitions in various bench-marking tasks and we survey several such contemporary findings.
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.
Drawing independent samples from a probability distribution is an important computational problem with applications in Monte Carlo algorithms, machine learning, and statistical physics. The problem can be solved in principle on a quantum computer by preparing a quantum state that encodes the entire probability distribution followed by a projective measurement. We investigate the complexity of adiabatically preparing such quantum states for the Gibbs distributions of various classical models including the Ising chain, hard-sphere models on different graphs, and a model encoding the unstructured search problem. By constructing a parent Hamiltonian, whose ground state is the desired quantum state, we relate the asymptotic scaling of the state preparation time to the nature of transitions between distinct quantum phases. These insights enable us to identify adiabatic paths that achieve a quantum speedup over classical Markov chain algorithms. In addition, we show that parent Hamiltonians for the problem of sampling from independent sets on certain graphs can be naturally realized with neutral atoms interacting via highly excited Rydberg states.
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.
Efficient sampling from a classical Gibbs distribution is an important computational problem with applications ranging from statistical physics over Monte Carlo and optimization algorithms to machine learning. We introduce a family of quantum algorithms that provide unbiased samples by preparing a state encoding the entire Gibbs distribution. We show that this approach leads to a speedup over a classical Markov chain algorithm for several examples, including the Ising model and sampling from weighted independent sets of two different graphs. Our approach connects computational complexity with phase transitions, providing a physical interpretation of quantum speedup. Moreover, it opens the door to exploring potentially useful sampling algorithms on near-term quantum devices, as the algorithm for sampling from independent sets on certain graphs can be naturally implemented using Rydberg atom arrays.
One of the surprising, and potentially very useful, capabilities of analog quantum computers, such as D-Wave quantum annealers, is sampling from the Boltzmann, or Gibbs, distribution defined by a classical Hamiltonian. In this study, we thoroughly examine the ability of D-Wave quantum annealers to sample from the Boltzmann distribution defined by a canonical type of competing magnetic frustration J1J_1J1​-J2J_2J2​ model; the 1-dimensional ANNNI (axial next-nearest-neighbor Ising) model. Boltzmann sampling error rate is quantified for standard linear-ramp anneals ranging from 555 nanosecond annealing times up to 200020002000 microseconds on two different D-Wave quantum annealing processors. Interestingly, we find some analog hardware parameters which result in a very high accuracy (down to a TVD of 0.00030.00030.0003) and low temperature sampling (down to β=32.2β=32.2β=32.2) in a frustrated region of the ANNNI model magnetic phase diagram. This bolsters the viability of current analog quantum computers for thermodynamic sampling applications of highly frustrated magnetic spin systems.