---
abstract: |
    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  [@moser2010constructive; @kolipaka2011moser; @harvey2015algorithmic]. A tight criterion under which the *abstract* version LLL (ALLL) 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. [@ambainis2012quantum] introduced a quantum version LLL (QLLL), which was then shown to be powerful for the quantum satisfiability problem.

    In this paper, we prove that Shearer’s bound is tight for QLLL, i.e., the relative dimension of the smallest satisfying subspace is completely characterized by the independent set polynomial, affirming a conjecture proposed by Sattath et al. [@pnas; @Morampudi2018Many]. Our result also shows the tightness of Gily[é]{}n and Sattath’s algorithm [@gilyen2016preparing], and implies that the lattice gas partition function fully characterizes quantum satisfiability for almost all Hamiltonians with large enough qudits [@pnas].

    Commuting LLL (CLLL), LLL for commuting local Hamiltonians which are widely studied in the literature, is also investigated here. We prove that the tight regions of CLLL and QLLL are different in general. This result might imply that it is possible to design an algorithm for CLLL which is still efficient beyond Shearer’s bound.

    In applications of LLLs, the symmetric cases are most common, i.e., the events are with the same probability  [@gebauer2016local; @gebauer2009lovasz] and the Hamiltonians are with the same relative dimension  [@ambainis2012quantum; @pnas]. We give the first lower bound on the gap between the symmetric VLLL and Shearer’s bound. Our result can be viewed as a quantitative study on the separation between quantum and classical constraint satisfaction problems. Additionally, we obtain similar results for the symmetric CLLL. As an application, we give lower bounds on the critical thresholds of VLLL and CLLL for several of the most common lattices.
author:
- 'Kun He$^{*}$, Qian Li $^{\dag}$, Xiaoming Sun$^{*}$ and Jiapeng Zhang $^{\ddag}$'
bibliography:
- 'reference.bib'
title: 'Quantum Lov[á]{}sz Local Lemma: Shearer’s Bound is Tight'
---

Introduction
============

Definitions and Notations {#sec:definitionsandnotations}
=========================

QLLL: Shearer’s Bound Is Tight {#sec:ShearerBoundisTight}
==============================

\[sec: qlll\]

CLLL: Beyond Shearer’s Bound {#sec:tightregionforclll}
============================

In this section, we focus on the tight region of commuting LLL.

Acknowledgement {#acknowledgement .unnumbered}
===============

We are grateful to Andr[á]{}s Gily[é]{}n for his manuscript about VLLL and letting us know the problem whether Shearer’s bound is tight for QLLL. We also thank the anonymous referees for their valuable comments.

Kun He, Qian Li and Xiaoming Sun’s work was supported in part by the National Natural Science Foundation of China Grants No. 61433014, 61832003, 61761136014, 61872334, 61801459, the 973 Program of China Grant No. 2016YFB1000201, and the Strategic Priority Research Program of Chinese Academy of Sciences Grant No. XDB28000000. Jiapeng Zhang’s work was supported by NSF grant CCF-1614023.
