Quantum Lovász Local Lemma: Shearer's Bound is Tight

• URL: http://arxiv.org/abs/1804.07055v5
• Date: Fri, 27 Sep 2024 08:37:35 GMT
• Title: Quantum Lovász Local Lemma: Shearer's Bound is Tight
• Authors: Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang,
• Abstract summary: 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. We also show that it is possible to design an algorithm for CLLL which is still efficient beyond Shearer's bound.
• Score: 17.44514830974561
• License:
• Abstract: The Lov\'asz 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 conditions. In a seminal paper, Ambainis, Kempe, and Sattath (JACM 2012) introduced a quantum version LLL (QLLL) which shows the possibility of avoiding all ``bad" Hamiltonians under some weakly dependent condition, and applied QLLL to the random k-QSAT problem. Sattath, Morampudi, Laumann, and Moessner (PNAS 2015) extended Ambainis, Kempe, and Sattath's result and showed that Shearer's bound is a sufficient condition for QLLL, and conjectured that Shearer's bound is indeed the tight condition for QLLL. In this paper, we affirm this conjecture. Precisely, 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. Our result implies the tightness of Gily\'en and Sattath's algorithm (FOCS 2017), and also implies that the lattice gas partition function fully characterizes quantum satisfiability for almost all Hamiltonians with large enough qudits (Sattath, Morampudi, Laumann and Moessner, PNAS 2015). The commuting LLL (CLLL), which focuses on commuting local Hamiltonians, is also investigated here. We prove that the tight regions of CLLL and QLLL are different in general. This result indicates that it is possible to design an algorithm for CLLL which is still efficient beyond Shearer's bound.

Related papers

• SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions [50.20087216230159]
  We study the complexity of Non-Gaussian Component Analysis (NGCA) in the Statistical Query model. We prove near-optimal SQ lower bounds for NGCA under the moment-matching condition only.
  arXiv  Detail & Related papers  (2024-03-07T18:49:32Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  We derive a new convergence guarantee of Adam, with only an $L$-smooth condition and a bounded noise variance assumption. Our proof utilizes novel techniques to handle the entanglement between momentum and adaptive learning rate.
  arXiv  Detail & Related papers  (2023-10-27T09:16:58Z)
• Quantum Lower Bounds by Sample-to-Query Lifting [7.319050391449301]
  We propose an arguably new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem. We provide unified proof for some known lower bounds, including those for phase/amplitude estimation and Hamiltonian simulation.
  arXiv  Detail & Related papers  (2023-08-03T14:41:49Z)
• Quantum correlations on the no-signaling boundary: self-testing and more [0.39146761527401425]
  We prove that self-testing is possible in all nontrivial Classes beyond the known examples of Hardy-type correlations. All correlations of $mathcalM$ in the simplest Bell scenario are attainable as convex combinations of those achievable using a Bell pair and projective measurements.
  arXiv  Detail & Related papers  (2022-07-28T01:55:21Z)
• A construction of Combinatorial NLTS [22.539300644593936]
  NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] posits that there exist families of Hamiltonians with all low energy states of high complexity. Here, we prove a weaker version called the NLTS, where a quantum circuit lower bound is shown against states that violate a (small) constant fraction of local terms.
  arXiv  Detail & Related papers  (2022-06-06T16:55:34Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Concentration of OTOC and Lieb-Robinson velocity in random Hamiltonians [0.0]
  Commutator between operators at different space and time has been a diagnostic for locality of unitary evolution. In this work, we study commutators in typical Hamiltonians.
  arXiv  Detail & Related papers  (2021-03-16T16:37:19Z)
• A converse to Lieb-Robinson bounds in one dimension using index theory [1.3807918535446089]
  Unitary dynamics with a strict causal cone (or "light cone") have been studied extensively, under the name of quantum cellular automata (QCAs) We show that the index theory is robust and completely extends to one-dimensional ALPUs. For the special case of finite chains with open boundaries, any unitary satisfying the Lieb-Robinson bound may be generated by such a Hamiltonian.
  arXiv  Detail & Related papers  (2020-12-01T18:59:26Z)
• Metrizing Weak Convergence with Maximum Mean Discrepancies [88.54422104669078]
  This paper characterizes the maximum mean discrepancies (MMD) that metrize the weak convergence of probability measures for a wide class of kernels. We prove that, on a locally compact, non-compact, Hausdorff space, the MMD of a bounded continuous Borel measurable kernel k, metrizes the weak convergence of probability measures if and only if k is continuous.
  arXiv  Detail & Related papers  (2020-06-16T15:49:33Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  We design and analyze CascadeBAI, an algorithm for finding the best set of $K$ items. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes.
  arXiv  Detail & Related papers  (2020-01-23T16:47:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.