Complete Characterization of the Ground Space Structure of Two-Body Frustration-Free Hamiltonians for Qubits

Abstract

The problem of finding the ground state of a frustration-free Hamiltonian carrying only two-body interactions between qubits is known to be solvable in polynomial time. It is also shown recently that, for any such Hamiltonian, there is always a ground state that is a product of single- or two-qubit states. However, it remains unclear whether the whole ground space is of any succinct structure. Here, we give a complete characterization of the ground space of any two-body frustration-free Hamiltonian of qubits. Namely, it is a span of tree tensor network states of the same tree structure. This characterization allows us to show that the problem of determining the ground state degeneracy is as hard as, but no harder than, its classical analog.

5pages, 3 figures

References in corpus (5)

• The Quantum Transverse Field Ising Model on an Infinite Tree from Matrix Product States
• On product, generic and random generic quantum satisfiability
• No-go Theorem for One-way Quantum Computing on Naturally Occurring Two-level Systems
• Solving frustration-free spin systems
• Ground states of unfrustrated spin Hamiltonians satisfy an area law

Cited by in corpus (11)

• Quantum spin systems for measurement-based quantum computation
• Measurement-Based Quantum Computing with Valence-Bond-Solids
• Ground-State Spaces of Frustration-Free Hamiltonians
• Quantum 3-SAT is QMA1-complete
• The pair-flip model: a very entangled translationally invariant spin chain
• The 7 faces of quantum NP
• Models of interacting bosons with exact ground states: a unified approach
• Quantum marginals, faces, and coatoms
• A variation principle for ground spaces
• Difficult instances of the counting problem for 2-quantum-SAT are very atypical
• Complexity of Fermionic 2-SAT