Ground state connectivity of local Hamiltonians

Abstract

The study of ground state energies of local Hamiltonians has played a fundamental role in quantum complexity theory. In this paper, we take a new direction by introducing the physically motivated notion of "ground state connectivity" of local Hamiltonians, which captures problems in areas ranging from quantum stabilizer codes to quantum memories. Roughly, "ground state connectivity" corresponds to the natural question: Given two ground states |ψ> and |ϕ> of a local Hamiltonian H, is there an "energy barrier" (with respect to H) along any sequence of local operations mapping |ψ> to |ϕ>? We show that the complexity of this question can range from QCMA-complete to PSPACE-complete, as well as NEXP-complete for an appropriately defined "succinct" version of the problem. As a result, we obtain a natural QCMA-complete problem, a goal which has generally proven difficult since the conception of QCMA over a decade ago. Our proofs rely on a new technical tool, the Traversal Lemma, which analyzes the Hilbert space a local unitary evolution must traverse under certain conditions. We show that this lemma is essentially tight with respect to the length of the unitary evolution in question.

31 pages; v3 is published journal version. Various minor updates over v2, including observing that our QCMA-hardness result actually also holds for frustration-free Hamiltonians (FF-GSCON). Thank you to anonymous referees for their feedback

References in corpus (9)

• Coding Theorem and Strong Converse for Quantum Channels
• All non-classical correlations can be activated into distillable entanglement
• Quantum Hamiltonian Complexity
• Quantum NP - A Survey
• Topological phases and quantum computation
• Computational Difficulty of Computing the Density of States
• BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
• The k-local Pauli Commuting Hamiltonians Problem is in P
• Approximation, Proof Systems, and Correlations in a Quantum World

Cited by in corpus (13)

• Quantum Hamiltonian Complexity
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Quantum Proofs
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• On girth and the parameterized complexity of token sliding and token jumping
• The pair-flip model: a very entangled translationally invariant spin chain
• QCMA hardness of ground space connectivity for commuting Hamiltonians
• The Complexity of Translationally Invariant Problems beyond Ground State Energies
• The 7 faces of quantum NP
• Some results on Vertex Separator Reconfiguration
• Pinned QMA: The power of fixing a few qubits in proofs
• Uniform Diagonalization Theorem for Complexity Classes of Promise Problems including Randomized and Quantum Classes
• Shorter unentangled proofs for Ground State Connectivity