Ground state energy estimation and preparation by the truncated power method

Abstract:The Guided Local Hamiltonian Problem (GLHP) is the problem of ground state energy estimation and preparation given a guiding state having good overlap with the true ground state. The problem is known to be BQP-complete for small error but is classically tractable for larger error. In this work, we identify an orthogonal regime in which the problem is classically tractable, namely when the true ground state $\psi$ has polynomially bounded $\ell_1$-norm. In particular, we show that the Truncated Power Method (TPM), a classical algorithm introduced by Kirby et al. in the quantum context, has a runtime that is polynomially comparable to quantum algorithms for GLHP in all relevant parameters, except for an extra factor of $\|\psi\|_1^2$. In other words, if $\|\psi\|_1^2$ is polynomially bounded, then TPM dequantizes quantum algorithms for GLHP.

Quantum Physics (quant-ph); Numerical Analysis (math.NA)

arXiv:2610.05627 [quant-ph]

(or arXiv:2610.05627v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.05627 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

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.