論文の概要: Exponential Quantum Advantage in Numbers-on-Forehead Communication
- arxiv url: http://arxiv.org/abs/2609.40273v2
- Date: Mon, 05 Oct 2026 17:49:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-07 04:43:28.48579
- Title: Exponential Quantum Advantage in Numbers-on-Forehead Communication
- Title（参考訳）: 前頭通信における指数量子アドバンテージ
- Abstract要約: 一般対話型3要素数対フォアヘッド(NOF)モデルにおいて、決定問題に対する最初の指数的量子優位性を与える。
我々は、O(log n)$ NOF量子通信のみを必要とするが、$widetilde(n1/32)$ランダム化された通信を必要とするインターリーブド・ユニタリ・プロダクト問題である明示的な部分ブール関数を構築した。
- 参考スコア（独自算出の注目度）: 4.188553797799496
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Product problem, that requires only $O(\log n)$ NOF quantum communication but $\widetildeΩ(n^{1/32})$ randomized communication. This function builds on the two-party unitary product problem of Arunachalam, Girish, and Lifshitz (TQC 2024). The main technical obstacle is that discrepancy, the standard lower-bound method for NOF, also lower-bounds quantum communication. We instead develop a regularity-based argument for randomized NOF lower bounds, building on the approach of Kelley, Lovett, and Meka and adapting the regularity decomposition of Abboud, Fischer, Kelley, Lovett, and Meka (STOC 2024) to cylinder intersections. Combined with matrix-product estimates of Arunachalam, Girish, and Lifshitz, this yields our randomized lower bound.
- Abstract（参考訳）: 一般対話型3要素数対フォアヘッド(NOF)モデルにおいて、決定問題に対する最初の指数的量子優位性を与える。
以前の分離は、関係のための一方的な通信のような制限されたプロトコルに対してのみ保持される。
我々は、O(\log n)$ NOF量子通信のみを必要とするが、$\widetildeΩ(n^{1/32})$ランダム化された通信を必要とするインターリーブドユニタリ製品問題である明示的な部分ブール関数を構築した。
この関数は、Arunachalam, Girish, Lifshitz (TQC 2024) の2政党のユニタリ製品問題に基づいている。
主な技術的障害は、NOFの標準的な低バウンド法である差分法(英語版)もまた低バウンド量子通信である。
代わりに、ランダム化NOF下界に対する正則性に基づく議論を、ケリー、ラヴェット、メカのアプローチに基づいて構築し、アブード、フィッシャー、ケリー、ラヴェット、メカ(STOC 2024)の正則性分解をシリンダー交叉に適用する。
Arunachalam, Girish, Lifshitz の行列積推定と組み合わせることで、ランダム化された下界が得られる。
関連論文リスト
- Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and a Tight Univariate Rate [47.36630149538994]
高次元のオンライン予測では、最良の予測子はいくつかの機能にのみ依存する可能性があるため、後悔は周囲の次元ではなく、疎らさでスケールすべきである。
WarmuthとAmidはCOLT 2023で、これらの3つのルールのいずれかが競合するオンライン後悔の保証を認めているかどうかを尋ねた。
安価なニュアンスは、リフィットが真の予測座標を過度に重くする原因となる。
論文 参考訳（メタデータ） (2026-08-18T09:32:03Z) - Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。
任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
論文 参考訳（メタデータ） (2026-07-22T07:41:32Z) - Asymptotic Limits of Entanglement Distribution [43.748379918040854]
中間局と局所演算を用いた量子ネットワーク間の絡み合い分布の限界について検討する。
我々は厳密な二分法を確立する: 量子チャネルが補正可能な部分空間を持つ場合、任意の長距離での絡み合いの保存が可能となる。
物理資源要求の基本的な下限を導出し、補正可能な部分空間のないチャネルの場合、リンク毎の並列チャネルの数は、非ゼロ量の絡み合いを維持するために、少なくとも中間ステーションの数と対数的にスケールする必要があることを証明した。
論文 参考訳（メタデータ） (2026-05-22T09:56:38Z) - Tight Quantum Lower Bound for k-Distinctness [52.10197476419622]
我々は新しい量子クエリローバウンドフレームワークを導入する。
このフレームワークが入力文字列の等しい要素を見つけるという問題に対してどのように振る舞うかを示す。
特に、k-distinctness問題に対する最初の厳密な量子クエリローバウンドを証明することによって、そのパワーを実証する。
論文 参考訳（メタデータ） (2026-04-06T19:52:58Z) - Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication [14.595648710226735]
NoF(Numbers-on-Forehead)通信モデルは、通信複雑性の中心的なモデルである。
本論文では,一方通行NOFモデルにおいて,量子とランダム化通信の複雑性を指数関数的に分離する最初の方法を確立する。
論文 参考訳（メタデータ） (2026-03-24T04:38:22Z) - 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) - Rank lower bounds on non-local quantum computation [0.0]
非局所量子計算(NLQC)は、2つの量子システム間の相互作用を1ラウンドの通信と共有絡みによって置き換える。
NLQCの2つのクラス、$f$-routingと$f$-BB84を研究し、これは古典的な情報理論の暗号と量子位置の検証に関係している。
論文 参考訳（メタデータ） (2024-02-28T19:00:09Z) - Unbounded Quantum Advantage in Communication with Minimal Input Scaling [0.0]
一般の硬貨を使わずに関係の再構築を行う場合, 量子的に非有界な利点を示す。
また、このタスクの半デバイス非依存なディメンションの目撃や、ミューチュアル・アンバイアスド・ベースの検出への応用についても強調する。
論文 参考訳（メタデータ） (2023-05-17T16:58:05Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。