When a local Hamiltonian must be frustration-free

Area of Science:

• Quantum Information Science
• Quantum Many-Body Physics
• Computational Complexity Theory

Background:

• Many quantum optimization problems are equivalent to finding if a system's Hamiltonian is frustration-free (ground state at zero energy).
• Frustration-free Hamiltonians are fundamental for understanding novel quantum phases of matter.
• Determining if a Hamiltonian is frustration-free is computationally intractable.

Purpose of the Study:

• To develop efficient heuristics and algorithms for identifying frustration-free Hamiltonians.
• To establish a general criterion guaranteeing a local Hamiltonian is frustration-free.

Main Methods:

• Quantum lifting of Shearer's theorem from classical probability theory.
• Classical analysis of a hardcore lattice gas at negative fugacity on the interaction graph.
• Application of spin glass physics tools to random quantum satisfiability problems.

Main Results:

• A sufficient condition is proven for local Hamiltonians to be frustration-free.
• The evaluation of this condition involves classical statistical mechanics, specifically a lattice gas model.
• New bounds are derived for the satisfiable-to-unsatisfiable transition in random quantum satisfiability problems.

Conclusions:

• The study provides a novel, efficient method for analyzing quantum Hamiltonians by leveraging classical statistical mechanics.
• The findings offer insights into quantum phases of matter, computational complexity, and random quantum satisfiability.
• This work highlights the synergy between classical statistical mechanics, quantum computation, and complexity theory.