論文の概要: Unbounded Quantum Advantage in One-Way Strong Communication Complexity
of a Distributed Clique Labelling Relation
- arxiv url: http://arxiv.org/abs/2305.10372v2
- Date: Wed, 26 Jul 2023 18:02:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-28 19:49:57.990561
- 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 $m$,
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タスクにおける一方向の古典的通信と量子的通信の分離がグラフ $m$ の順序で増加するグラフのクラスが存在し、特に量子的複雑性は $o(1)$ であり、古典的複雑性は $\omega(\log m)$ である。
第二に、固定された制限された通信のシナリオにおける分離を克服するために必要な共有ランダム性の量に対する下界(傾きの数で線型)を証明し、直交配列の存在に接続する。
最後に,この課題を半デバイス非依存次元の目撃や,相互に偏りのない基底の検出に応用する。
関連論文リスト
- Linear gate bounds against natural functions for position-verification [0.0]
量子位置検証スキームは、証明者の空間的位置を検証しようとする。
我々は、$f$-routing(英語版)と$f$-BB84(英語版)として知られる2つのよく研究された位置検証スキームを考える。
論文 参考訳（メタデータ） (2024-02-28T19:00:10Z) - One Clean Qubit Suffices for Quantum Communication Advantage [3.729242965449096]
1つの量子ビットが純粋な状態にあり、他の全ての量子ビットが最大混合される量子通信の1つのクリーン量子ビットモデルについて検討する。
我々の証明は、Ellis, Kindler, Lifshitz, Minzerが最近導入した超収縮性不等式に基づいている。
論文 参考訳（メタデータ） (2023-10-03T19:58:08Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - Exponential separations between learning with and without quantum memory [17.763817187554096]
量子システムと力学の学習特性を学習するための量子メモリのパワーについて検討する。
多くの最先端の学習アルゴリズムは、追加の外部量子メモリへのアクセスを必要とする。
このトレードオフは、幅広い学習問題に固有のものであることを示す。
論文 参考訳（メタデータ） (2021-11-10T19:03:49Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Deterministic and Entanglement-Efficient Preparation of
Amplitude-Encoded Quantum Registers [0.533024001730262]
古典ベクトル $mathbfb$ は量子状態の振幅で符号化される。
任意の状態の$Q$ qubitsは通常、約2Q$のエンタングゲートを必要とする。
状態準備に必要な量子資源を柔軟に削減できる決定論的(非変分法)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-26T07:37:54Z) - Quantum advantage for computations with limited space [6.327095331866255]
我々は、入力が読み取り専用メモリであり、1(qu)ビットしか計算できない空間制限型計算を考える。
我々は、量子回路による3ドル、4ドル、5ドル、6ドルという計算を、カスタム2量子ゲートを利用して実験的に実証した。
論文 参考訳（メタデータ） (2020-08-14T17:31:12Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。