2026-07-20T11:15:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24541 2025-12-16T14:00:34Z ddc:004 open_access

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians Le Gall, François approximation algorithms quantum computing dequantization 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 poly (1/χ,n) time and 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 to a 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik François Le Gall 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.73 urn:nbn:de:0030-drops-245419 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.73 eng https://creativecommons.org/licenses/by/4.0/legalcode