When a local Hamiltonian must be frustration-free

Abstract

A broad range of quantum optimisation problems can be phrased as the question whether a specific system has a ground state at zero energy, i.e.\ whether its Hamiltonian is frustration free. Frustration-free Hamiltonians, in turn, play a central role for constructing and understanding new phases of matter in quantum many-body physics. Unfortunately, determining whether this is the case is known to be a complexity-theoretically intractable problem. This makes it highly desirable to search for efficient heuristics and algorithms in order to, at least, partially answer this question. Here we prove a general criterion - a sufficient condition - under which a local Hamiltonian is guaranteed to be frustration free by lifting Shearer's theorem from classical probability theory to the quantum world. Remarkably, evaluating this condition proceeds via a fully classical analysis of a hard-core lattice gas at negative fugacity on the Hamiltonian's interaction graph which, as a statistical mechanics problem, is of interest in its own right. We concretely apply this criterion to local Hamiltonians on various regular lattices, while bringing to bear the tools of spin glass physics which permit us to obtain new bounds on the SAT/UNSAT transition in random quantum satisfiability. These also lead us to natural conjectures for when such bounds will be tight, as well as to a novel notion of universality for these computer science problems. Besides providing concrete algorithms leading to detailed and quantitative insights, this underscores the power of marrying classical statistical mechanics with quantum computation and complexity theory.

References in corpus (5)

• The power of quantum systems on a line
• Quantum Graphical Models and Belief Propagation
• Quantum Belief Propagation
• Cavity method for quantum spin glasses on the Bethe lattice
• Unfrustration Condition and Degeneracy of Qudits on Trees

Cited by in corpus (17)

• Machine Learning Topological States
• Quantum Many-Body Scars: A Quasiparticle Perspective
• Correlation Length versus Gap in Frustration-Free Systems
• Quantum Max-flow/Min-cut
• On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
• Certificates of quantum many-body properties assisted by machine learning
• Many-body systems with random spatially local interactions
• Random translation-invariant Hamiltonians and their spectral gaps
• Clustering in Hilbert space of a quantum optimization problem
• Multipartite entanglement and quantum error identification in $D$-dimensional cluster states
• On the critical finite-size gap scaling for frustration-free Hamiltonians
• A Novel Perspective on Ideal Chern Bands with Strong Short-Range Repulsion: Applications to Correlated Metals, Superconductivity, and Topological Order
• On efficiently solvable cases of Quantum k-SAT
• Models of interacting bosons with exact ground states: a unified approach
• A supersymmetric quantum perspective on the explicit large deviations for reversible Markov jump processes, with applications to pure and random spin chains
• Total Functions in QMA
• Quantum Lovász Local Lemma: Shearer's Bound is Tight