論文の概要: Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication

• arxiv url: http://arxiv.org/abs/2603.22795v1
• Date: Tue, 24 Mar 2026 04:38:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-25 19:53:37.310231
• Title: Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
• Title（参考訳）: 前頭通信における量子と古典的ワンウェイ数の指数分離
• Authors: Guangxu Yang, Jiapeng Zhang,
• Abstract要約: NoF(Numbers-on-Forehead)通信モデルは、通信複雑性の中心的なモデルである。 本論文では,一方通行NOFモデルにおいて,量子とランダム化通信の複雑性を指数関数的に分離する最初の方法を確立する。
• 参考スコア（独自算出の注目度）: 14.595648710226735
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Numbers-on-Forehead (NOF) communication model is a central model in communication complexity. As a restricted variant, one-way NOF model is of particular interest. Establishing strong one-way NOF lower bounds would imply circuit lower bounds, resolve well-known problems in additive combinatorics, and yield wide-ranging applications in areas such as cryptography and distributed computing. However, proving strong lower bounds in one-way NOF communication remains highly challenging; many fundamental questions in one-way NOF communication remain wide open. One of the fundamental questions, proposed by Gavinsky and Pudlák (CCC 2008), is to establish an explicit exponential separation between quantum and classical one-way NOF communication. In this paper, we resolve this open problem by establishing the first exponential separation between quantum and randomized communication complexity in one-way NOF model. Specifically, we define a lifted variant of the Hidden Matching problem of Bar-Yossef, Jayram, and Kerenidis (STOC 2004) and show that it admits an ($O(\log n)$)-cost quantum protocol in the one-way NOF setting. By contrast, we prove that any $k$-party one-way randomized protocol for this problem requires communication $Ω(\frac{n^{1/3}}{2^{k/3}})$. Notably, our separation applies even to a generalization of $k$-player one-way communication, where the first player speaks once, and all other $k-1$ players can communicate freely.
• Abstract（参考訳）: NoF(Numbers-on-Forehead)通信モデルは、通信複雑性の中心的なモデルである。 制限された変種として、一方通行のNOFモデルは特に興味深い。 強い一方通行NOFの下界を確立することは、下界を回路化し、加法コンビネータにおけるよく知られた問題を解決し、暗号や分散コンピューティングなどの分野において幅広い応用をもたらす。 しかし、一方のNOF通信における強い下位境界の証明は依然として非常に困難であり、一方のNOF通信における多くの基本的な疑問は依然として広く開かれている。 Gavinsky と Pudlák (CCC 2008) によって提案された基本的な問題の1つは、量子と古典的な一方通行のNOF通信を明示的に分離することである。 本稿では、一方通行NOFモデルにおいて、量子とランダム化通信の複雑性を初めて指数関数的に分離することで、この問題を解決する。 具体的には、Bar-Yossef, Jayram, and Kerenidis (STOC 2004) のHidden Matching問題の持ち上げ変種を定義し、一方方向NOF設定において$O(\log n)$)コストの量子プロトコルを許容していることを示す。 対照的に、この問題に対する任意の$k$の一方通行ランダム化プロトコルは、通信$Ω(\frac{n^{1/3}}{2^{k/3}})$が必要であることを証明している。 特に、我々の分離は、最初のプレイヤーが一度話し、他のすべての$k-1$プレーヤーが自由にコミュニケーションできる、$k$-player片道通信の一般化にも適用される。

関連論文リスト

• Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
  本稿では,マルチプレイヤー通信ゲームに基づく新しい証明手法を提案する。 本稿では,このコミュニケーションゲームに勝つためには,過剰なユーザ数に比例した情報伝達が必要であることを示す。 このコミュニケーション理論の手法は幅広い問題のクラスに一般化し、プライベートな中央値、量子化値、最大選択値の下位境界を導出することを示す。
  論文  参考訳（メタデータ） (2026-02-12T17:49:07Z)
• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  量子多体系のシミュレーションを劇的に高速化するマルコフ連鎖モンテカルロ(MCMC)アルゴリズムを導入する。 我々は,量子物理学のベンチマーク問題に対するアルゴリズムの有効性を検証し,既知の理論結果を正確に再現する。 我々の研究は、大規模確率的推論のための強力なツールを提供し、物理学に着想を得た生成モデルのための道を開く。
  論文  参考訳（メタデータ） (2025-10-13T07:57:21Z)
• Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication [4.871651154984323]
  本稿では、量子と有界エラーのランダム化通信の複雑性を、Number-on-Foreheadモデルの変種で初めて指数関数的に分離する。 具体的には、Gadgeted Hidden Matching Problemを導入し、O(log n)$の同時量子通信でのみ解けることを示す。
  論文  参考訳（メタデータ） (2025-06-20T07:40:43Z)
• One Clean Qubit Suffices for Quantum Communication Advantage [3.729242965449096]
  1つの量子ビットが純粋な状態にあり、他の全ての量子ビットが最大混合される量子通信の1つのクリーン量子ビットモデルについて検討する。 我々の証明は、Ellis, Kindler, Lifshitz, Minzerが最近導入した超収縮性不等式に基づいている。
  論文  参考訳（メタデータ） (2023-10-03T19:58:08Z)
• Sparse Decentralized Federated Learning [35.32297764027417]
  分散フェデレートラーニング(DFL)は、中央サーバーなしで協調的なモデルトレーニングを可能にするが、効率、安定性、信頼性の課題に直面している。 Sparse DFL (SDFL) に繋がる共有モデルに空間制約を導入し,新しいアルゴリズムCEPSを提案する。 数値実験により,高い信頼性を維持しつつ,コミュニケーションと効率を向上させるための提案アルゴリズムの有効性が検証された。
  論文  参考訳（メタデータ） (2023-08-31T12:22:40Z)
• Unbounded Quantum Advantage in Communication with Minimal Input Scaling [0.0]
  一般の硬貨を使わずに関係の再構築を行う場合, 量子的に非有界な利点を示す。 また、このタスクの半デバイス非依存なディメンションの目撃や、ミューチュアル・アンバイアスド・ベースの検出への応用についても強調する。
  論文  参考訳（メタデータ） (2023-05-17T16:58:05Z)
• FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learning [75.46959684676371]
  我々は、クライアントからPSにヘッセン情報を送信する必要がないFedNewという新しいフレームワークを紹介した。 FedNewは勾配情報を隠蔽し、既存の最先端技術と比べてプライバシー保護のアプローチをもたらす。
  論文  参考訳（メタデータ） (2022-06-17T15:21:39Z)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  ノイズチャネルの多くの用途でメッセージを確実に送信するために、回路をエンコードしてデコードする。 すべての量子チャネル$T$とすべての$eps>0$に対して、以下に示すゲートエラー確率のしきい値$p(epsilon,T)$が存在し、$C-epsilon$より大きいレートはフォールトトレラント的に達成可能である。 我々の結果は、遠方の量子コンピュータが高レベルのノイズの下で通信する必要があるような、大きな距離での通信やオンチップでの通信に関係している。
  論文  参考訳（メタデータ） (2020-09-15T15:10:50Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography [0.0]
  まず、実験データに基づいて、後部のエントロピーが定数列によって最小化されることを予想する。 次に,DC-QKEを提案するために,隠蔽通信とデニビリティの接続を確立する。 完全ホモモルフィック暗号をベースとした,効率的な耐保磁・量子セキュリティ投票方式を提案する。
  論文  参考訳（メタデータ） (2020-03-25T22:20:47Z)

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

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