論文の概要: The Quantum Message Complexity of Distributed Wake-Up with Advice

• arxiv url: http://arxiv.org/abs/2602.05801v1
• Date: Thu, 05 Feb 2026 15:55:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-06 18:49:09.020627
• Title: The Quantum Message Complexity of Distributed Wake-Up with Advice
• Title（参考訳）: 分散ウェイクアップとアドバイスの量子メッセージ複雑性
• Authors: Peter Robinson, Ming Ming Tan,
• Abstract要約: 本稿では、量子ルーティングモデルにおいて、ウェイクアップのためのメッセージの複雑さに関する第1および第2の上限を示す。 我々は、ウェイクアップがアドバイスなしで$(n3/2 )$の量子メッセージ複雑性を持つことを示した。
• 参考スコア（独自算出の注目度）: 0.2578242050187029
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the distributed wake-up problem with advice, where nodes are equipped with initial knowledge about the network at large. After the adversary awakens a subset of nodes, an oracle computes a bit string (``the advice'') for each node, and the goal is to wake up all sleeping nodes efficiently. We present the first upper and lower bounds on the message complexity for wake-up in the quantum routing model, introduced by Dufoulon, Magniez, and Pandurangan (PODC 2025). In more detail, we give a distributed advising scheme that, given $α$ bits of advice per node, wakes up all nodes with a message complexity of $O( \sqrt{\frac{n^3}{2^{\max\{\lfloor (α-1)/2 \rfloor},0\}}}\cdot\log n )$ with high probability. Our result breaks the $Ω( \frac{n^2}{2^α} )$ barrier known for the classical port numbering model in sufficiently dense graphs. To complement our algorithm, we give a lower bound on the message complexity for distributed quantum algorithms: By leveraging a lower bound result for the single-bit descriptor problem in the query complexity model, we show that wake-up has a quantum message complexity of $Ω( n^{3/2} )$ without advice, which holds independently of how much time we allow. In the setting where an adversary decides which nodes start the algorithm, most graph problems of interest implicitly require solving wake-up, and thus the same lower bound also holds for other fundamental problems such as single-source broadcast and spanning tree construction.
• Abstract（参考訳）: 本稿では,ノードにネットワークに関する初期知識が備わっている分散起動問題について,アドバイスとともに考察する。 敵がノードのサブセットを起動した後、オラクルは各ノードに対してビット文字列(`the advice'')を計算し、その目標はすべての睡眠ノードを効率的に起こすことである。 我々は、Dufoulon, Magniez, Pandurangan (PODC 2025)によって導入された量子ルーティングモデルにおいて、ウェイクアップのためのメッセージの複雑さに関する最初の上と下の境界を示す。 より詳しくは、ノード毎に$α$のアドバイスを与える分散アドバイススキームを、高い確率で$O( \sqrt {\frac{n^3}{2^{\max\{\lfloor (α-1)/2 \rfloor},0\}}}\cdot\log n )$のメッセージ複雑性ですべてのノードを起動する。 我々の結果は、十分に密度の高いグラフの古典的なポート番号モデルで知られている$Ω( \frac{n^2}{2^α} )$バリアを破る。 クエリ複雑性モデルにおける単一ビットディスクリプタ問題に対する低いバウンダリ結果を利用することで、ウォークアップがアドバイスなしで$Ω(n^{3/2})$の量子メッセージ複雑性を持つことを示す。 敵がどのノードをアルゴリズムで開始するかを決定する場合、ほとんどのグラフ問題は暗黙的にウェイクアップを解く必要があり、したがって同じ下位境界は、単一ソースブロードキャストやスパンディングツリー構築のような他の基本的な問題にも当てはまる。

関連論文リスト

• Asymptotic robustness of entanglement in noisy quantum networks and graph connectivity [46.44827993583994]
  リンクが騒々しい場合には,ネットワークのグローバルな絡み合い特性に関して,大きく異なる2つの挙動が生じることを示す。 特定の構成では、ノイズレベルが一定の閾値以下であれば、ネットワークは真のマルチパーティ・エンタングルメント(GME)を表示するが、他のGMEは、固定された非ゼロレベルのノイズに対してシステムサイズが十分大きい場合、洗い流される。
  論文  参考訳（メタデータ） (2024-11-19T15:01:50Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。 このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。 次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。 有名な座標降下法に基づく新しいN-Cut解法を提案する。
  論文  参考訳（メタデータ） (2023-11-26T07:11:58Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• 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)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。 次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。 頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
  論文  参考訳（メタデータ） (2021-07-22T14:25:16Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)

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

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