論文の概要: Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
- arxiv url: http://arxiv.org/abs/2602.15529v1
- Date: Tue, 17 Feb 2026 12:10:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-18 16:03:18.056115
- Title: Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
- Title（参考訳）: 量子ルーティングモデルにおける分散アルゴリズムのタイト通信境界
- Authors: Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan,
- Abstract要約: 本稿では,分散コンピューティングの基本問題に対する新しい分散量子アルゴリズムを提案する。
これらの問題には、任意のネットワークでリーダー選挙、放送、最小スパンニングツリー(MST)、ブレッドスファースト検索(BFS)ツリーが含まれる。
我々のアルゴリズムのメッセージ複雑性は、リーダー選挙、放送、MSTの$tildeO(n)$、BFSの$tildeO(sqrtmn)$です。
- 参考スコア（独自算出の注目度）: 0.5074812070492739
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks. These algorithms are (essentially) optimal with respect to their communication (message) complexity in the {\em quantum routing model} introduced in [PODC 2025]. The message complexity of our algorithms is $\tilde{O}(n)$ for leader election, broadcast, and MST, and $\tilde{O}(\sqrt{mn})$ for BFS ($n$ and $m$ are the number of nodes and edges of the network, respectively). These message bounds are nearly tight in the quantum routing model since we show almost matching corresponding quantum message lower bounds. Our results significantly improve on the prior work of [PODC 2025], who presented distributed quantum algorithms under the same model that had a message complexity of $\tilde{O}(\sqrt{mn})$ for leader election. Our algorithms demonstrate the significant communication advantage that quantum routing has over classical in distributed computing, since $Ω(m)$ is a well-established classical message lower bound for leader election, broadcast, MST, and BFS that applies even to randomized Monte-Carlo algorithms [JACM 2015]. Thus, our quantum algorithms can, in general, give a quadratic advantage in the communication cost for these fundamental problems. A main technical tool we use to design our distributed algorithms is quantum walks based on electric networks. We posit a framework for using quantum walks in the distributed setting to design communication-efficient distributed quantum algorithms. Our framework can be used as a black box to significantly reduce communication costs and may be of independent interest. Additionally, our lower-bound technique for establishing distributed quantum message lower bounds can also be applied to other problems.
- Abstract（参考訳）: 本稿では,分散コンピューティングの基本問題,すなわちリーダ選挙,放送,最小スパンニングツリー(MST),ブレッドスファーストサーチ(BFS)ツリーについて,任意のネットワークで新たな分散量子アルゴリズムを提案する。
これらのアルゴリズムは [PODC 2025] で導入された {\em 量子ルーティングモデルにおける通信(メッセージ)の複雑さに対して(本質的に)最適である。
我々のアルゴリズムのメッセージ複雑性は$\tilde{O}である
(n)$ for leader election, broadcast, and MST, and $\tilde{O}(\sqrt{mn})$ for BFS$n$と$m$はそれぞれネットワークのノード数とエッジ数である。
これらのメッセージ境界は、ほぼ一致する量子メッセージ下位境界を示すため、量子ルーティングモデルにおいてほぼ緊密である。
この結果, [PODC 2025] は, メッセージの複雑さが$\tilde{O}(\sqrt{mn})$の同じモデルで分散量子アルゴリズムを提示した。
我々のアルゴリズムは、$Ω以降の分散コンピューティングにおいて、量子ルーティングが古典的よりも優れていることを示す。
(m)$は、モンテカルロのランダム化アルゴリズム [JACM 2015] にも適用可能な、リーダー選挙、放送、MST、BFSのための、確立された古典的メッセージローバウンドである。
したがって、我々の量子アルゴリズムは、一般に、これらの基本的な問題に対する通信コストの二次的な優位性を与えることができる。
私たちが分散アルゴリズムの設計に使用している主要な技術ツールは、電気ネットワークに基づく量子ウォークです。
通信効率のよい分散量子アルゴリズムを設計するために、分散環境で量子ウォークを使用するためのフレームワークを提案する。
我々のフレームワークは通信コストを大幅に削減するためにブラックボックスとして使用することができ、独立した関心を持つ可能性がある。
また、分散量子メッセージの下位境界を確立するための低バウンド手法も他の問題に適用できる。
関連論文リスト
- Exponential Quantum Advantage for Message Complexity in Distributed Algorithms [0.8808021343665321]
ネットワークの2つの特定ノード間で情報をルーティングする、基本的なタスクに対する指数的量子優位性を示す。
我々の量子アルゴリズムは、Li、Li、Luoによる溶接木上の量子ウォークの最近の「簡潔な」実装に基づいている。
論文 参考訳（メタデータ） (2025-10-02T04:28:54Z) - Optimizing entanglement distribution via noisy quantum channels [44.99833362998488]
絡み合い分布は量子情報科学において重要な問題である。
ノイズの多い量子チャネルを経由した2つの遠方部間の量子絡み合いの分散戦略について検討する。
論文 参考訳（メタデータ） (2025-06-06T13:48:20Z) - 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 Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z) - Fault-tolerant Coding for Quantum Communication [71.206200318454]
ノイズチャネルの多くの用途でメッセージを確実に送信するために、回路をエンコードしてデコードする。
すべての量子チャネル$T$とすべての$eps>0$に対して、以下に示すゲートエラー確率のしきい値$p(epsilon,T)$が存在し、$C-epsilon$より大きいレートはフォールトトレラント的に達成可能である。
我々の結果は、遠方の量子コンピュータが高レベルのノイズの下で通信する必要があるような、大きな距離での通信やオンチップでの通信に関係している。
論文 参考訳（メタデータ） (2020-09-15T15:10:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。