論文の概要: No Distributed Quantum Advantage for 3-Coloring Rooted Trees and 2-Coloring Even Cycles
- arxiv url: http://arxiv.org/abs/2607.04852v1
- Date: Mon, 06 Jul 2026 09:24:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-08 14:37:43.297754
- Title: No Distributed Quantum Advantage for 3-Coloring Rooted Trees and 2-Coloring Even Cycles
- Title（参考訳）: 3色のルート木と2色のサイクルに対する分散量子アドバンテージ
- Abstract要約: 最近、Coiteux-Royetal. (STOC 2024) は、量子資源が3色交配木に役立たないことを示した。
量子アルゴリズムは、古典的決定論的アルゴリズムよりも1ラウンドでも2色の偶数サイクルを保存できないことを示す。
- 参考スコア（独自算出の注目度）: 0.7009487789080343
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Significant effort has been devoted over the past decade to understanding whether quantum resources can provide advantages in distributed computing, and in particular whether they can help overcome locality constraints in networks, typically in Linial's LOCAL model. Recently, Coiteux-Roy~et~al.~(STOC 2024) showed that quantum resources do not help for 3-coloring \textit{unrooted} trees: in particular, their lower bound holds in the stronger \textit{non-signaling} model, which formalizes the principle of physical causality in distributed computing. The case of \textit{rooted} trees, however, was left open by their work. For rooted trees, the deterministic Cole-Vishkin algorithm 3-colors $n$-node trees in $O(\log^\star n)$ rounds, matching Linial's classical $Ω(\log^\star n)$ lower bound (FOCS 1987). In this paper, we show that any algorithm in quantum-LOCAL (without pre-shared entanglement) that properly 3-colors $n$-node rooted trees with probability at least ${1-O(1/\log n)}$ must perform $Ω(\log^\star n)$ rounds. That is, quantum resources provide no advantage for 3-coloring rooted trees. To get this result, we show a lower bound of $Ω(\log^\star Δ)$ for 3-coloring any $Δ$-ary tree with success probability at least $1-1/Δ$. The proof uses a \textit{color lifting} technique that bears similarity to Linial's original argument. We also show, as a separate result, that 2-coloring even-length $n$-node cycles with probability $1-O(1/n)$ requires $n/2-1$ rounds in the quantum-LOCAL model, even with pre-shared entangled states. This improves the previously known $\lceil (n-2)/4 \rceil$ lower bound of Gavoille, Kosowski, and Markiewicz (DISC 2009) by a factor of two, and shows that quantum algorithms cannot save even a single round over classical deterministic algorithms for 2-coloring even-length cycles.
- Abstract（参考訳）: 過去10年間、量子リソースが分散コンピューティングにメリットをもたらすかどうか、特にLinialのLOCALモデルにおいて、ネットワーク内の局所性制約を克服するのに役立つかどうかを理解するために、重要な努力が続けられてきた。
最近、Coiteux-Roy〜et〜al。
特に、その下限は分散コンピューティングにおける物理的因果性の原理を定式化するより強い \textit{non-signaling} モデルである。
しかし、 \textit{rooted} ツリーのケースは、その作業によって開放された。
根木に対して、決定論的Cole-Vishkinアルゴリズムは、$O(\log^\star n)$ラウンドで$n$-ノード木を3色化し、Linialの古典的な$Ω(\log^\star n)$ lower bound (FOCS 1987)と一致する。
本稿では,少なくとも${1-O(1/\log n)}$が$Ω(\log^\star n)$の確率で,n$ノードルート木を適切に3色化する量子LOCALの任意のアルゴリズムが,$Ω(\log^\star n)$のラウンドを実行しなければならないことを示す。
つまり、量子資源は3色の根木に利点を与えない。
この結果を得るために、少なくとも1-1/Δ$の成功確率を持つ任意の$Δ$-ary treeを3色化するための$Ω(\log^\star Δ)$の低い境界を示す。
この証明は、Linialの元々の議論と類似性を持つ \textit{color lifting} 技術を用いている。
また、別の結果として、1-O(1/n) の確率を持つ2色の偶数長 $n$-node サイクルは、事前共有の絡み合った状態であっても量子-LOCALモデルにおいて$n/2-1$ ラウンドを必要とすることも示している。
これは以前に知られていた$\lceil (n-2)/4 \rceil$ lower bound of Gavoille, Kosowski, and Markiewicz (DISC 2009) を2倍に改善し、量子アルゴリズムが古典的決定論的アルゴリズムよりも1ラウンドも保存できないことを示す。
関連論文リスト
- Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - 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) - Extending the Design Space of Graph Neural Networks by Rethinking
Folklore Weisfeiler-Lehman [66.23316415757456]
近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。
しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。
我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。
N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
論文 参考訳（メタデータ） (2023-06-05T21:35:32Z) - 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) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL
model [0.0]
本研究では,一対一の通信のみを行うリングをカラー化するための分散アルゴリズムについて検討する。
適切な$$3のカラー化を出力する量子シングルラウンドワンウェイ分散アルゴリズムの確率は、指数関数的に$n$である。
論文 参考訳（メタデータ） (2022-12-06T05:39:50Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。
任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
論文 参考訳（メタデータ） (2020-08-20T01:04:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。