論文の概要: Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication

• arxiv url: http://arxiv.org/abs/2506.16804v1
• Date: Fri, 20 Jun 2025 07:40:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-23 19:00:05.371805
• Title: Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication
• Title（参考訳）: 前頭同時通信における量子対古典的分離
• Authors: Guangxu Yang, Jiapeng Zhang,
• Abstract要約: 本稿では、量子と有界エラーのランダム化通信の複雑性を、Number-on-Foreheadモデルの変種で初めて指数関数的に分離する。 具体的には、Gadgeted Hidden Matching Problemを導入し、O(log n)$の同時量子通信でのみ解けることを示す。
• 参考スコア（独自算出の注目度）: 4.871651154984323
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum versus classical separation plays a central role in understanding the advantages of quantum computation. In this paper, we present the first exponential separation between quantum and bounded-error randomized communication complexity in a variant of the Number-on-Forehead (NOF) model. Namely, the three-player Simultaneous Number-on-Forehead model. Specifically, we introduce the Gadgeted Hidden Matching Problem and show that it can be solved using only $O(\log n)$ simultaneous quantum communication. In contrast, any simultaneous randomized protocol requires $\Omega(n^{1/16})$ communication. On the technical side, a key obstacle in separating quantum and classical communication in NOF models is that all known randomized NOF lower bound tools, such as the discrepancy method, typically apply to both randomized and quantum protocols. In this regard, our technique provides a new method for proving randomized lower bounds in the NOF setting and may be of independent interest beyond the separation result.
• Abstract（参考訳）: 量子対古典分離は、量子計算の利点を理解する上で中心的な役割を果たす。 本稿では,Number-on-Forehead(NOF)モデルの変種において,量子と有界エラーのランダム化通信の複雑性を指数関数的に分離した最初の例を示す。 つまり、3人のプレイヤーの同時数対フォアヘッドモデルである。 具体的には、Gadgeted Hidden Matching Problemを導入し、O(\log n)$の同時量子通信でのみ解けることを示す。 対照的に、任意の同時ランダム化プロトコルは$\Omega(n^{1/16})$通信を必要とする。 技術的側面において、NOFモデルにおける量子通信と古典通信を分離する上で重要な障害は、一般にランダム化されたNOFの下界ツール、例えば離散法(英語版)がランダム化されたプロトコルと量子プロトコルの両方に適用されることである。 そこで本手法は,NOF設定におけるランダム化下界の証明方法を提供し,分離結果を超える独立性を持つ可能性がある。

関連論文リスト

• Communication Complexity of Common Randomness Generation with Isotropic States [5.312109949216557]
  本稿は、一方通行古典通信と一方通行量子通信の2つの通信モデルについて考察する。 古典的通信の場合、量子等方性状態はノイズのある古典的相関に勝らないことを示す。 量子通信の場合、量子等方性状態の超高密度符号化を用いることで、共通乱数率を増大させることができることを示す。
  論文  参考訳（メタデータ） (2023-11-08T14:48:15Z)
• One Clean Qubit Suffices for Quantum Communication Advantage [3.729242965449096]
  1つの量子ビットが純粋な状態にあり、他の全ての量子ビットが最大混合される量子通信の1つのクリーン量子ビットモデルについて検討する。 我々の証明は、Ellis, Kindler, Lifshitz, Minzerが最近導入した超収縮性不等式に基づいている。
  論文  参考訳（メタデータ） (2023-10-03T19:58:08Z)
• Classical Verification of Quantum Learning [42.362388367152256]
  量子学習の古典的検証のための枠組みを開発する。 そこで我々は,新しい量子データアクセスモデルを提案し,これを"mixture-of-superpositions"量子例と呼ぶ。 この結果から,学習課題における量子データの潜在能力は無限ではないものの,古典的エージェントが活用できることが示唆された。
  論文  参考訳（メタデータ） (2023-06-08T00:31:27Z)
• Decoupling by local random unitaries without simultaneous smoothing, and applications to multi-user quantum information tasks [0.0]
  単純なテレスコープ和のトリックは、三角形の不等式とランダムチャネルの予測収縮係数のテンソル化特性とともに、局所的な動作によって複数のユーザに対して一般的な同時疎結合を実現することができることを示す。 我々は、スムーズなミンエントロピーの1ショット設定やR'enyiエントロピーの有限ブロック長設定のいずれにおいても、理想デカップリングから期待される偏差の有界を得る。 これは量子シャノン理論におけるいくつかのタスクに対して、1ショット、有限ブロック長、同時達成性をもたらす。
  論文  参考訳（メタデータ） (2023-04-24T14:17:32Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  証明者と検証者の間の「相互作用」は、検証可能性と実装のギャップを埋めることができる。 イオントラップ量子コンピュータを用いた対話型量子アドバンストプロトコルの最初の実装を実演する。
  論文  参考訳（メタデータ） (2021-12-09T19:00:00Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。 悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。 我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
  論文  参考訳（メタデータ） (2020-10-15T17:55:31Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)

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

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