論文の概要: Clifford Strategies in Interactive Protocols are Classically Simulatable
- arxiv url: http://arxiv.org/abs/2410.12030v2
- Date: Fri, 28 Feb 2025 01:57:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-03 13:38:25.405113
- Title: Clifford Strategies in Interactive Protocols are Classically Simulatable
- Title（参考訳）: 対話型プロトコルにおけるClifford Strategiesは古典的にシミュレート可能である
- Authors: Itay Shalit,
- Abstract要約: 複雑性クラス $textClifford-MIPast$ を導入し、量子プロバーを Clifford 演算に制限する。
このモデルにおける戦略は古典的ランダム性共有プロバーによってシミュレートできることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: The complexity class $\text{MIP}^\ast$ consists of all languages decidable by an efficient classical verifier interacting with multiple entanglement-sharing and non-communicating quantum provers. Notably, $\text{MIP}^\ast$ was proved to equal $\text{RE}$, the class of all recursively enumerable languages. We introduce the complexity class $\text{Clifford-MIP}^\ast$, which restricts quantum provers to Clifford operations and classical post-processing of measurement results. We show that strategies in this model can be simulated by classical randomness-sharing provers. In other words, Clifford operations alone do not suffice to generate non-classical correlations in interactive protocols. Consequently, $\text{Clifford-MIP}^\ast = \text{MIP}$, a vastly smaller complexity class compared to $\text{RE}$. Moreover, we resolve an open question posed by Kalai et al. (STOC 2023), by showing that quantum advantage in any single-round non-local game requires at least two provers operating outside the $\text{Clifford-MIP}^\ast$ computational model. This rules out a proposed approach for significantly improving the efficiency of tests for quantum advantage that are based on compiling non-local games into single-prover interactive protocols.
- Abstract（参考訳）: 複雑性クラス $\text{MIP}^\ast$ は、複数の絡み合いと非通信量子プローバーと相互作用する効率的な古典的検証器によって決定できる全ての言語からなる。
特に、$\text{MIP}^\ast$は、すべての再帰可算言語のクラスである$\text{RE}$と等しいことが証明された。
我々は、量子プロバーをクリフォード演算と古典的な測定結果の後処理に制限する複雑性クラス $\text{Clifford-MIP}^\ast$ を導入する。
このモデルにおける戦略は古典的ランダム性共有プロバーによってシミュレートできることを示す。
言い換えれば、クリフォード演算だけでは対話プロトコルにおいて古典的でない相関を生成するのに十分ではない。
その結果、$\text{Clifford-MIP}^\ast = \text{MIP}$は、$\text{RE}$に比べてはるかに小さな複雑性クラスである。
さらに、Kalai et al (STOC 2023) が提起したオープンな疑問を解決し、任意の単一ラウンドの非局所ゲームにおける量子的優位性は、$\text{Clifford-MIP}^\ast$計算モデルの外で動作する少なくとも2つのプロバーを必要とすることを示す。
これは、非ローカルなゲームを単一プロデューサの対話プロトコルにコンパイルすることに基づいて、量子優位性のテストの効率を大幅に改善するための提案されたアプローチを規定する。
関連論文リスト
- Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states [0.552480439325792]
我々は、$T$ゲート数でドープされた$N$-qubit Clifford回路の古典的シミュラビリティについて検討する。
我々は,制御パウリゲートを用いたCAMPSにおけるMPS成分の絡み合いを低減するために,単純な解離アルゴリズムを用いる。
この研究は、$t$ドープ回路の古典的シミュレート可能性を理解するために、CAMPSに基づく汎用的なフレームワークを確立する。
論文 参考訳（メタデータ） (2024-12-23T01:26:40Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Simulation of IBM's kicked Ising experiment with Projected Entangled
Pair Operator [71.10376783074766]
我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。
提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。
我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
論文 参考訳（メタデータ） (2023-08-06T10:24:23Z) - Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions [3.9482012852779085]
ウィグナー関数形式主義は、量子状態の非古典的側面とその古典的シミュラビリティを調べる上で重要な役割を担っている。
フレーム化ウィグナー関数に基づく量子クリフォード回路の新しい古典的シミュレーション法を提案する。
論文 参考訳（メタデータ） (2023-07-31T14:02:33Z) - Learning efficient decoders for quasi-chaotic quantum scramblers [3.823356975862005]
我々は,スクランブラーの知識がなくても,スクランブラー情報の検索が可能であることを示す。
古典デコーダは、ランダムなユニタリによってスクランブルされた情報の1つを忠実に検索することができる。
結果は古典的な形で量子ユニタリの正則性を学ぶことができることを示している。
論文 参考訳（メタデータ） (2022-12-21T20:19:53Z) - On the relation between completely bounded and $(1,cb)$-summing maps
with applications to quantum XOR games [65.51757376525798]
一般作用素空間から C$*$-代数の双対への線型写像が与えられたとき、その完全有界ノルムは、その$(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
論文 参考訳（メタデータ） (2021-12-09T21:06:52Z) - Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
効率的な分散コンピューティングは、リソース要求タスクを解決するためのスケーラブルな戦略を提供する。
量子リソースはこのタスクに適しており、古典的手法よりも優れた明確な戦略を提供する。
我々は,ベルのような不等式に,新たなコミュニケーション複雑性タスクのクラスを関連付けることができることを証明した。
論文 参考訳（メタデータ） (2021-06-11T18:00:09Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Hadamard-free circuits expose the structure of the Clifford group [9.480212602202517]
クリフォード群は量子ランダム化ベンチマーク、量子トモグラフィ、誤り訂正プロトコルにおいて中心的な役割を果たす。
任意のクリフォード作用素が標準形式$F_HSF$で一意に書けることを示す。
ランダムな一様クリフォード作用素と対称群上のマロース分布の間の驚くべき接続が強調される。
論文 参考訳（メタデータ） (2020-03-20T17:51:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。