論文の概要: Quantum Advantage for Distributed Symmetry Breaking

• arxiv url: http://arxiv.org/abs/2609.26788v1
• Date: Tue, 22 Sep 2026 17:58:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-24 01:05:39.780924
• Title: Quantum Advantage for Distributed Symmetry Breaking
• Title（参考訳）: 分散対称性破砕のための量子アドバンテージ
• Abstract要約: 分散量子アルゴリズムでは、O(1)$ラウンドで3ドルカラーのサイクルを、高い確率で行う。 古典的LOCALモデルにおける複雑性$O(log* n)$を持つ局所チェック可能なラベリング問題(LCL)は、量子モデルにおいて$O(1)$ラウンドで解決できる。
• 参考スコア（独自算出の注目度）: 0.4460583138505674
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a distributed quantum algorithm that $3$-colors cycles in $O(1)$ rounds, with high probability. It follows that all locally checkable labeling problems (LCLs) that have round complexity $O(\log^* n)$ in the classical LOCAL model can be solved in $O(1)$ rounds in the quantum-LOCAL model, with high probability; this includes problems such as maximal independent set and maximal matching in bounded-degree graphs. This presents the first natural examples of graph problems with an asymptotic distributed quantum advantage for the LOCAL model; all prior examples that separate LOCAL and quantum-LOCAL are artificial problems constructed merely for the sake of demonstrating quantum advantage.
• Abstract（参考訳）: 分散量子アルゴリズムでは、O(1)$ラウンドで3ドルカラーのサイクルを、高い確率で行う。 古典的なLOCALモデルにおいて、ラウンド複雑性が$O(\log^* n)$の局所チェック可能なラベリング問題(LCL)は、高い確率で量子LOCALモデルにおいて$O(1)$のラウンドで解ける。 これは、LOCALモデルに対して漸近的な分散量子優位性を持つグラフ問題の最初の自然な例を示し、LOCALと量子LOCALを分離する以前の例は、単に量子優位性を示すために作られた人工的な問題である。

関連論文リスト

• Distributed Quantum Advantage in Locally Checkable Labeling Problems [1.4886567189108137]
  LOCALモデル分散コンピューティングにおいて、分散量子優位性を認める局所チェック可能なラベル問題(LCL)の最初の例を示す。 我々の問題は量子モデルにおける$O(log n)$通信ラウンドで解決できるが、古典モデルでは$Omega(log n)$通信ラウンドを必要とする。
  論文  参考訳（メタデータ） (2025-04-07T15:42:05Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。 この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
  論文  参考訳（メタデータ） (2024-11-04T20:21:16Z)
• Online Locality Meets Distributed Quantum Computing [2.3821076274208552]
  分散コンピューティングの古典的なLOCALモデルの拡張について、3行の研究が最近行われた。 局所チェック可能なラベリング問題(LCL)に対するこれらのモデルの機能と制限に関する新しい結果が証明された。 我々の研究は、分散環境での利点の限界を示唆しており、より厳密な境界を示すための新たな障壁も示しています。
  論文  参考訳（メタデータ） (2024-03-04T10:03:54Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。 ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
  論文  参考訳（メタデータ） (2022-07-07T08:04:15Z)

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

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