← 研踪 PaperTrailarXiv:2602.23183 · v2
Dequantization Barriers for Guided Stoquastic Hamiltonians
首次提交 2026-02-27 00:40
版本更新 2026-11-05 20:50
雷达观测 2026-11-06 12:09
摘要
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.
作者备注：36 pages, 5 figures; v2: new hardness result for energy estimation, improved exposition
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-05 20:50 · 最新观测版本
Dequantization Barriers for Guided Stoquastic Hamiltonians
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.
查看此版本解读 →查看此版本原文 ↗