Quantum Lovász local lemma: Shearer’s bound is tight

DOI10.1145/3313276.3316392zbMath1433.68148arXiv1804.07055OpenAlexW2963530380MaRDI QIDQ5212787

Qian Li, Kun He, Jiapeng Zhang, Xiaoming Sun

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.07055

zbMATH Keywords

critical thresholdscommuting Lovász local lemmaquantum Lovász local lemmaquantum satisfiability problemShearer's bound

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Quantum computation (81P68) Combinatorial probability (60C05) Quantum algorithms and complexity in the theory of computing (68Q12) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)

Related Items

Total functions in QMA, On efficiently solvable cases of quantum \(k\)-SAT, Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma