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:2602.23183

Dequantization Barriers for Guided Stoquastic Hamiltonians

Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara

quant-phcs.CCcs.DSSubmitted Feb 26, 2026• Announced Feb 27, 2026• 3 citations
arXivHTMLPDF

Abstract

We construct a probability distribution, induced by the Perron--Frobenius eigenvector of an exponentially large graph, which cannot be efficiently sampled by any classical algorithm, even when provided with the best-possible warm-start distribution. In the quantum setting, this problem can be viewed as preparing the ground state of a stoquastic Hamiltonian given a guiding state as input, and is known to be efficiently solvable on a quantum computer. Our result suggests that no efficient classical algorithm can solve a broad class of stoquastic ground-state problems. Our graph is constructed from a class of high-degree, high-girth spectral expanders to which self-similar trees are attached. This builds on and extends prior work of Gilyén, Hastings, and Vazirani [Quantum 2021, STOC 2021], which ruled out dequantization for a specific stoquastic adiabatic path algorithm. We strengthen their result by ruling out any classical algorithm for guided ground-state preparation.

Related papers

Monte Carlo simulation of stoquastic Hamiltonians

Sergey B. Bravyi

Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian $H$ with a promise that the ground state of $H$ has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).

arXiv:1402.2295•Quantum Information and Computation•Oct 1, 2015•86 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

Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians

Jacob Bringewatt, W. Dorland, Stephen P. Jordan +1 more

Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real non-negative amplitudes and thus for whom destructive interference is not manifest. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path-integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-$k$-SAT problems, use $k$-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved $n$-body interactions. Here we present a 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.

arXiv:1709.03971•Physical Review A•Feb 15, 2018•12 citations

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians

François Le Gall

We construct classical algorithms computing an approximation of the ground state energy of an arbitrary $k$-local Hamiltonian acting on $n$ qubits. We first consider the setting where a good ``guiding state'' is available, which is the main setting where quantum algorithms are expected to achieve an exponential speedup over classical methods. We show that a constant approximation (i.e., an approximation with constant relative accuracy) of the ground state energy can be computed classically in $\mathrm{poly}\left(1/χ,n\right)$ time and $\mathrm{poly}(n)$ space, where $χ$ denotes the overlap between the guiding state and the ground state (as in prior works in dequantization, we assume sample-and-query access to the guiding state). This gives a significant improvement over the recent classical algorithm by Gharibian and Le Gall (SICOMP 2023), and matches (up a to polynomial overhead) both the time and space complexities of quantum algorithms for constant approximation of the ground state energy. We also obtain classical algorithms for higher-precision approximation. For the setting where no guided state is given (i.e., the standard version of the local Hamiltonian problem), we obtain a classical algorithm computing a constant approximation of the ground state energy in $2^{O(n)}$ time and $\mathrm{poly}(n)$ space. To our knowledge, before this work it was unknown how to classically achieve these bounds simultaneously, even for constant approximation. We also discuss complexity-theoretic aspects of our results.

arXiv:2410.21833•Leibniz international proceedings in informatics•Oct 29, 2024•7 citations

Classical Algorithms for Hamiltonian Dynamics Mean Value and Guided Local Hamiltonian Problem

Yusen Wu, Yukun Zhang, Wang, Chuan +1 more

The efficient simulation of quantum dynamics and ground states is a central challenge in physics and a key frontier for quantum advantage. While short-time evolution in one-dimensional systems can often be simulated classically, extending this to higher dimensions remains difficult. Here, we introduce an efficient classical algorithm for simulating the short-time dynamics of arbitrary local quantum systems. For any local Hamiltonian $H$ and constant evolution time $t$, our method estimates expectation values of the form $\langleψ|e^{iHt}Oe^{-iHt}|ψ\rangle$ for global Pauli observables $O$ and stabilizer states $|ψ\rangle$, with high precision and exponentially small failure probability. Furthermore, we present a classical dequantization of a tailored quantum algorithm that efficiently solves the guided local Hamiltonian (GLH) problem to constant additive error - previously considered classically hard and hence a promising candidate for quantum computational advantage. These results reveal unexpected classical tractability in constant-time quantum dynamics and fundamental connections between Hamiltonian dynamics mean value and the GLH problem. Our work refines the boundary between classical and quantum computational power, identifying sharper criteria for regimes where quantum advantage may genuinely emerge.

arXiv:2409.04161•Sep 6, 2024•8 citations

Polynomial-time exact diagonalization via sparse guided eigenwalks

Zachary E. Chin, Mario Motta, Javier Robledo Moreno +3 more

Computing quantum ground states is generically difficult, but additional structure can sometimes allow diagonalization to be recast as a more feasible problem. For example, when the desired ground state is sparse in a given basis, diagonalization can be facilitated via graph search. We make this reformulation precise by introducing the eigenwalk problem, which seeks the support of a sparse eigenvector of a Hermitian matrix by exploring the graph induced by its nonzero entries. However, it is not obvious whether the relevant support vertices must always be efficiently reachable by a search on the graph. To resolve this question, we prove that for every sparse eigenvector, there exists a (possibly different) sparse eigenvector with the same eigenvalue whose support is tightly localized in the graph, with diameter scaling only linearly in the sparsity and independently of the total number of vertices. As a consequence, if a $2^n$-dimensional, ${\rm poly}(n)$-sparse Hamiltonian has an $\mathcal{O}(1)$-sparse extremal eigenvector and one support element is known, then an exact eigenvector with the same eigenvalue can be computed classically in ${\rm poly}(n)$ time. The same conclusion follows when the $\mathcal{O}(1)$-sparse eigenvector is non-extremal, provided that it is sparser than every eigenvector with a different eigenvalue. These results hold with no assumptions on the degeneracy, locality, spectral width, or spectral gap of the Hamiltonian, and the underlying support-localization principle also extends to problems beyond exact diagonalization, such as sparse principal component analysis.

