論文の概要: Unbounded Quantum Advantage in Communication with Minimal Input Scaling
- arxiv url: http://arxiv.org/abs/2305.10372v3
- Date: Fri, 29 Nov 2024 13:45:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-02 15:16:07.395689
- Title: Unbounded Quantum Advantage in Communication with Minimal Input Scaling
- Title（参考訳）: 最小入力スケーリングを用いた通信における非有界量子アドバンテージ
- Authors: Sumit Rout, Nitica Sakharwade, Some Sankar Bhattacharya, Ravishankar Ramanathan, Paweł Horodecki,
- Abstract要約: 一般の硬貨を使わずに関係の再構築を行う場合, 量子的に非有界な利点を示す。
また、このタスクの半デバイス非依存なディメンションの目撃や、ミューチュアルアンバイアスベースの検出への応用についても強調する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: In communication complexity-like problems, previous studies have shown either an exponential quantum advantage or an unbounded quantum advantage with an exponentially large input set $\Theta(2^{n})$ bits with respect to classical communication $\Theta(n)$ bits. In the former, the quantum and classical separation grows exponentially in input while the latter's quantum communication resource is a constant. Remarkably, it was still open whether an unbounded quantum advantage exists while the inputs do not scale exponentially. Here we answer this question affirmatively using an input size of optimal order. Considering two variants as tasks: 1) distributed computation of relation and 2) {\it relation reconstruction}, we study the one-way zero-error communication complexity of a relation induced by a distributed clique labelling problem for orthogonality graphs. While we prove no quantum advantage in the first task, we show an {\it unbounded quantum advantage} in relation reconstruction without public coins. Specifically, for a class of graphs with order $m$, the quantum complexity is $\Theta(1)$ while the classical complexity is $\Theta(\log m)$. Remarkably, the input size is $\Theta(\log m)$ bits and the order of its scaling with respect to classical communication is {\it minimal}. This is exponentially better compared to previous works. Additionally, we prove a lower bound (linear in the number of maximum cliques) on the amount of classical public coin necessary to overcome the separation in the scenario of 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（参考訳）: 通信複雑性のような問題において、以前の研究では、古典的な通信に対して、指数的に大きい入力セット$\Theta(2^{n})$ bitsで指数的量子優位または非有界量子優位を示す。
(n)$ bits.
前者では、量子と古典の分離は指数関数的に増加し、後者の量子通信資源は定数である。
注目すべきは、入力が指数関数的にスケールしない間に、非有界な量子優位性が存在するかどうかである。
ここでは、最適順序の入力サイズを用いて肯定的にこの質問に答える。
タスクとして2つの変種を考慮する。
1)関係の分散計算及び分散計算
直交グラフに対する分散斜めラベリング問題により誘導される関係の一方向ゼロエラー通信複雑性について検討する。
最初のタスクでは量子上の優位性は証明されていないが、公開硬貨を使わずに関係の再構築において量子上の優位性を示す。
具体的には、次数$m$のグラフのクラスに対して、量子複雑性は$\Theta(1)$であり、古典複雑性は$\Theta(\log)である。
m)$
注目すべきは、入力サイズが$\Theta(\log)であることだ。
m)$bits で、古典的な通信に対するスケーリングの順序は、最小限である。
これは以前の作品より指数関数的に優れている。
さらに、制限された通信のシナリオにおける分離を克服するために必要な古典的公鋳貨幣の量に対する下限(最大斜め数の直線)を証明し、直交配列の存在と結び付ける。
最後に、このタスクの半デバイス非依存なディメンション目撃への応用と、ミューチュアルアンバイアスベースの検出について強調する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。