論文の概要: Bounds on oblivious multiparty quantum communication complexity

• arxiv url: http://arxiv.org/abs/2210.15402v1
• Date: Thu, 27 Oct 2022 13:09:51 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-21 08:14:46.980560
• Title: Bounds on oblivious multiparty quantum communication complexity
• Title（参考訳）: 暗黙のマルチパーティ量子通信複雑性の境界
• Authors: Fran\c{c}ois Le Gall and Daiki Suruga
• Abstract要約: 幅広い種類の関数に対して、その難解な量子$k$-party通信複雑性に対して強い下界を証明する方法を示す。 特に、最適$Omega(ksqrtn)$low bound on the oblivious quantum $k$-party communication complexity of the $n$-bit Set-Disjointness function。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The main conceptual contribution of this paper is investigating quantum multiparty communication complexity in the setting where communication is \emph{oblivious}. This requirement, which to our knowledge is satisfied by all quantum multiparty protocols in the literature, means that the communication pattern, and in particular the amount of communication exchanged between each pair of players at each round is fixed \emph{independently of the input} before the execution of the protocol. We show, for a wide class of functions, how to prove strong lower bounds on their oblivious quantum $k$-party communication complexity using lower bounds on their \emph{two-party} communication complexity. We apply this technique to prove tight lower bounds for all symmetric functions with \textsf{AND} gadget, and in particular obtain an optimal $\Omega(k\sqrt{n})$ lower bound on the oblivious quantum $k$-party communication complexity of the $n$-bit Set-Disjointness function. We also show the tightness of these lower bounds by giving (nearly) matching upper bounds.
• Abstract（参考訳）: 本論文の主な概念的貢献は,通信がemph{oblivious} となる環境での量子マルチパーティ通信の複雑性について考察することである。 この要件は、我々の知識が文献中の全ての量子マルチパーティプロトコルによって満たされることであり、通信パターン、特に各ラウンドにおける各プレイヤーのペア間で交換される通信量は、プロトコルの実行前に入力と無依存に固定されることを意味する。 広義の関数に対して、これらの難解な量子$k$-party通信複雑性の強い下界を、それらの 'emph{two-party} 通信複雑性の低い境界を用いて証明する方法を示す。 我々はこの手法を, \textsf{and} ガジェットを用いたすべての対称関数の厳密な下界の証明に適用し,特に,n$-bit の set-disjointness 関数の任意の量子 $k$-party 通信複雑性に対して最適な $\omega(k\sqrt{n})$ の上限を求める。 また,上界に(ほぼ)一致するようにすることで,下界のタイトさを示す。

関連論文リスト

• The multimode conditional quantum Entropy Power Inequality and the squashed entanglement of the extreme multimode bosonic Gaussian channels [53.253900735220796]
  不等式はボゾン量子モードの最も一般的な線形混合の出力の最小条件フォン・ノイマンエントロピーを決定する。 ボソニック量子系は、量子状態における電磁放射の数学的モデルを構成する。
  論文  参考訳（メタデータ） (2024-10-18T13:59:50Z)
• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement [0.0]
  量子リソースは、この課題に対処する上で、古典的な手法よりも有利である。 受信機と送信機がマルチキュービットのGreenberger-Horne-Zeilinger(GHZ)状態を共有すると、分散入力のある種のグローバル関数は、送信機からの古典的通信の1ビットでしか計算できないことを示す。 また, 絡み合いに基づくプロトコルは, 白色雑音下では顕著な堅牢性を示すことを示す。
  論文  参考訳（メタデータ） (2024-09-20T05:17:09Z)
• General Communication Enhancement via the Quantum Switch [15.779145740528417]
  我々は$mathcalP_n>0$が、量子$tt SWITCH$による通信強化に必要な条件であり、十分な条件であると予想する。 次に、BB84チャネルのプライベートキャパシティを高める量子$tt SWITCH$を含む通信プロトコルを定式化する。
  論文  参考訳（メタデータ） (2024-07-03T00:47:13Z)
• Unbounded quantum advantage in communication complexity measured by distinguishability [0.0]
  本研究では,送信者の入力を識別し,通信の複雑さを計測する新しい視点を採用する。 我々は、ランダムアクセスコードの一般的なバージョンと、グラフで定義される等式問題という、コミュニケーション複雑性タスクの2つの重要なカテゴリに焦点を当てる。 古典的コミュニケーションと量子通信の区別可能性の比が同じ成功度を達成するための比は、これらのタスクの複雑さと共にエスカレートすることを示す。
  論文  参考訳（メタデータ） (2024-01-23T16:48:59Z)
• Unbounded Quantum Advantage in One-Way Strong Communication Complexity of a Distributed Clique Labelling Relation [0.19090202146054183]
  分散クリフラベル問題により誘導される関係のクラスに対する一方向ゼロエラー古典的および量子的通信複雑性について検討する。 ここでは、プレイヤーがリソースを共有しない場合に考慮された特定の関係のクラスについて、任意のグラフに対してCCRタスクに量子的優位性はないことを示す。 我々は、このタスクの半デバイス非依存のディメンション目撃への応用と、ミューチュアルアンバイアスベースの検出について強調する。
  論文  参考訳（メタデータ） (2023-05-17T16:58:05Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。 本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。 我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
  論文  参考訳（メタデータ） (2023-05-10T20:29:29Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。 量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。 我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
  論文  参考訳（メタデータ） (2021-06-11T18:00:09Z)
• General theory of quantum fingerprinting network [6.768616299601037]
  マルチパーティ量子フィンガープリントは、多くのパーティからのメッセージが同じかどうかについて研究する。 量子フィンガープリントネットワークの一般的なモデルを提供し、関係関数を$fR$と定義し、対応する決定規則を与える。 マルチパーティ量子フィンガープリントと2パーティ量子フィンガープリントに基づくプロトコルを比較し、マルチパーティ量子フィンガープリントプロトコルには明らかな利点があることを見出した。
  論文  参考訳（メタデータ） (2020-11-12T09:00:15Z)
• 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)

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

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