Gabriel Waite, Karl Lin, Samuel J Elman, Michael J Bremner (Oct 01 2025).
Abstract: This work characterises families of guiding states for the Guided Local Hamiltonian problem, revealing new connections between physical constraints and computational complexity. Focusing on states motivated by Quantum Chemistry and Hamiltonian Complexity, we extend prior BQP-hardness results beyond semi-classical subset states. We demonstrate that broader state families preserve hardness, while maintaining classical tractability under practical parameter regimes. Crucially, we provide a constructive proof of BQP containment for the canonical problem, showing the problem is BQP-complete when provided with a polynomial-size classical description of the guiding state. Our results show quantum advantage persists for physically meaningful state classes, and classical methods remain viable when guiding states admit appropriate descriptions. We identify a Goldilocks zone of guiding states that are efficiently preparable, succinctly described, and sample-query accessible, allowing for a meaningful comparison between quantum and classical approaches. Our work furthers the complexity landscape for ground state estimation problems, presenting steps toward experimentally relevant settings while clarifying the boundaries of quantum advantage.
