Dequantization Barriers for Guided Stoquastic Hamiltonians

• URL: http://arxiv.org/abs/2602.23183v1
• Date: Thu, 26 Feb 2026 16:40:32 GMT
• Title: Dequantization Barriers for Guided Stoquastic Hamiltonians
• Abstract summary: In the quantum setting, this problem can be viewed as preparing the ground state of a stoquastic Hamiltonian given a guiding state as input.<n>Our result suggests that no efficient classical algorithm can solve a broad class of stoquastic ground-state problems.
• Score: 0.6308539010172308
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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

• Alternative adiabatic quantum dynamics with algorithmic applications [0.038233569758620044]
  In adiabatic quantum computing the aim is to track an eigenstate as the Hamiltonian changes.<n>We propose several alternative processes that achieve the same goal, but can easily be implemented on a gate-based quantum computer.
  arXiv  Detail & Related papers  (2026-05-28T15:48:15Z)
• SpinGQE: A Generative Quantum Eigensolver for Spin Hamiltonians [42.007194397302825]
  Ground state search is central to quantum computing.<n>We present SpinGQE, an extension of the Generative Quantum Eigensolver framework to spin Hamiltonians.<n>We employ a transformer-based decoder to learn over quantum circuits that produce low-energy states.
  arXiv  Detail & Related papers  (2026-03-25T13:38:15Z)
• Observation of Improved Accuracy over Classical Sparse Ground-State Solvers using a Quantum Computer [4.158044333915682]
  We show that a hybrid quantum-classical algorithm can outperform purely classical, off-the-shelf selected configuration interaction methods.<n>A sample-based quantum diagonalization algorithm, run on an IBM Heron R3 processor, succeeds at the same task.
  arXiv  Detail & Related papers  (2026-03-03T20:11:28Z)
• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs [0.13654846342364307]
  We design two variational algorithms to optimize specific 2-local Hamiltonians defined on graphs.<n>We develop formulae to analyze the energy achieved by these algorithms with high probability over random regular graphs in the infinite-size limit.<n>We show that with just five layers of our algorithm, we can already prepare states within 1.62% error of the ground state energy for QMC on an infinite 1D ring.
  arXiv  Detail & Related papers  (2024-12-19T18:27:39Z)
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations [0.06022769903412461]
  We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches a lower bound for a class of classical local spin Hamiltonians.<n>We show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision.
  arXiv  Detail & Related papers  (2024-11-08T17:51:18Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Classical Algorithms for Hamiltonian Dynamics Mean Value and Guided Local Hamiltonian Problem [9.550310003133555]
  We introduce an efficient classical algorithm for simulating the short-time dynamics of arbitrary local quantum systems.<n>We also present a tailored quantum algorithm that efficiently solves the guided local Hamiltonian (GLH) problem to constant additive error.
  arXiv  Detail & Related papers  (2024-09-06T09:59:12Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  We generalize the Arimoto-Blahut algorithm to a general function defined over Bregman-divergence system.<n>This algorithm can be applied to classical and quantum rate-distortion theory.
  arXiv  Detail & Related papers  (2024-08-10T06:16:24Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Quantum Assisted Eigensolver [0.0]
  We propose a hybrid quantum-classical algorithm for approxing the ground state and ground state energy of a Hamiltonian. The output from the quantum part of the algorithm is utilized as input for the classical computer.
  arXiv  Detail & Related papers  (2020-09-23T08:33:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.