Posted

Gabriel Waite (Oct 01 2025).
Abstract: We show that the Guided Local Hamiltonian problem for stoquastic Hamiltonians is (promise) BPP-hard. The Guided Local Hamiltonian problem is a variant of the Local Hamiltonian problem that incorporates an additional input known as a guiding state, which is promised to overlap with the ground state. For a range of local Hamiltonian families, this problem is (promise) BQP-hard, though for stoquastic Hamiltonians, the complexity was previously unknown. Our results are achieved by first reducing from quantum-inspired BPP circuits to 6-local stoquastic Hamiltonians. We prove particular classes of quantum states, known as semi-classical encoded subset states, can guide the estimation of the ground state energy. Subsequent analysis shows the BPP-hardness is not dependent on the locality, i.e., the result holds for 2-local stoquastic Hamiltonians. Additional arguments further the BPP-hardness to Hamiltonians restricted to a square lattice. We also find for stoquastic Hamiltonians with a fixed local constraint on a subset of the system qubits, the Guided Local Hamiltonian problem is BQP-hard.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!