文献

J-GLOBAL ID：202002232521868797   整理番号：20A1511828

量子Lovasz局所補題:シアーの束縛はタイトである【JST・京大機械翻訳】

Quantum Lovasz local lemma: Shearer’s bound is tight

著者 (4件)： He Kun (Institute of Computing Technology at Chinese Academy of Sciences, China / University of Chinese Academy of Sciences, China) ,  Li Qian (Shenzhen Institute of Computing Sciences, China / Shenzhen University, China) ,  Sun Xiaoming (Institute of Computing Technology at Chinese Academy of Sciences, China / University of Chinese Academy of Sciences, China) ,  Zhang Jiapeng (University of California at San Diego, USA)
資料名： ACM Proceedings  (ACM Proceedings)
号： STOC 2019  ページ： 461-472  発行年： 2019年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： Lovasz Local Lemma(LLL)は,いくつかの”弱依存”条件下で全ての”bad”事象を回避する可能性を示すために,結合器と確率理論における非常に強力なツールである。過去数十年にわたって,LLLのアルゴリズム的側面も,理論的コンピュータ科学において多くの注目を引きつけた。抽象バージョンLLL(ALLL)が,シヤによって与えられたタイトな判定基準を,与えた。可変バージョンLLL(VLLL)に対して,シヤの境界は,一般的には堅くないことが判明した。最近,Ambanisらは量子バージョンLLL(QLLL)を導入し,量子充足可能性問題に対して強力であることを示した。本論文では,QLLLに対してシヤの境界がタイトであること,すなわち,最小満足部分空間の相対次元が独立集合多項式によって完全に特性化され,Sattathらによって提案された推測を確証した。また,著者らの結果は,GilyenとSattathのアルゴリズムの堅さを示し,格子ガス分配関数が,十分に大きなquditsを持つほとんどすべてのハミルトニアンに対して量子充足可能性を完全に特徴付けることを意味する。LLL(CLLL),LLLは,文献において広く研究されている局所ハミルトニアンを交換するために,ここで調査する。CLLLとQLLLのタイト領域は一般に異なることを証明した。この結果は,シヤの境界を越えてまだ効率的であるCLLLのためのアルゴリズムを設計することが可能であることを意味した。LLLsの応用において,対称ケースは最も一般的であり,すなわち,イベントは同じ確率で,ハミルトニアンは同じ相対次元を有する。著者らは,対称VLLLとシヤの境界の間のギャップに関する最初の下限を与えた。この結果は,量子と古典的制約充足問題の間の分離に関する定量的研究として見ることができる。さらに,対称CLLLに対して同様の結果を得た。応用として,いくつかの最も一般的な格子に対してVLLLとCLLLの臨界閾値に関する下限を与えた。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ハミルトニアン ,  アルゴリズム ,  対称性 ,  多項式 ,  *シヤー ,  結合器 ,  計算機科学 ,  確率論 ,  格子気体 ,  臨界 ,  分配関数 ,  充足可能性問題 ,  制約充足問題
準シソーラス用語： 部分空間 ,  *補題 , 【Automatic Indexing@JST】

著者キーワード (5件)： せん断器の限界 ,  Lovasz Local Lemmaの通勤 ,  臨界閾値 ,  量子Lovasz局所補題 ,  量子充足可能性問題

分類 (2件)： 無線通信一般  (ND08010L) ,  信号理論  (ND02020G)

タイトルに関連する用語 (4件)： 量子 ,  補題 ,  シアー ,  束縛