論文の概要: Unbounded quantum advantage in communication complexity measured by distinguishability
- arxiv url: http://arxiv.org/abs/2401.12903v2
- Date: Tue, 24 Dec 2024 05:09:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-25 15:52:33.933171
- Title: Unbounded quantum advantage in communication complexity measured by distinguishability
- Title(参考訳): 識別可能性による通信複雑性の非有界量子優位性
- Authors: Satyaki Manna, Anubhav Chaturvedi, Debashis Saha,
- Abstract要約: タスクの複雑さを、それを達成するのに必要な最小限の識別可能性によって測定する。
同じ成功度を達成するために必要となる、最小の識別可能性の古典-量子比が指数関数的にエスカレートすることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: Communication complexity is a fundamental aspect of information science, concerned with the amount of communication required to solve a problem distributed among multiple parties. The standard quantification of one-way communication complexity relies on the minimal dimension of the communicated systems. In this paper, we measure the communication complexity of a task by the minimal distinguishability required to accomplish it, while leaving the dimension of the communicated systems unconstrained. Distinguishability is defined as the maximum probability of correctly guessing the sender's input from the message, quantifying the message's distinctiveness relative to the sender's input. This measure becomes especially relevant when maintaining the confidentiality of the sender's input is essential. After establishing the generic framework, we focus on three relevant families of communication complexity tasks -- the random access codes, equality problems defined by graphs and the pair-distinguishability tasks. We derive general lower bounds on the minimal classical distinguishability as a function of the success metric of these tasks. We demonstrate that quantum communication outperforms classical communication, presenting explicit protocols and utilizing semi-definite programming methods. In particular, we demonstrate unbounded quantum advantage for random access codes and Hadamard graph-based equality problems. Specifically, we show that the classical-to-quantum ratio of minimal distinguishability required to achieve the same success metric escalates polynomially and exponentially with the complexity of these tasks, reaching arbitrarily large values.
- Abstract(参考訳): コミュニケーションの複雑さは情報科学の基本的な側面であり、複数の当事者に分散した問題を解決するのに必要なコミュニケーションの量に関係している。
ワンウェイ通信複雑性の標準的な定量化は、通信システムの最小次元に依存する。
本稿では,タスクの通信複雑性を,通信システムの寸法を制約なく保ちながら,それを達成するために必要な最小限の識別可能性によって測定する。
識別可能性(distinguishability)は、送信者の入力をメッセージから正しく推測し、送信者の入力に対してメッセージの特異性を定量化する最大確率として定義される。
この尺度は、送信者の入力の機密性を維持することが不可欠であるときに特に重要となる。
汎用フレームワークを確立した後、ランダムアクセスコード、グラフで定義される平等問題、ペア識別可能性タスクの3つの関連した通信複雑性タスクに焦点を合わせます。
これらのタスクの成功距離の関数として、最小古典的微分可能性に関する一般的な下界を導出する。
量子通信は古典的通信よりも優れており、明示的なプロトコルを示し、半定値プログラミング手法を利用する。
特に,ランダムアクセス符号とアダマールグラフに基づく等式問題に対する非有界量子優位性を示す。
具体的には、同じ成功度を達成するために必要となる最小微分可能性の古典-量子比が、これらのタスクの複雑さと共に多項式的に指数関数的にエスカレートし、任意に大きな値に達することを示す。
関連論文リスト
- Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement [0.0]
量子リソースは、この課題に対処する上で、古典的な手法よりも有利である。
受信機と送信機がマルチキュービットのGreenberger-Horne-Zeilinger(GHZ)状態を共有すると、分散入力のある種のグローバル関数は、送信機からの古典的通信の1ビットでしか計算できないことを示す。
また, 絡み合いに基づくプロトコルは, 白色雑音下では顕著な堅牢性を示すことを示す。
論文 参考訳(メタデータ) (2024-09-20T05:17:09Z) - Semantic Communication for Cooperative Perception using HARQ [51.148203799109304]
我々は重要セマンティック情報を抽出するために重要地図を活用し、協調的な知覚セマンティックコミュニケーションフレームワークを導入する。
周波数分割多重化(OFDM)とチャネル推定と等化戦略を併用して,時間変化によるマルチパスフェーディングによる課題に対処する。
我々は,ハイブリッド自動繰り返し要求(HARQ)の精神において,我々の意味コミュニケーションフレームワークと統合された新しい意味エラー検出手法を提案する。
論文 参考訳(メタデータ) (2024-08-29T08:53:26Z) - An operational definition of quantum information scrambling [0.0]
量子情報スクランブル(QIS)は、いくつかの量子系の特徴である。
本稿では,QISの定式化に基づく量子状態の量子化に基づく新しい計算効率のQIS量化器を提案する。
等尺的量子進化によって引き起こされるQISの度合いを反映した最適推定確率が、アクセス可能な最小情報に直接接続されていることを示す。
論文 参考訳(メタデータ) (2023-12-18T19:00:01Z) - Cognitive Semantic Communication Systems Driven by Knowledge Graph:
Principle, Implementation, and Performance Evaluation [74.38561925376996]
単一ユーザと複数ユーザのコミュニケーションシナリオに対して,認知意味コミュニケーションフレームワークが2つ提案されている。
知識グラフから推論規則をマイニングすることにより,効果的な意味補正アルゴリズムを提案する。
マルチユーザ認知型セマンティックコミュニケーションシステムにおいて,異なるユーザのメッセージを識別するために,メッセージ復元アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-15T12:01:43Z) - Emergent Quantized Communication [34.31732248872158]
本稿では,メッセージの量子化という,離散的なコミュニケーションを実現するための代替手法を提案する。
メッセージの量子化により、モデルのエンドツーエンドのトレーニングが可能になり、複数のセットアップで優れたパフォーマンスを実現します。
論文 参考訳(メタデータ) (2022-11-04T12:39:45Z) - Semantic-Native Communication: A Simplicial Complex Perspective [50.099494681671224]
トポロジカル空間の観点から意味コミュニケーションを研究する。
送信機はまずデータを$k$の単純複素数にマッピングし、その高次相関を学習する。
受信機は構造を復号し、行方不明または歪んだデータを推測する。
論文 参考訳(メタデータ) (2022-10-30T22:33:44Z) - Bounds on oblivious multiparty quantum communication complexity [0.0]
幅広い種類の関数に対して、その難解な量子$k$-party通信複雑性に対して強い下界を証明する方法を示す。
特に、最適$Omega(ksqrtn)$low bound on the oblivious quantum $k$-party communication complexity of the $n$-bit Set-Disjointness function。
論文 参考訳(メタデータ) (2022-10-27T13:09:51Z) - Quantum contextuality provides communication complexity advantage [0.683495465775299]
量子状態と十分小さな次元の観測可能量に対して、量子優位性を持つ通信タスクが存在することを示す。
本稿では,これらの各通信タスクを,量子鍵分布のための半デバイス独立プロトコルに変換する方法について述べる。
論文 参考訳(メタデータ) (2022-05-06T15:40:57Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳(メタデータ) (2022-03-30T02:02:16Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。