論文の概要: An exponential separation between entanglement-assisted and unassisted one-way quantum communication

• arxiv url: http://arxiv.org/abs/2610.02099v1
• Date: Thu, 01 Oct 2026 17:25:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.331266
• Title: An exponential separation between entanglement-assisted and unassisted one-way quantum communication
• Title（参考訳）: 絡み合い支援と非支援片道量子通信の指数的分離
• Abstract要約: 量子通信複雑性における長年の疑問は、絡み合いの存在下で少量の通信で、あるタスクが達成できるかどうかである。 先行絡み合いが与えられた一方向古典通信の$O(log n)$ bitsで計算できる総ブール関数の族を示す。 我々の機能は、Aaronson、Le Gall、Russell、Taniによる通信環境で最初に研究されたサブグループメンバシップ問題の特別なケースである。
• 参考スコア（独自算出の注目度）: 2.4032714597247256
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence of entanglement. Separations of this nature were previously known for relational problems and, in the simultaneous message passing model, for partial functions. But it has remained unresolved whether any such separation exists for a total Boolean function. We resolve this question with an exponential separation in the one-way setting: we exhibit a family of total Boolean functions $f_n\colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ that can be computed with $O(\log n)$ bits of one-way classical communication given prior entanglement, but that require $Ω(n^{1/3})$ qubits of one-way quantum communication without entanglement. Our function is a special case of the subgroup membership problem, first studied in the communication setting by Aaronson, Le Gall, Russell, and Tani.
• Abstract（参考訳）: 量子通信複雑性における長年の疑問は、絡み合いの存在下で少量の通信で達成できるタスクがあるが、絡み合いがない場合にはより多くの量子通信を必要とするかどうかである。 この性質の分離は、以前は関係問題や部分関数の同時メッセージパッシングモデルで知られていた。 しかし、そのような分離が全体ブール函数に対して存在するかどうかについては未解決のままである。 我々はこの問題を、一方向の設定において指数関数的に分離することで解決する: 全体ブール関数の族 $f_n\colon \{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ は、先行エンタングルメントを与えられた一方向古典的通信の$O(\log n)$ ビットで計算できるが、エンタングルメントのない一方向量子通信の$Ω(n^{1/3})$ qubits を必要とする。 我々の関数は、Aaronson、Le Gall、Russell、Taniによる通信環境で最初に研究された部分群メンバシップ問題の特別な場合である。

関連論文リスト

• Improved Separations between Quantum and Classical Communication Complexity of Total Functions [1.3706331473063882]
  我々は、全関数の量子的およびランダム化された通信複雑性の指数的分離のためのガヴィンスキーの枠組みを洗練する。 固定された$0varepsilon1$に対して、より量子的なメッセージは$(n1-varepsilon)$に対して$(n1-varepsilon)$である。
  論文  参考訳（メタデータ） (2026-09-15T06:56:34Z)
• Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement [0.3004066195320147]
  入力サイズが$n$である関係問題を、絡み合い支援量子通信モデルのための通信無しで解くことができる。 これは、共有絡み合いと非共有絡み合いによる量子通信複雑性の最大分離である。
  論文  参考訳（メタデータ） (2025-05-22T09:41:04Z)
• Unbounded Quantum Advantage in Communication with Minimal Input Scaling [0.0]
  一般の硬貨を使わずに関係の再構築を行う場合, 量子的に非有界な利点を示す。 また、このタスクの半デバイス非依存なディメンションの目撃や、ミューチュアル・アンバイアスド・ベースの検出への応用についても強調する。
  論文  参考訳（メタデータ） (2023-05-17T16:58:05Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  証明者と検証者の間の「相互作用」は、検証可能性と実装のギャップを埋めることができる。 イオントラップ量子コンピュータを用いた対話型量子アドバンストプロトコルの最初の実装を実演する。
  論文  参考訳（メタデータ） (2021-12-09T19:00:00Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。 量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。 我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
  論文  参考訳（メタデータ） (2021-06-11T18:00:09Z)
• 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)
• Communication Cost of Quantum Processes [49.281159740373326]
  分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。 重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。 クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
  論文  参考訳（メタデータ） (2020-02-17T08:51:42Z)

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

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