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

• arxiv url: http://arxiv.org/abs/2403.01903v2
• Date: Tue, 9 Apr 2024 10:50:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-10 19:27:41.002510
• 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要約: 我々は、局所チェック可能なラベル問題(LCL)の理論を古典的なLOCALモデルから他の多くのモデルに拡張する。 有限依存プロセスが古典的LOCALモデルよりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 2.3821076274208552
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We extend the theory of locally checkable labeling problems (LCLs) from the classical LOCAL model to a number of other models that have been studied recently, including the quantum-LOCAL model, finitely-dependent processes, non-signaling model, dynamic-LOCAL model, and online-LOCAL model [e.g. STOC 2024, ICALP 2023]. First, we demonstrate the advantage that finitely-dependent processes have over the classical LOCAL model. We show that all LCL problems solvable with locality $O(\log^\star n)$ in the LOCAL model admit a finitely-dependent distribution (with constant locality). In particular, this gives a finitely-dependent coloring for regular trees, answering an open question by Holroyd [2023]. This also introduces a new formal barrier for understanding the distributed quantum advantage: it is not possible to exclude quantum advantage for any LCL in the $\Theta(\log^\star n)$ complexity class by using non-signaling arguments. Second, we put limits on the capabilities of all of these models. To this end, we introduce a model called randomized online-LOCAL, which is strong enough to simulate e.g. SLOCAL and dynamic-LOCAL, and we show that it is also strong enough to simulate any non-signaling distribution and hence any quantum-LOCAL algorithm. We prove the following result for rooted trees: if we can solve an LCL problem with locality $o(\log \log n)$ in the randomized online-LOCAL model, we can solve it with locality $O(\log^\star n)$ in the classical deterministic LOCAL model. Put together, these results show that in rooted trees the set of LCLs that can be solved with locality $O(\log^\star n)$ is the same across all these models: classical deterministic and randomized LOCAL, quantum-LOCAL, non-signaling model, dynamic-LOCAL, and deterministic and randomized online-LOCAL.
• Abstract（参考訳）: 従来のLOCALモデルから、量子LOCALモデル、有限依存プロセス、非シグナリングモデル、動的LOCALモデル、オンラインLOCALモデル(例えば STOC 2024, ICALP 2023)など、近年研究されている多くのモデルまで、局所チェック可能なラベリング問題(LCL)の理論を拡張した。 まず、有限依存プロセスが古典的LOCALモデルよりも優れていることを示す。 LOCAL モデルにおいて、局所性$O(\log^\star n)$ で解ける全ての LCL 問題は有限独立分布(局所性は一定)を持つことを示す。 特に、これは正規木に対して有限依存的な色付けを与え、Holroyd [2023] の開問題に答える。 これはまた、分散量子優位性を理解するための新しい公式な障壁も導入している: $\Theta(\log^\star n)$ complexity class における任意の LCL に対する量子優位性は、非シグナリング引数を用いて除外することはできない。 第2に、これらすべてのモデルの能力に制限を加えました。 そこで本研究では,eg SLOCALとDynamic-LOCALをシミュレートするのに十分な強度を持つランダム化オンラインLOCALというモデルを導入し,非シグナリング分布や量子LOCALアルゴリズムをシミュレートするのに十分な強度を示す。 局所性$o(\log \log n)$をランダム化オンライン-LOCALモデルで解くことができれば、局所性$O(\log^\star n)$を古典的決定論的LOCALモデルで解くことができる。 これらの結果は、ルート木において、局所性$O(\log^\star n)$で解けるLCLの集合は、古典的決定論的およびランダム化LOCAL、量子LOCAL、非シグナリングモデル、動的LOCAL、決定論的およびランダム化オンラインLOCALのすべてのモデルで同じであることを示している。

関連論文リスト

• 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)

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

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