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

DOI10.1145/3313276.3316392zbMath1433.68148arXiv1804.07055OpenAlexW2963530380WikidataQ130916920 ScholiaQ130916920MaRDI 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 (3)

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

This page was built for publication: Quantum Lovász local lemma: Shearer’s bound is tight