論文の概要: A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

• arxiv url: http://arxiv.org/abs/2511.17227v1
• Date: Fri, 21 Nov 2025 13:14:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-24 18:08:19.035983
• Title: A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
• Title（参考訳）: ハイブリッド古典量子通信複雑性のリフティング理論
• Authors: Xudong Wu, Guangxu Yang, Penghui Yao,
• Abstract要約: 古典通信と量子通信のトレードオフを$f:0,1ntopm1$と$G$の形式で構成する関数に対して検討する。 我々は、$c$古典ビットを通信し、$q$ qubitsが続く任意のハイブリッドプロトコルが$c+q2=bigを満たす必要があることを示す。 これは、ハイブリッド双方向通信複雑性における古典的通信と量子的通信の非自明なトレードオフとしては初めてである。
• 参考スコア（独自算出の注目度）: 10.42638550548464
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigates a model of hybrid classical-quantum communication complexity, in which two parties first exchange classical messages and subsequently communicate using quantum messages. We study the trade-off between the classical and quantum communication for composed functions of the form $f\circ G^n$, where $f:\{0,1\}^n\to\{\pm1\}$ and $G$ is an inner product function of $Θ(\log n)$ bits. To prove the trade-off, we establish a novel lifting theorem for hybrid communication complexity. This theorem unifies two previously separate lifting paradigms: the query-to-communication lifting framework for classical communication complexity and the approximate-degree-to-generalized-discrepancy lifting methods for quantum communication complexity. Our hybrid lifting theorem therefore offers a new framework for proving lower bounds in hybrid classical-quantum communication models. As a corollary, we show that any hybrid protocol communicating $c$ classical bits followed by $q$ qubits to compute $f\circ G^n$ must satisfy $c+q^2=Ω\big(\max\{\mathrm{deg}(f),\mathrm{bs}(f)\}\cdot\log n\big)$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{bs}(f)$ is the block sensitivity of $f$. For read-once formula $f$, this yields an almost tight trade-off: either they have to exchange $Θ\big(n\cdot\log n\big)$ classical bits or $\widetildeΘ\big(\sqrt n\cdot\log n\big)$ qubits, showing that classical pre-processing cannot significantly reduce the quantum communication required. To the best of our knowledge, this is the first non-trivial trade-off between classical and quantum communication in hybrid two-way communication complexity.
• Abstract（参考訳）: 本稿では,古典的メッセージの交換と,量子メッセージを用いた通信を行うハイブリッド古典量子通信複雑性のモデルについて検討する。 ここでは、$f:\{0,1\}^n\to\{\pm1\}$と$G$は、$(\log n)$ bitsの内積関数である。 トレードオフを証明するために,ハイブリッド通信の複雑性に関する新しいリフト定理を確立する。 この定理は、古典的な通信複雑性のためのクエリ・ツー・コミュニケーション・リフティング・フレームワークと、量子通信複雑性のための近似度・一般化・分散・リフティング・メソッドである。 したがって、我々のハイブリッドリフト定理は、ハイブリッド古典量子通信モデルにおける下界を証明するための新しい枠組みを提供する。 結論として、$c$ 古典的ビットを通信する任意のハイブリッドプロトコルに$f\circ G^n$を計算するための$q$ qubitsが続くことを示す: $c+q^2=Ω\big(\max\{\mathrm{deg}(f),\mathrm{bs}(f)\}\cdot\log n\big)$, ここで$\mathrm{deg}(f)$は$f$の次数であり、$\mathrm{bs}(f)$は$f$のブロック感度である。 リード・オンス式 $f$ の場合、これはほぼ厳密なトレードオフをもたらす: 古典的なビットを $ \big(n\cdot\log n\big)$ または $\widetilde\big(\sqrt n\cdot\log n\big)$ qubits と交換する必要があるか、古典的な前処理が要求される量子通信を著しく削減できないことを示す。 我々の知る限りでは、これはハイブリッド双方向通信における古典的通信と量子的通信の非自明なトレードオフとしては初めてである。

関連論文リスト

• Unbounded Quantum Advantage in Communication with Minimal Input Scaling [0.0]
  一般の硬貨を使わずに関係の再構築を行う場合, 量子的に非有界な利点を示す。 また、このタスクの半デバイス非依存なディメンションの目撃や、ミューチュアル・アンバイアスド・ベースの検出への応用についても強調する。
  論文  参考訳（メタデータ） (2023-05-17T16:58:05Z)
• Communication complexity of entanglement assisted multi-party computation [11.820804392113294]
  プレーヤが2ドル、ドットが2ドル、n$が1に適切な情報を伝達する必要がある場合、プレーヤが$n$のマルチパーティ計算問題を考える。 量子プロトコル(複雑性$(n-1)log n$ bits)と古典的プロトコル(複雑性$(n-1)2(log n2$)ビット)を示す。 これは、我々の量子プロトコルが古典的プロトコルよりも厳密に優れていることを示している。
  論文  参考訳（メタデータ） (2023-05-08T03:10:08Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Quantum teleportation in the commuting operator framework [63.69764116066747]
  我々は、相対可換群 $N'cap M$ に対して、Nsubseteq M$ と tracial von Neumann algebra の大きいクラスに対する非バイアス付きテレポーテーションスキームを提示する。 N$ に対する厳密なテレポーテーションスキームは、必ずしも正則ユニタリな Pimsner-Popa 基底 $M_n(mathbbC)$ over$N'$ から生じる。
  論文  参考訳（メタデータ） (2022-08-02T00:20:46Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• 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)

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

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