aiqbench analysis
This paper establishes rigorous theoretical barriers demonstrating that classical algorithms cannot efficiently solve guided ground-state preparation or energy estimation for a broad class of stoquastic Hamiltonians, even with optimal warm-start distributions. By leveraging high-degree spectral expanders and self-similar trees, the authors extend prior work to prove that these specific quantum problems offer genuine computational advantages over any classical approach. The findings solidify the complexity separation between classical sampling and quantum state preparation for this important subclass of quantum systems.
Dequantization Barriers for Guided Stoquastic Hamiltonians
arXiv:2602.23183v2 Announce Type: replace Abstract: We construct a probability distribution, induced by the Perron--Frobenius eigenvector of an exponentially large graph, that cannot be efficiently sampled by any classical algorithm, even when given 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. We further show that even estimating the ground-state energy of that Hamiltonian remains classically hard. Our results suggest 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 (such as the LPS Ramanujan graphs) to which self-similar trees are attached. This builds on and extends prior work of Gily\'en, 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 or energy estimation, while also providing a derandomized construction.
Abstract:We construct a probability distribution, induced by the Perron--Frobenius eigenvector of an exponentially large graph, that cannot be efficiently sampled by any classical algorithm, even when given 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. We further show that even estimating the ground-state energy of that Hamiltonian remains classically hard. Our results suggest 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 (such as the LPS Ramanujan graphs) 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 or energy estimation, while also providing a derandomized construction.
Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
arXiv:2602.23183 [quant-ph]
(or arXiv:2602.23183v2 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2602.23183 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 272 words
Related coverage
Gibbs state preparation through quantum decoding
arXiv · Oct 5, 2026
Ground state energy estimation and preparation by the truncated power method
arXiv · Oct 6, 2026
Quantum-Enhanced Algorithm Simulates 127-Qubit Dynamics Classically
Quantum Zeitgeist · Jun 14, 2026
Zak Phase Quantization without Global Symmetry through Destructive Interference
arXiv · Oct 12, 2026