論文の概要: Exponential Quantum Advantage for Message Complexity in Distributed Algorithms

• arxiv url: http://arxiv.org/abs/2510.01657v1
• Date: Thu, 02 Oct 2025 04:28:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 14:32:17.251493
• Title: Exponential Quantum Advantage for Message Complexity in Distributed Algorithms
• Title（参考訳）: 分散アルゴリズムにおけるメッセージ複雑性の指数量子アドバンテージ
• Authors: François Le Gall, Maël Luce, Joseph Marchand, Mathieu Roget,
• Abstract要約: ネットワークの2つの特定ノード間で情報をルーティングする、基本的なタスクに対する指数的量子優位性を示す。 我々の量子アルゴリズムは、Li、Li、Luoによる溶接木上の量子ウォークの最近の「簡潔な」実装に基づいている。
• 参考スコア（独自算出の注目度）: 0.8808021343665321
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate how much quantum distributed algorithms can outperform classical distributed algorithms with respect to the message complexity (the overall amount of communication used by the algorithm). Recently, Dufoulon, Magniez and Pandurangan (PODC 2025) have shown a polynomial quantum advantage for several tasks such as leader election and agreement. In this paper, we show an exponential quantum advantage for a fundamental task: routing information between two specified nodes of a network. We prove that for the family of ``welded trees" introduced in the seminal work by Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003), there exists a quantum distributed algorithm that transfers messages from the entrance of the graph to the exit with message complexity exponentially smaller than any classical algorithm. Our quantum algorithm is based on the recent "succinct" implementation of quantum walks over the welded trees by Li, Li and Luo (SODA 2024). Our classical lower bound is obtained by ``lifting'' the lower bound from Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003) from query complexity to message complexity.
• Abstract（参考訳）: 本稿では,従来の分散アルゴリズムがメッセージの複雑さ(アルゴリズムが使用する通信の総量)に対して,どの程度の量子分散アルゴリズムが優れているかを検討する。 最近、Dufoulon, Magniez and Pandurangan (PODC 2025) は、リーダー選挙や合意のようないくつかのタスクにおいて多項式量子の優位性を示している。 本稿では,ネットワークの2つの特定ノード間で情報をルーティングする,基本課題に対する指数的量子優位性を示す。 我々は、Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003) のセミナル研究で導入された 'welded tree' の族について、グラフの入り口から出口へメッセージを転送する量子分散アルゴリズムが存在することを証明した。この量子アルゴリズムは、Li, Li, Luo (SODA 2024) による溶接木上の量子ウォークの「簡潔な」実装に基づいている。 私たちの古典的な下限は、クエリの複雑さからメッセージの複雑さまで、Childs, Cleve, Deotto, Farhi, Gutmann, Spielman (STOC 2003) から下限の‘lifting’によって得られます。

関連論文リスト

• Quantum algorithms through graph composition [0.40792653193642503]
  本稿では、量子アルゴリズムを生成するための st-connectivity framework の一般化であるグラフ合成フレームワークを紹介する。 st接続性フレームワークが学習グラフフレームワーク,重み付き決定木フレームワーク,および後者のゼロエラーバージョンをどう仮定するかを示す。 また、空間効率の高い有向st接続問題、パターンマッチング問題、固定探索問題に対する既存の量子アルゴリズムを単純化する。
  論文  参考訳（メタデータ） (2025-04-02T20:20:51Z)
• Quantum Communication Advantage for Leader Election and Agreement [0.6937243101289334]
  本稿では,Grover検索や量子カウント,量子ウォークなどの量子アルゴリズム技術が,分散アルゴリズムのメッセージ効率を著しく向上させることを示す。 特に、直径2ネットワークのためのリーダー選挙プロトコルでは、改良されたメッセージ複雑性を実現するために量子ウォークを用いています。
  論文  参考訳（メタデータ） (2025-02-11T09:52:20Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。 我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。 最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
  論文  参考訳（メタデータ） (2023-05-17T18:00:06Z)
• Concise and Efficient Quantum Algorithms for Distribution Closeness Testing [0.2741266294612775]
  本研究では, 量子計算が分布特性の試験の基礎的問題に与える影響について検討する。 この問題に対して現在最高の量子アルゴリズムを$l1$-distanceと$l2$-distanceのメトリクスで提案する。
  論文  参考訳（メタデータ） (2023-02-13T04:03:59Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)

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

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