論文の概要: Online Locality Meets Distributed Quantum Computing
- arxiv url: http://arxiv.org/abs/2403.01903v1
- Date: Mon, 4 Mar 2024 10:03:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-06 19:18:19.493186
- Title: Online Locality Meets Distributed Quantum Computing
- Title（参考訳）: オンラインローカリティと分散量子コンピューティング
- Authors: Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, Fran\c{c}ois
Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai,
Marc-Olivier Renou, V\'aclav Rozho\v{n}, Jukka Suomela
- Abstract要約: 我々は、局所チェック可能なラベル付け問題(s)の理論を古典的なLOCALモデルから最近研究されている多くのモデルに拡張する。
有限依存プロセスが古典的LOCALモデルよりも優れていることを示す。
- 参考スコア（独自算出の注目度）: 2.2470290096767003
- 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^* 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^* 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 trees: if we can
solve an LCL problem with locality $o(\log^{(5)} n)$ in the randomized
online-LOCAL model, we can solve it with locality $O(\log^* n)$ in the
classical deterministic LOCAL model.
Put together, these results show that in trees the set of LCLs that can be
solved with locality $O(\log^* n)$ is the same across all these models:
locality $O(\log^* n)$ in quantum-LOCAL, non-signaling model, dynamic-LOCAL, or
online-LOCAL is not stronger than locality $O(\log^* n)$ in the classical
deterministic LOCAL model.
- Abstract（参考訳）: 従来のLOCALモデルから、量子LOCALモデル、有限依存プロセス、非シグナリングモデル、動的LOCALモデル、オンラインLOCALモデル(STOC 2024, ICALP 2023)など、近年研究されている多くのモデルまで、局所チェック可能なラベル問題(LCL)の理論を拡張した。
まず,有限依存過程が古典的局所モデルよりも優れていることを示す。
LOCAL モデルにおいて、局所性$O(\log^* n)$ で解ける全ての LCL 問題は有限独立分布(局所性は一定)を持つことを示す。
特に、これは正規木に対して有限依存的な色付けを与え、Holroyd [2023] の開問題に答える。
これはまた、分散量子アドバンテージを理解するための新しい形式的障壁を導入する:非符号引数を使って$\theta(\log^* n)$ 複雑性クラスにおいて任意の lcl に対する量子アドバンテージを排除することはできない。
第2に、これらすべてのモデルの能力に制限を加えました。
この目的のために,SLOCALや動的LOCALをシミュレートするのに十分な強度を持つランダム化オンラインLOCALというモデルを導入し,非シグナリング分布や量子LOCALアルゴリズムをシミュレートするのに十分な強度を示す。
ランダム化されたオンライン局所モデルにおいて、局所性 $o(\log^{(5)} n)$ でlcl問題を解くことができるならば、古典的な決定論的局所モデルにおいて、局所性 $o(\log^* n)$ で解くことができる。
まとめると、木では局所性$O(\log^* n)$で解けるLCLの集合は、これらのモデルで同じである: Locality $O(\log^* n)$ in quantum-LOCAL, non-signaling model, dynamic-LOCAL, online-LOCAL is not strong than locality $O(\log^* n)$ in classical deterministic LOCAL model。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。