Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all “bad” events under some “weakly dependent” condition. Over the last decades, the algorithmic aspect of LLL has also attracted lots of attention in theoretical computer science. A tight criterion under which the abstract version LLL (ALLL) holds was given by Shearer. It turns out that Shearer’s bound is generally not tight for variable version LLL (VLLL). Recently, Ambainis et al. introduced a quantum version LLL (QLLL), which was then shown to be powerful for the quantum satisfiability problem.
The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lov\'asz Local Lemma gives a sufficient condition for a Quantum Satisfiability problem to be satisfiable~\cite{ambainis2012quantum}, by generalizing the classical Lov\'asz Local Lemma. The next natural question that arises is: can a satisfying quantum state be \emph{efficiently} found, when these conditions hold? In this work we present such an algorithm, with the additional requirement that all the projectors commute. The proof follows the information theoretic proof given by Moser's breakthrough result in the classical setting~\cite{moser2009constructiveSTOC}. Similar results were independently published in~\cite{cubitt2011constructive, cubitt2013quantum}.