Yassine Hamoudi

Stoquastic Hamiltonians form an important class of quantum Hamiltonians, with applications to combinatorial optimization, analog computation, and adiabatic algorithms. The absence of a sign problem makes stoquastic Hamiltonians particularly amenable to classical simulation and dequantization techniques. Many such approaches rely on the availability of a guiding state, that is, a state with non-negligible overlap with the true ground state. This raises a fundamental question: can a suitably chosen guiding state always suffice to dequantize the preparation of stoquastic ground states? We answer this question in the negative by constructing a family of stoquastic Hamiltonians, represented as adjacency matrices of carefully designed graphs, for which classical algorithms cannot efficiently sample from the ground-state distribution -- even given the optimal guiding state. Our graphs are built from a certain type of 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. We strengthen their result by ruling out any classical algorithm for guided ground-state preparation, while also providing a derandomized construction.