論文の概要: Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic

• arxiv url: http://arxiv.org/abs/2506.19369v1
• Date: Tue, 24 Jun 2025 06:57:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-25 19:48:23.526382
• Title: Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic
• Title（参考訳）: Gottesman-Knill氏によるワンウェイ通信の複雑さに関する制限:量子アドバンテージをマジックに追跡
• Authors: Snehasish Roy Chowdhury, Sahil Gopalkrishna Naik, Ananya Chakraborty, Ram Krishna Patra, Subhendu B. Ghosh, Pratik Ghosal, Manik Banik, Ananda G. Maity,
• Abstract要約: 素次元量子システムを用いて実装された任意の一方的な通信複雑性プロトコルは、常に同じ次元の古典的なシステムと通信することで、正確にシミュレート可能であることを示す。 量子計算における Gottesman-Knill の定理と直接的に類似して、我々の結果は一方的な通信複雑性における量子上の優位性を実現するのに不可欠である同じ資源を識別する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A recent influential result by Frenkel and Weiner establishes that in presence of shared randomness (SR), any input-output correlation, with a classical input provided to one party and a classical output produced by a distant party, achievable with a d-dimensional quantum system can always be reproduced by a d-dimensional classical system. In contrast, quantum systems are known to offer advantages in communication complexity tasks, which consider an additional input variable to the second party. Here, we show that, in presence of SR, any one-way communication complexity protocol implemented using a prime-dimensional quantum system can always be simulated exactly by communicating a classical system of the same dimension, whenever quantum protocols are restricted to stabilizer state preparations and stabilizer measurements. In direct analogy with the Gottesman-Knill theorem in quantum computation, which attributes quantum advantage to non-stabilizer (or magic) resources, our result identifies the same resources as essential for realizing quantum advantage in one-way communication complexity. We further present explicit tasks where `minimal magic' suffices to offer a provable quantum advantage, underscoring the efficient use of such resources in communication complexity.
• Abstract（参考訳）: Frenkel と Weiner の最近の影響力のある結果は、共有ランダム性(SR)、任意の入力出力相関、一方に古典的な入力が提供され、遠方から得られる古典的な出力がd-次元量子システムで達成可能なことは、常にd-次元の古典的システムによって再現可能であることを証明している。 対照的に、量子システムは、第2者への追加入力変数を考慮した通信複雑性タスクにおいて利点を提供することが知られている。 ここでは、SRが存在する場合、素次元量子システムを用いて実装された任意の一方的な通信複雑性プロトコルは、常に同じ次元の古典的なシステムと通信することで、量子プロトコルが安定化状態の準備や安定化器の測定に制限される場合、正確にシミュレート可能であることを示す。 量子計算における Gottesman-Knill の定理と直接的に類似しており、これは非安定化器(またはマジック)資源に量子的優位性をもたらすものである。 さらに、「最小の魔法」が証明可能な量子的優位性を提供するのに十分であるような明示的なタスクを提示し、コミュニケーションの複雑さにおけるそのようなリソースの効率的な利用を裏付ける。

関連論文リスト

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか? 我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。 我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Quantum-Amplified Simultaneous Quantum-Classical Communications [0.2982610402087727]
  本稿では,従来のFSOシステムを最小限に修正して,従来の通信と共存する量子通信の要素を提供する方法について検討する。 しかし、スタンドアローンの量子通信とは対照的に、余分なレシーバの複雑さを犠牲にしているだけである。
  論文  参考訳（メタデータ） (2024-05-15T06:44:01Z)
• Quantum Advantage: A Single Qubit's Experimental Edge in Classical Data Storage [5.669806907215807]
  我々は,古典情報記憶における基本量子システムの有効性を確立するためのフォトニック量子プロセッサの実験を行った。 我々の研究は、短期量子技術における即時応用の道を開いた。
  論文  参考訳（メタデータ） (2024-03-05T05:09:32Z)
• Classical Verification of Quantum Learning [42.362388367152256]
  量子学習の古典的検証のための枠組みを開発する。 そこで我々は,新しい量子データアクセスモデルを提案し,これを"mixture-of-superpositions"量子例と呼ぶ。 この結果から,学習課題における量子データの潜在能力は無限ではないものの,古典的エージェントが活用できることが示唆された。
  論文  参考訳（メタデータ） (2023-06-08T00:31:27Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  量子計算を古典的な結果によって補う手法を提案する。 予測の利点を生かして、新しいタイプの量子測度がもたらされる。 予測量子測定では、古典計算と量子計算の結果の組み合わせは最後にのみ起こる。
  論文  参考訳（メタデータ） (2022-09-12T15:47:44Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  証明者と検証者の間の「相互作用」は、検証可能性と実装のギャップを埋めることができる。 イオントラップ量子コンピュータを用いた対話型量子アドバンストプロトコルの最初の実装を実演する。
  論文  参考訳（メタデータ） (2021-12-09T19:00:00Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。 量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。 我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
  論文  参考訳（メタデータ） (2021-06-11T18:00:09Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  量子コンピューティングの標準的なアプローチは、古典的にシミュレート可能なフォールトトレラントな演算セットを促進するという考え方に基づいている。 量子回路の古典的準確率シミュレーションをどのように促進するかを示す。
  論文  参考訳（メタデータ） (2021-03-12T20:58:41Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  53量子ビット量子プロセッサにおける量子スクランブルのダイナミクスを実験的に検討する。 演算子の拡散は効率的な古典的モデルによって捉えられるが、演算子の絡み合いは指数関数的にスケールされた計算資源を必要とする。
  論文  参考訳（メタデータ） (2021-01-21T22:18:49Z)

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

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