quant-pharXiv:2606.23967•Jun 24, 2026•1 citation
We construct a probability distribution, induced by the Perron--Frobenius eigenvector of an exponentially large graph, which cannot be efficiently sampled by any classical algorithm, even when provided with the best-possible warm-start distribution. In the quantum setting, this problem can be viewed as preparing the ground state of a stoquastic Hamiltonian given a guiding state as input, and is known to be efficiently solvable on a quantum computer. Our result suggests that no efficient classical algorithm can solve a broad class of stoquastic ground-state problems.
Our graph is constructed from a class of high-degree, high-girth spectral expanders to which self-similar trees are attached. This builds on and extends prior work of Gilyén, Hastings, and Vazirani [Quantum 2021, STOC 2021], which ruled out dequantization for a specific stoquastic adiabatic path algorithm. We strengthen their result by ruling out any classical algorithm for guided ground-state preparation.
Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian HHH with a promise that the ground state of HHH has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).
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.
Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real non-negative amplitudes and thus for whom destructive interference is not manifest. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path-integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-kkk-SAT problems, use kkk-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved nnn-body interactions. Here we present a 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.
We construct classical algorithms computing an approximation of the ground state energy of an arbitrary kkk-local Hamiltonian acting on nnn qubits. We first consider the setting where a good ``guiding state'' is available, which is the main setting where quantum algorithms are expected to achieve an exponential speedup over classical methods. We show that a constant approximation (i.e., an approximation with constant relative accuracy) of the ground state energy can be computed classically in poly(1/χ,n)\mathrm{poly}\left(1/χ,n\right)poly(1/χ,n) time and poly(n)\mathrm{poly}(n)poly(n) space, where χχχ denotes the overlap between the guiding state and the ground state (as in prior works in dequantization, we assume sample-and-query access to the guiding state). This gives a significant improvement over the recent classical algorithm by Gharibian and Le Gall (SICOMP 2023), and matches (up a to polynomial overhead) both the time and space complexities of quantum algorithms for constant approximation of the ground state energy. We also obtain classical algorithms for higher-precision approximation. For the setting where no guided state is given (i.e., the standard version of the local Hamiltonian problem), we obtain a classical algorithm computing a constant approximation of the ground state energy in 2O(n)2^{O(n)}2O(n) time and poly(n)\mathrm{poly}(n)poly(n) space. To our knowledge, before this work it was unknown how to classically achieve these bounds simultaneously, even for constant approximation. We also discuss complexity-theoretic aspects of our results.
The efficient simulation of quantum dynamics and ground states is a central challenge in physics and a key frontier for quantum advantage. While short-time evolution in one-dimensional systems can often be simulated classically, extending this to higher dimensions remains difficult. Here, we introduce an efficient classical algorithm for simulating the short-time dynamics of arbitrary local quantum systems. For any local Hamiltonian HHH and constant evolution time ttt, our method estimates expectation values of the form ⟨ψ∣eiHtOe−iHt∣ψ⟩\langleψ|e^{iHt}Oe^{-iHt}|ψ\rangle⟨ψ∣eiHtOe−iHt∣ψ⟩ for global Pauli observables OOO and stabilizer states ∣ψ⟩|ψ\rangle∣ψ⟩, with high precision and exponentially small failure probability. Furthermore, we present a classical dequantization of a tailored quantum algorithm that efficiently solves the guided local Hamiltonian (GLH) problem to constant additive error - previously considered classically hard and hence a promising candidate for quantum computational advantage. These results reveal unexpected classical tractability in constant-time quantum dynamics and fundamental connections between Hamiltonian dynamics mean value and the GLH problem. Our work refines the boundary between classical and quantum computational power, identifying sharper criteria for regimes where quantum advantage may genuinely emerge.
Computing quantum ground states is generically difficult, but additional structure can sometimes allow diagonalization to be recast as a more feasible problem. For example, when the desired ground state is sparse in a given basis, diagonalization can be facilitated via graph search. We make this reformulation precise by introducing the eigenwalk problem, which seeks the support of a sparse eigenvector of a Hermitian matrix by exploring the graph induced by its nonzero entries. However, it is not obvious whether the relevant support vertices must always be efficiently reachable by a search on the graph. To resolve this question, we prove that for every sparse eigenvector, there exists a (possibly different) sparse eigenvector with the same eigenvalue whose support is tightly localized in the graph, with diameter scaling only linearly in the sparsity and independently of the total number of vertices. As a consequence, if a 2n2^n2n-dimensional, poly(n){\rm poly}(n)poly(n)-sparse Hamiltonian has an O(1)\mathcal{O}(1)O(1)-sparse extremal eigenvector and one support element is known, then an exact eigenvector with the same eigenvalue can be computed classically in poly(n){\rm poly}(n)poly(n) time. The same conclusion follows when the O(1)\mathcal{O}(1)O(1)-sparse eigenvector is non-extremal, provided that it is sparser than every eigenvector with a different eigenvalue. These results hold with no assumptions on the degeneracy, locality, spectral width, or spectral gap of the Hamiltonian, and the underlying support-localization principle also extends to problems beyond exact diagonalization, such as sparse principal component analysis.