論文の概要: 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 16:38:45.059162
• Title: Clifford Strategies in Interactive Protocols are Classically Simulatable
• Title（参考訳）: 対話型プロトコルにおけるClifford Strategiesは古典的にシミュレート可能である
• Authors: Itay Shalit,
• Abstract要約: 複雑性クラス $textClifford-MIPast$ を導入し、量子プロバーを Clifford 演算に制限する。 このモデルにおける戦略は古典的ランダム性共有プロバーによってシミュレートできることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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つのプロバーを必要とすることを示す。 これは、非ローカルなゲームを単一プロデューサの対話プロトコルにコンパイルすることに基づいて、量子優位性のテストの効率を大幅に改善するための提案されたアプローチを規定する。

関連論文リスト

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  p/mBQP, p/mQ(C)MA, $textp/mQSZK_texthv$, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, p/mPSPACEの構造結果を示す。 驚いたことに、我々の発見は、彼らの古典的な類推から分岐する関係を明らかにした。 応用においては、量子暗号、量子特性試験、およびユニタリ合成における興味深い問題に対処する。
  論文  参考訳（メタデータ） (2024-11-06T07:29:52Z)
• QuCLEAR: Clifford Extraction and Absorption for Significant Reduction in Quantum Circuit Size [8.043057448895343]
  現在利用可能な量子デバイスは、実行された量子回路の忠実さを低下させるノイズの多い量子ゲートに悩まされている。 本稿では,量子回路の最適化を目的としたコンパイルフレームワークQuCLEARを提案する。
  論文  参考訳（メタデータ） (2024-08-23T18:03:57Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。 次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
  論文  参考訳（メタデータ） (2023-11-07T04:59:02Z)
• Efficient learning of $t$-doped stabilizer states with single-copy measurements [7.5275459858139175]
  我々は,Cifford回路が生成する状態を最大$O(log n)$非Ciffordゲートで学習するために,非適応的な単一コピー測定のみを用いる効率的な量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-14T09:01:47Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。 提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。 我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
  論文  参考訳（メタデータ） (2023-08-06T10:24:23Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。 本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。 我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
  論文  参考訳（メタデータ） (2023-05-10T20:29:29Z)
• Communication complexity of entanglement assisted multi-party computation [11.820804392113294]
  プレーヤが2ドル、ドットが2ドル、n$が1に適切な情報を伝達する必要がある場合、プレーヤが$n$のマルチパーティ計算問題を考える。 量子プロトコル(複雑性$(n-1)log n$ bits)と古典的プロトコル(複雑性$(n-1)2(log n2$)ビット)を示す。 これは、我々の量子プロトコルが古典的プロトコルよりも厳密に優れていることを示している。
  論文  参考訳（メタデータ） (2023-05-08T03:10:08Z)
• Learning efficient decoders for quasi-chaotic quantum scramblers [3.823356975862005]
  我々は,スクランブラーの知識がなくても,スクランブラー情報の検索が可能であることを示す。 古典デコーダは、ランダムなユニタリによってスクランブルされた情報の1つを忠実に検索することができる。 結果は古典的な形で量子ユニタリの正則性を学ぶことができることを示している。
  論文  参考訳（メタデータ） (2022-12-21T20:19:53Z)
• Approximate traces on groups and the quantum complexity class $\operatorname{MIP}^{co,s}$ [0.0]
  量子交換相関に近似をエンコードするqc-モジュラーの概念を導入する。 計算可能なqc-モジュラーの存在は、上記の質問の自然な変形に対して負の答えを与えることを示す。
  論文  参考訳（メタデータ） (2022-09-16T15:45:49Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• 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)
• Communication Complexity of Private Simultaneous Quantum Messages Protocols [0.609170287691728]
  本稿では、量子通信の利点と、プライベート同時量子メッセージモデルの事前絡み合いについて検討する。 プライバシ条件は,PSQMモデルの通信コストを必然的に増大させることを示す。 また,共有絡み合った状態と共有ランダム文字列を持つPSQMプロトコルの通信複雑性の指数的差を示す。
  論文  参考訳（メタデータ） (2021-05-15T03:08:01Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。 悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。 我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
  論文  参考訳（メタデータ） (2020-10-15T17:55:31Z)
• Lower Bounds for XOR of Forrelations [7.510385608531827]
  我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。 また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:05:09Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。