論文の概要: How hard is it to fake entanglement? A complexity theoretic view of
nonlocality and its applications to delegating quantum computation
- arxiv url: http://arxiv.org/abs/2303.02080v1
- Date: Fri, 3 Mar 2023 16:53:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-06 14:00:49.915378
- Title: How hard is it to fake entanglement? A complexity theoretic view of
nonlocality and its applications to delegating quantum computation
- Title（参考訳）: 嘘の絡み合いって どれだけ難しいの?
非局所性の複雑性理論的考察と量子計算のデリゲートへの応用
- Authors: Khashayar Barooti, Grzegorz G{\l}uch, Marc-Olivier Renou
- Abstract要約: すべての絡み合った状態とすべての分離可能な状態とを区別することは可能であることを示す。
量子計算の1ラウンドのデリゲートが存在する場合、$mathttBQP neq mathttPP$。
- 参考スコア（独自算出の注目度）: 4.125187280299247
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Is it possible to operationally distinguish every entangled state from all
separable states? This is a long-standing open question in quantum information.
More concretely, assuming that two non-communicating parties interact
classically with a verifier, can the verifier distinguish the following two
cases: (i) the parties have access to an entangled state, (ii) they have access
to a separable state only (a local hidden variable model). In this work, we
define a computational version of state non-locality, and show that if every
entangled state exhibits such non-locality then $\mathtt{BQP} \neq
\mathtt{PP}$.
Surprisingly, we demonstrate how this result implies that if a one-round
delegation of quantum computation (DQC) exists then $\mathtt{BQP} \neq
\mathtt{PP}$. This gives a necessary complexity-theoretic assumption needed for
the existence of such DQC. Our proof technique essentially builds a framework
that allows one to give stronger lower-bounds for DQC by proving upper-bounds
for the complexity of local-hidden-variable models.
- Abstract（参考訳）: すべての絡み合った状態とすべての分離可能な状態とを運用的に区別することは可能か?
これは量子情報における長年の疑問である。
より具体的には、2つの非コミュニケーション当事者が古典的に検証者と相互作用することを仮定すると、検証者は以下の2つのケースを区別できる。
(i)当事者は、絡み合った国にアクセスすることができる。
(ii) 分離可能な状態のみにアクセスする(ローカルな隠れ変数モデル)。
本研究では、状態非局所性の計算バージョンを定義し、すべての絡み合った状態がそのような非局所性を示すならば、$\mathtt{BQP} \neq \mathtt{PP}$であることを示す。
驚くべきことに、この結果が量子計算(dqc)の1ラウンドのデリゲーションが存在する場合、$\mathtt{bqp} \neq \mathtt{pp}$ であることを示す。
このことは、そのようなDQCの存在に必要な複雑性理論的な仮定を与える。
我々の証明手法は、局所隠れ変数モデルの複雑さに対して上界を証明し、DQCのより強い下界を与えるフレームワークを本質的に構築する。
関連論文リスト
- Learning finitely correlated states: stability of the spectral reconstruction [1.9573380763700716]
鎖上の有限相関な変換不変状態の$t$系のブロックの辺は、$O(t2)$コピーでトレース距離で学習可能であることを示す。
このアルゴリズムは、最小結合次元で制限された最悪の場合において、制御された大きさの限界を推定することのみを必要とする。
論文 参考訳（メタデータ） (2023-12-12T18:47:12Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Maximal gap between local and global distinguishability of bipartite
quantum states [7.605814048051737]
2つの二部分量子状態の判別において、局所的な量子測定(古典的な通信なしで)の有効性について、厳密で近似的な下限を証明した。
論文 参考訳（メタデータ） (2021-10-08T21:40:02Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - Nonlocality of tripartite orthogonal product states [0.0]
我々は$mathbbC2dbigotimesmathbbC2dbigotimesmathbbC2d$に局所的に区別できない部分集合を構築する。
我々はこの手法を任意の三部分量子系に一般化する。
3量子GHZ状態は、上記の状態のそれぞれを区別する資源として十分であることを示す。
論文 参考訳（メタデータ） (2020-11-07T18:46:24Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - Testing the Structure of Multipartite Entanglement with Hardy's
Nonlocality [0.6091702876917279]
一般$N$-qubit GHZ状態と一般$N$-qubit W状態の2つの重要な異なる挙動を示す。
我々は一般の$N$-qubit W状態に対する直観を得るアプローチを一般化し、N$の最大違反確率減衰が一般の$N$-qubit GHZ状態よりも指数関数的に遅いことを明らかにした。
論文 参考訳（メタデータ） (2020-01-07T16:05:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。