論文の概要: Optimal and Verifiable Quantum Advantages in Communication Complexity
- arxiv url: http://arxiv.org/abs/2610.05585v1
- Date: Sun, 04 Oct 2026 22:40:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-10 12:50:11.198789
- Title: Optimal and Verifiable Quantum Advantages in Communication Complexity
- Title（参考訳）: 通信複雑度における最適かつ検証可能な量子アドバンテージ
- Abstract要約: 探索問題に対する通信複雑性の最適量子古典的分離を確立する。
効率的な全探索問題の族は、量子一方向通信とランダム化された一方向通信を分離する$n$対$_d(nd)$を達成している。
- 参考スコア（独自算出の注目度）: 2.9921676170902676
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently verifiable total search problems achieving an $n$ versus $Ω_d(n^d)$ separation between quantum one-way and randomized one-way communication for every fixed $d \ge 2$. In the quantum protocol, Alice prepares her message using a single unitary from the $d$th level of the Clifford hierarchy, and Bob performs a Clifford measurement. This separation is asymptotically optimal under this restriction on Alice's message. For $d = 2$, Alice's message is a stabilizer state and Bob's measurement is Clifford, so the protocol uses no magic, yet achieves an optimal quadratic quantum advantage. Finally, we discuss how these separations can be adapted to near-term quantum advantage experiments in which the demonstrated advantage is both unconditional and efficiently verifiable.
- Abstract（参考訳）: 探索問題に対する通信複雑性の最適量子古典的分離を確立する。
ペラシック・フーリエ・フィッシング (Pelagic Fourier Fishing) と呼ばれる全探索問題を導入し、$n$-qubitの量子ワンウェイプロトコルを許容していることを示し、一方、ランダム化された全ての双方向プロトコルは$Ω(2^n)$の通信を必要とすることを示した。
次に、多項式時間で解を検証できる問題の変種を導入する。
この変種はまた$n$-qubitの量子ワンウェイプロトコルを許容するが、ランダム化された任意のワンウェイプロトコルは$Ω(2^n)$の通信を必要とする。
また、固定された$d \ge 2$に対して、量子一方向とランダム化された一方向の通信を分離する$n$対$Ω_d(n^d)$に対して効率よく検証可能な全探索問題の族を構築する。
量子プロトコルでは、アリスはクリフォード階層の$d$thレベルから単一のユニタリを使用してメッセージを準備し、ボブはクリフォードの測定を行う。
この分離は、アリスのメッセージに対するこの制限の下で漸近的に最適である。
$d = 2$の場合、アリスのメッセージは安定化状態であり、ボブの測定はクリフォードであり、このプロトコルはマジックを使用しないが、最適二次量子優位性を達成する。
最後に、これらの分離が、実証された利点が無条件かつ効率よく検証可能な、短期量子優位実験にどのように適応できるかについて議論する。
関連論文リスト
- On the Limits of Quantum Multiparty Simultaneous Communication [1.7205106391379026]
我々はtextscIndex Coordination の自然な $k$-party 一般化を通じて,多元的指数分離を確立する。
量子重ね合わせは、公共のランダム性によって得られる調整を効率的にシミュレートできないことを示し、この分離を任意の$k$に拡張する。
論文 参考訳（メタデータ） (2026-09-09T15:07:22Z) - Optimal complex conjugation of unknown isometry channels [0.0]
並列プロトコルは、適応的および不定値順序戦略を含む一般的な量子超チャネルの中でも最適であることを示す。
また、量子シュル変換と二重クレブシュ-ゴルダン変換に基づく回路構成を示し、回路複雑性は$O(mathrmpoly(D,1/))$である。
論文 参考訳（メタデータ） (2026-07-31T06:13:40Z) - Quantum memory advantage for quantum process tomography [2.956729394666618]
ブラックボックスアクセスから未知の量子チャネルを学習するタスクである量子プロセストモグラフィは、量子情報の中心的な問題である。
量子メモリのないプロトコルが実験に適応しても、量子メモリはクエリ・複雑性に有利であることを示す。
この結果から,量子プロセストモグラフィーと量子メモリとの厳密な学習分離が確立された。
論文 参考訳（メタデータ） (2026-07-15T06:09:08Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Efficient Pauli channel estimation with logarithmic quantum memory [17.16536262746742]
a protocol can estimated the eigen values of a Pauli channel to error $epsilon$ using only $O(log n/epsilon2)$ ancilla and $tildeO(n2/epsilon2)$ measured。
我々の知識によれば、量子メモリの対数的に多くの量子ビットが指数統計上の優位性のために十分である最初の量子学習タスクである。
論文 参考訳（メタデータ） (2023-09-25T17:53:12Z) - Lattice-Based Quantum Advantage from Rotated Measurements [2.0249250133493195]
我々は、$XY$-planeの量子ビット測定範囲全体を利用する新しい手法を示す。
パウリ-Z$補正まで$XY$平面上の任意の状態のブラインド遠隔準備のためのワンラウンドプロトコルを構築する。
論文 参考訳（メタデータ） (2022-10-18T20:18:15Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
パラメータ化量子回路で完了した2プレーヤゼロサムゲームとして,両部絡み検出を再構成する。
このプロトコルを線形光ネットワーク上で実験的に実装し、5量子量子純状態と2量子量子混合状態の両部絡み検出に有効であることを示す。
論文 参考訳（メタデータ） (2022-03-15T09:46:45Z) - 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) - Communication Cost of Quantum Processes [49.281159740373326]
分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。
重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。
クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
論文 参考訳（メタデータ） (2020-02-17T08:51:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。