On preparing ground states of gapped Hamiltonians: An efficient Quantum Lov\'asz Local Lemma

Understand

A frustration-free local Hamiltonian has the property that its ground state minimises the energy of all local terms simultaneously.

• In general, even deciding whether a Hamiltonian is frustration-free is a hard task, as it is closely related to the QMA1-complete quantum satisfiability problem (QSAT) -- the quantum analogue of SAT, which is the archetypal NP-complete problem in classical computer science.
• This connection shows that the frustration-free property is not only relevant to physics but also to computer science.
• The Quantum Lov\'asz Local Lemma (QLLL) provides a sufficient condition for frustration-freeness.