論文の概要: Distributed Quantum Advantage in Locally Checkable Labeling Problems
- arxiv url: http://arxiv.org/abs/2504.05191v1
- Date: Mon, 07 Apr 2025 15:42:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-08 14:08:54.408875
- Title: Distributed Quantum Advantage in Locally Checkable Labeling Problems
- Title（参考訳）: 局所チェック可能なラベリング問題における分散量子アドバンテージ
- Authors: Alkida Balliu, Filippo Casagrande, Francesco d'Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, Jukka Suomela,
- Abstract要約: LOCALモデル分散コンピューティングにおいて、分散量子優位性を認める局所チェック可能なラベル問題(LCL)の最初の例を示す。
我々の問題は量子モデルにおける$O(log n)$通信ラウンドで解決できるが、古典モデルでは$Omega(log n)$通信ラウンドを必要とする。
- 参考スコア（独自算出の注目度）: 1.4886567189108137
- License:
- Abstract: In this paper, we present the first known example of a locally checkable labeling problem (LCL) that admits asymptotic distributed quantum advantage in the LOCAL model of distributed computing: our problem can be solved in $O(\log n)$ communication rounds in the quantum-LOCAL model, but it requires $\Omega(\log n \cdot \log^{0.99} \log n)$ communication rounds in the classical randomized-LOCAL model. We also show that distributed quantum advantage cannot be arbitrarily large: if an LCL problem can be solved in $T(n)$ rounds in the quantum-LOCAL model, it can also be solved in $\tilde O(\sqrt{n T(n)})$ rounds in the classical randomized-LOCAL model. In particular, a problem that is strictly global classically is also almost-global in quantum-LOCAL. Our second result also holds for $T(n)$-dependent probability distributions. As a corollary, if there exists a finitely dependent distribution over valid labelings of some LCL problem $\Pi$, then the same problem $\Pi$ can also be solved in $\tilde O(\sqrt{n})$ rounds in the classical randomized-LOCAL and deterministic-LOCAL models. That is, finitely dependent distributions cannot exist for global LCL problems.
- Abstract（参考訳）: 本稿では、分散コンピューティングのLOCALモデルにおける漸近的分散量子優位性を認める局所チェック可能なラベリング問題(LCL)の最初の例として、量子LOCALモデルでは$O(\log n)$通信ラウンドで解決できるが、古典的ランダム化-LOCALモデルでは$Omega(\log n \cdot \log^{0.99} \log n)$通信ラウンドが必要である。
量子-LOCALモデルでは、LCL問題を$T(n)$ラウンドで解くことができれば、古典的ランダム化-LOCALモデルでは$\tilde O(\sqrt{n T(n)})$ラウンドでも解ける。
特に、厳密に大域的に古典的である問題は、量子LOCALにおいてもほぼグロバルである。
第二の結果も$T(n)$依存確率分布である。
系として、ある LCL 問題 $\Pi$ の有効ラベル付けに有限依存分布が存在する場合、同じ問題 $\Pi$ は古典的ランダム化-LOCAL および決定論的-LOCAL モデルにおいて $\tilde O(\sqrt{n})$ ラウンドでも解決できる。
すなわち、大域的なLCL問題に対して有限依存分布は存在しない。
関連論文リスト
- Distributed Quantum Advantage for Local Problems [3.1024627815534593]
分散コンピューティングの古典的ランダム化LOCALモデルと,その量子的モデルとの超コンスタントな分離を示す。
本稿では,局所的制約のみを用いて定義した反復GHZ問題を提案する。
論文 参考訳（メタデータ） (2024-11-05T16:38:49Z) - Predicting quantum channels over general product distributions [19.09244195034539]
我々は、分布$D$からサンプリングされたほとんどの$rho$に対して、写像の始点* rho mapto mathrmTr(O E[rho]) endequation* を小さな誤差の範囲内で学習する。
自明な指数的下界が存在する場合の「古典的」ではないことを前提として、基本的に任意の積分布に対して正確な予測を行う新しいアプローチを提案する。
論文 参考訳（メタデータ） (2024-09-05T16:39:13Z) - Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
本稿では,AQC(Adiabatic Quantum Computation)と同様,量子計算のためのフレームワークを提案する。
ポアソン過程によって決定された間隔でランダムデファーズ演算を行うことにより、特定の固有値に関連する固有空間を追跡することができる。
有限性に対する単純な微分方程式を導出し、アルゴリズムのクラスの時間複雑性を境界とする一般定理を導出する。
論文 参考訳（メタデータ） (2024-06-06T11:33:29Z) - Online Locality Meets Distributed Quantum Computing [2.3821076274208552]
分散コンピューティングの古典的なLOCALモデルの拡張について、3行の研究が最近行われた。
局所チェック可能なラベリング問題(LCL)に対するこれらのモデルの機能と制限に関する新しい結果が証明された。
我々の研究は、分散環境での利点の限界を示唆しており、より厳密な境界を示すための新たな障壁も示しています。
論文 参考訳（メタデータ） (2024-03-04T10:03:54Z) - No distributed quantum advantage for approximate graph coloring [2.8518543181146785]
分散アルゴリズムを用いた$c$-coloring $chi$-chromatic graphの難易度を,ほぼ完全に評価する。
これらの問題は、分散量子の優位性を認めないことを示している。
論文 参考訳（メタデータ） (2023-07-18T17:17:27Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。