Quantum Lovász Local Lemma: Shearer's Bound is Tight
share
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 holds was given by Shearer [shearer1985problem]. It turns out that Shearer's bound is generally not tight for variable version LLL (VLLL) [he2017variable]. Recently, Ambainis et al. introduced a quantum version LLL (QLLL), which was then shown to be powerful for quantum satisfiability problem. In this paper, we prove that Shearer's bound is tight for QLLL, affirming a conjecture proposed by Sattath et. al. Our result shows the tightness of Gilyén and Sattath's algorithm, and implies that the lattice gas partition function fully characterizes quantum satisfiability for almost all Hamiltonians with large enough qudits. Commuting LLL (CLLL), LLL for commuting local Hamiltonians which are widely studied in literature, is also investigated here. We prove that the tight regions of CLLL and QLLL are generally different. Thus, the efficient region of algorithms for CLLL can go beyond shearer's bound. Our proof is by first bridging CLLL and VLLL on a family of interaction bipartite graphs and then applying the tools of VLLL, e.g., the gapless/gapful results, to CLLL. We also provide a sufficient and necessary condition for deciding whether the tight regions of QLLL and CLLL are the same for a given interaction bipartite graph.
READ FULL TEXT