論文の概要: Quantum Lovász Local Lemma: Shearer's Bound is Tight

• arxiv url: http://arxiv.org/abs/1804.07055v5
• Date: Fri, 27 Sep 2024 08:37:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-02 16:31:45.697360
• Title: Quantum Lovász Local Lemma: Shearer's Bound is Tight
• Title（参考訳）: 量子Lovászローカルレムマ:シーラーの境界はタイト
• Authors: Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang,
• Abstract要約: シェラーの境界が QLLL に対して厳密であること、すなわち、最小を満たす部分空間の相対次元は独立集合によって完全に特徴づけられることを証明する。 また,シェラー境界を超える効率のよいCLLLのアルゴリズムを設計できることも示している。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: Lov\'asz Local Lemma (LLL) は、結合論と確率論において、弱い依存条件下で全ての悪い事象を避ける可能性を示す非常に強力なツールである。 Ambainis, Kempe, and Sattath (JACM 2012) では量子バージョン LLL (QLLL) が導入されたが、これは弱い依存条件下で全ての「悪い」ハミルトニアンを避ける可能性を示し、ランダムk-QSAT問題にQLLLを適用した。 Sattath, Morampudi, Laumann, and Moessner (PNAS 2015) は Ambainis, Kempe, Sattath の結果を拡張し、Shearer の境界が QLLL の十分条件であることを示した。 本稿では,この予想を裏付ける。 正確には、シェラーの境界が QLLL に対して厳密であること、すなわち、最小を満たす部分空間の相対次元が独立集合多項式によって完全に特徴づけられることを証明する。 この結果は、Gily\en と Sattath のアルゴリズム(FOCS 2017)の厳密さを示唆し、また格子ガス分配関数が、十分な量子量を持つハミルトンのほとんど全ての量子飽和度を完全に特徴付けることを示唆している(Sattath, Morampudi, Laumann and Moessner, PNAS 2015)。 また, 通勤用LLL (CLLL) についても検討した。 CLLLとQLLLのタイトな領域は一般的に異なることを証明している。 この結果から,シェラー境界を超える効率のよいCLLLのアルゴリズムを設計することが可能であることが示唆された。

関連論文リスト

• SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions [50.20087216230159]
  統計的クエリモデルにおける非ガウス成分分析(NGCA)の複雑さについて検討する。 本研究は, NGCAの場合, モーメントマッチング条件のみにおいて, ほぼ最適SQ下限を証明した。
  論文  参考訳（メタデータ） (2024-03-07T18:49:32Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。 本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
  論文  参考訳（メタデータ） (2023-10-27T09:16:58Z)
• Quantum Lower Bounds by Sample-to-Query Lifting [7.319050391449301]
  本稿では,量子サンプル対クエリリフト定理を用いて,量子クエリの下限を証明するための新しい手法を提案する。 位相/振幅推定やハミルトニアンシミュレーションなど,いくつかの既知の下界に対する統一的な証明を提供する。
  論文  参考訳（メタデータ） (2023-08-03T14:41:49Z)
• Quantum correlations on the no-signaling boundary: self-testing and more [0.39146761527401425]
  自己テストは、ハーディ型相関の既知の例を超えて、すべての非自明なクラスで可能であることを証明している。 最も単純なベルシナリオにおける$mathcalM$のすべての相関は、ベル対と射影測度を用いて達成可能な値の凸結合として達成できる。
  論文  参考訳（メタデータ） (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 the family of Hamiltonians with all low energy state with high complexity。 ここでは、NLTSと呼ばれるより弱いバージョンを証明し、局所項の(小さい)定数数に反する状態に対して量子回路の下限が示される。
  論文  参考訳（メタデータ） (2022-06-06T16:55:34Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Concentration of OTOC and Lieb-Robinson velocity in random Hamiltonians [0.0]
  異なる空間と時間における作用素間の通信は、ユニタリ進化の局所性の診断である。 本研究では、典型的なハミルトン多様体における可換作用素について研究する。
  論文  参考訳（メタデータ） (2021-03-16T16:37:19Z)
• A converse to Lieb-Robinson bounds in one dimension using index theory [1.3807918535446089]
  厳格な因果錐(または「光円錐」)を持つユニタリダイナミクスは量子セルオートマトン(QCA)という名前で広く研究されている。 指数論は頑健であり、一次元ALPUに完全に拡張されていることを示す。 開境界を持つ有限鎖の特別の場合、リーブ・ロビンソン境界を満たす任意のユニタリはそのようなハミルトニアンによって生成される。
  論文  参考訳（メタデータ） (2020-12-01T18:59:26Z)
• Metrizing Weak Convergence with Maximum Mean Discrepancies [88.54422104669078]
  本稿では、幅広い種類のカーネルに対する確率測度の弱収束を測る最大平均誤差(MMD)を特徴付ける。 我々は、局所コンパクトで非コンパクトなハウスドルフ空間において、有界連続ボレル可測核 k の MMD が確率測度の弱収束を測ることを証明する。
  論文  参考訳（メタデータ） (2020-06-16T15:49:33Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。 その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-01-23T16:47:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。