論文の概要: Online Locality Meets Distributed Quantum Computing

• arxiv url: http://arxiv.org/abs/2403.01903v3
• Date: Tue, 05 Nov 2024 16:57:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-06 14:55:37.650836
• Title: Online Locality Meets Distributed Quantum Computing
• Title（参考訳）: オンラインローカリティと分散量子コンピューティング
• Authors: Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhoň, Jukka Suomela,
• Abstract要約: 分散コンピューティングの古典的なLOCALモデルの拡張について、3行の研究が最近行われた。 局所チェック可能なラベリング問題(LCL)に対するこれらのモデルの機能と制限に関する新しい結果が証明された。 我々の研究は、分散環境での利点の限界を示唆しており、より厳密な境界を示すための新たな障壁も示しています。
• 参考スコア（独自算出の注目度）: 2.3821076274208552
• License:
• Abstract: We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-signaling distributions [e.g. STOC 2024], B. finitely-dependent processes [e.g. Forum Math. Pi 2016], and C. locality in online graph algorithms and dynamic graph algorithms [e.g. ICALP 2023]. We prove new results on the capabilities and limitations of all of these models of computing, for locally checkable labeling problems (LCLs). We show that all these settings can be sandwiched between the classical LOCAL model and what we call the randomized online-LOCAL model. Our work implies limitations on the quantum advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds. Our main technical results are these: 1. All LCL problems solvable with locality $O(\log^\star n)$ in the classical deterministic LOCAL model admit a finitely-dependent distribution with locality $O(1)$. This answers an open question by Holroyd [2024], and also presents a new barrier for proving bounds on distributed quantum advantage using causality-based arguments. 2. In rooted trees, if we can solve an LCL problem with locality $o(\log \log \log n)$ in the randomized online-LOCAL model (or any of the weaker models, such as quantum-LOCAL), we can solve it with locality $O(\log^\star n)$ in the classical deterministic LOCAL model. One of many implications is that in rooted trees, $O(\log^\star n)$ locality in quantum-LOCAL is not stronger than $O(\log^\star n)$ locality in classical LOCAL.
• Abstract（参考訳）: A.分散量子コンピューティングと非シグナリング分布 [eg STOC 2024]、B.有限依存プロセス [eg Forum Math. Pi 2016]、C.オンライングラフアルゴリズムと動的グラフアルゴリズム [eg ICALP 2023]。 ローカルチェック可能なラベリング問題(LCL)に対して,これら全ての計算モデルの能力と限界を新たに証明する。 これらの設定はすべて,従来のLOCALモデルとランダム化オンラインLOCALモデルとを挟むことができることを示す。 我々の研究は、分散環境での量子的優位性に関する制限を暗示しており、より厳密な境界を証明するための新たな障壁も示している。 主な技術的成果は以下のとおりです。 1. 古典的決定論的LOCALモデルにおいて、局所性$O(\log^\star n)$で解ける全てのLCL問題は、局所性$O(1)$で有限依存分布を持つ。 このことはHolroyd [2024] のオープンな疑問に答え、因果性に基づく議論を用いて分散量子優位性上の境界を証明するための新しい障壁を示す。 2. ルート木では、局所性$o(\log \log \log n)$をランダム化オンラインLOCALモデル(または量子LOCALのようなより弱いモデル)で解くことができれば、古典的決定論的LOCALモデルにおいて局所性$O(\log^\star n)$で解ける。 根木において、量子LOCALにおける$O(\log^\star n)$局所性は古典的LOCALにおける$O(\log^\star n)$局所性よりも強くない。

関連論文リスト

• Distributed Quantum Advantage for Local Problems [3.1024627815534593]
  分散コンピューティングの古典的ランダム化LOCALモデルと,その量子的モデルとの超コンスタントな分離を示す。 本稿では,局所的制約のみを用いて定義した反復GHZ問題を提案する。
  論文  参考訳（メタデータ） (2024-11-05T16:38:49Z)
• Generating multipartite nonlocality to benchmark quantum computers [0.0]
  量子コンピュータは大規模に$n$の非局所性を生み出すのに利用できることを示す。 これにより、量子ビットの数や接続性に関わらず、古典的でない相関をベンチマークすることができる。
  論文  参考訳（メタデータ） (2024-06-11T19:03:35Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• No distributed quantum advantage for approximate graph coloring [2.8518543181146785]
  分散アルゴリズムを用いた$c$-coloring $chi$-chromatic graphの難易度を,ほぼ完全に評価する。 これらの問題は、分散量子の優位性を認めないことを示している。
  論文  参考訳（メタデータ） (2023-07-18T17:17:27Z)
• Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms [0.0]
  確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。 従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。 Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
  論文  参考訳（メタデータ） (2023-04-06T02:18:52Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs [6.262125516926276]
  すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。 1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
  論文  参考訳（メタデータ） (2021-06-10T16:28:23Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)

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

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