論文の概要: Unbounded Quantum Advantage in One-Way Strong Communication Complexity
of a Distributed Clique Labelling Relation
- arxiv url: http://arxiv.org/abs/2305.10372v1
- Date: Wed, 17 May 2023 16:58:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-18 14:41:13.987706
- Title: Unbounded Quantum Advantage in One-Way Strong Communication Complexity
of a Distributed Clique Labelling Relation
- Title（参考訳）: 分散クランクラベリング関係の一方向強通信複雑性における非有界量子優位
- Authors: Sumit Rout, Nitica Sakharwade, Some Sankar Bhattacharya, Ravishankar
Ramanathan, Pawe{\l} Horodecki
- Abstract要約: 分散クリフラベル問題により誘導される関係のクラスに対する一方向ゼロエラー古典的および量子的通信複雑性について検討する。
ここでは、プレイヤーがリソースを共有しない場合に考慮された特定の関係のクラスについて、任意のグラフに対してCCRタスクに量子的優位性はないことを示す。
我々は、このタスクの半デバイス非依存のディメンション目撃への応用と、ミューチュアルアンバイアスベースの検出について強調する。
- 参考スコア（独自算出の注目度）: 0.19090202146054183
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the one-way zero-error classical and quantum communication
complexities for a class of relations induced by a distributed clique labelling
problem. We consider two variants: 1) the receiver outputs an answer satisfying
the relation - the traditional communication complexity of relations (CCR) and
2) the receiver has non-zero probabilities of outputting every valid answer
satisfying the relation (equivalently, the relation can be fully
reconstructed), that we denote the strong communication complexity of the
relation (S-CCR). We prove that for the specific class of relations considered
here when the players do not share any resources, there is no quantum advantage
in the CCR task for any graph. On the other hand, we show that there exist,
classes of graphs for which the separation between one-way classical and
quantum communication in the S-CCR task grow with the order of the graph,
specifically, the quantum complexity is $O(1)$ while the classical complexity
is $\Omega(\log m)$. Secondly, we prove a lower bound (that is linear in the
number of cliques) on the amount of shared randomness necessary to overcome the
separation in the scenario of fixed restricted communication and connect this
to the existence of Orthogonal Arrays. Finally, we highlight some applications
of this task to semi-device-independent dimension witnessing as well as to the
detection of Mutually Unbiased Bases.
- Abstract（参考訳）: 分散クリフラベル問題により誘導される関係のクラスに対する一方向ゼロエラー古典的および量子的通信複雑性について検討する。
2つの変種を考えます
1) 受信者は、関係を満足する回答 - 従来の関係の通信複雑性(ccr) - を出力し、
2)レシーバは、関係を満たすすべての有効な回答を出力する非ゼロ確率(つまり、関係を完全に再構築することができる)を持ち、関係の強い通信複雑性を示す(s-ccr)。
プレイヤーがリソースを共有しない場合、ここで考慮される特定の関係クラスに対して、任意のグラフに対するccrタスクに量子的な利点がないことを証明します。
一方、S-CCRタスクにおける一方方向の古典的および量子的コミュニケーションの分離がグラフの順序で成長するグラフのクラスが存在することを示し、特に、量子複雑性は$O(1)$であり、古典的複雑性は$\Omega(\log m)$である。
第二に、固定された制限された通信のシナリオにおける分離を克服するために必要な共有ランダム性の量に対する下界(傾きの数で線型)を証明し、直交配列の存在に接続する。
最後に,この課題を半デバイス非依存次元の目撃や,相互に偏りのない基底の検出に応用する。
関連論文リスト
- KPZ scaling from the Krylov space [83.88591755871734]
近年,Cardar-Parisi-Zhangスケーリングをリアルタイムの相関器や自動相関器に示す超拡散が報告されている。
これらの結果から着想を得て,Krylov演算子に基づく相関関数のKPZスケーリングについて検討する。
論文 参考訳（メタデータ） (2024-06-04T20:57:59Z) - The Complexity of Being Entangled [0.0]
ニールセンの量子状態複雑性へのアプローチは、一元変換の多様体上の特定のノルムで計算された測地線の長さに状態を作るのに必要な最小の量子ゲート数に関係している。
バイパーティイトシステムでは,単一サブシステムに作用するゲートがコストがかからないノルムに対応する結合複雑性について検討する。
論文 参考訳（メタデータ） (2023-11-07T19:00:02Z) - 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) - Pipelined correlated minimum weight perfect matching of the surface code [56.01788646782563]
最小ウェイト完全マッチングを用いて表面コードを復号するパイプライン手法について述べる。
独立な非通信可能な並列化処理段階は、潜在的な相関に従ってグラフを再重み付けする。
後続の一般的なステージがマッチングを終了します。
完全にフォールトトレラントなトーリック, 回転しない, 回転する曲面符号に対して, 新たなアルゴリズムの有効性を検証した。
論文 参考訳（メタデータ） (2022-05-19T19:58:02Z) - Permutation Compressors for Provably Faster Distributed Nonconvex
Optimization [68.8204255655161]
本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。
MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
論文 参考訳（メタデータ） (2021-10-07T09:38:15Z) - Experimental violations of Leggett-Garg's inequalities on a quantum
computer [77.34726150561087]
単一および多ビット系におけるLeggett-Garg-Bellの不等式違反を実験的に観察する。
本分析では, 量子プラットフォームの限界に注目し, 上記の相関関数は, 量子ビットの数や回路深さが大きくなるにつれて, 理論的予測から逸脱することを示した。
論文 参考訳（メタデータ） (2021-09-06T14:35:15Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳（メタデータ） (2021-06-11T18:00:09Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Solution to the Quantum Symmetric Simple Exclusion Process : the
Continuous Case [0.0]
無限大極限における一次元 Q-SSEP の不変確率測度に対する解を提案する。
本稿では,Q-SSEP相関関数の解釈を,驚くべきコネラトニクスとアソシアヘドロン多面体を通して,偶然に指摘する。
論文 参考訳（メタデータ） (2020-06-22T13:20:40Z) - Tight Limits on Nonlocality from Nontrivial Communication Complexity;
a.k.a. Reliable Computation with Asymmetric Gate Noise [19.970633213740363]
ある種の超量子非局所相関の存在が通信複雑性の崩壊を引き起こすことは、長い間知られている。
最大勝利確率が量子値を超える任意の物理理論において、通信複雑性が崩壊することを示す。
我々は、0.91の結果が証明戦略の大規模なクラスで可能な限り最良のものであることを示す。
論文 参考訳（メタデータ） (2018-09-25T22:39:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。