論文の概要: Nonlocality under Computational Assumptions

• arxiv url: http://arxiv.org/abs/2303.02080v2
• Date: Tue, 28 Nov 2023 17:53:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-01 03:59:41.826178
• Title: Nonlocality under Computational Assumptions
• Title（参考訳）: 計算仮定による非局所性
• Authors: Khashayar Barooti, Alexandru Gheorghiu, Grzegorz G{\l}uch, Marc-Olivier Renou
• Abstract要約: 相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。 ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
• 参考スコア（独自算出の注目度）: 51.020610614131186
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nonlocality and its connections to entanglement are fundamental features of quantum mechanics that have found numerous applications in quantum information science. A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations. An important practical consideration is that the runtime of the parties has to be shorter than the time it takes light to travel between them. One way to model this restriction is to assume that the parties are computationally bounded. We therefore initiate the study of nonlocality under computational assumptions and derive the following results: (a) We define the set $\mathsf{NeL}$ (not-efficiently-local) as consisting of all bipartite states whose correlations arising from local measurements cannot be reproduced with shared randomness and \emph{polynomial-time} local operations. (b) Under the assumption that the Learning With Errors problem cannot be solved in \emph{quantum} polynomial-time, we show that $\mathsf{NeL}=\mathsf{ENT}$, where $\mathsf{ENT}$ is the set of \emph{all} bipartite entangled states (pure and mixed). This is in contrast to the standard notion of nonlocality where it is known that some entangled states, e.g. Werner states, are local. In essence, we show that there exist (efficient) local measurements producing correlations that cannot be reproduced through shared randomness and quantum polynomial-time computation. (c) We prove that if $\mathsf{NeL}=\mathsf{ENT}$ unconditionally, then $\mathsf{BQP}\neq\mathsf{PP}$. In other words, the ability to certify all bipartite entangled states against computationally bounded adversaries gives a non-trivial separation of complexity classes. (d) Using (c), we show that a certain natural class of 1-round delegated quantum computation protocols that are sound against $\mathsf{PP}$ provers cannot exist.
• Abstract（参考訳）: 非局所性と絡み合いとのつながりは量子力学の基本的な特徴であり、量子情報科学において多くの応用が見つかっている。 相関の組が非局所であるとは、無作為性を共有し、局所的な操作を行うスペースのような分離されたパーティによって再現できない場合である。 重要な実践的考慮事項は、当事者のランタイムが、その間の移動に光がかかる時間よりも短くなければならないことである。 この制限をモデル化する一つの方法は、当事者が計算的に有界であると仮定することである。 そこで,計算仮定の下での非局所性の研究を開始し,以下の結果を得る。 a) 集合 $\mathsf{nel}$ (非効率的局所的) を、局所的な測定から生じる相関関係を共有ランダム性および \emph{polynomial-time} 局所演算で再現できないすべての二成分状態からなるものと定義する。 b)Learning With Errors が多項式時間で解けないという仮定の下では、$\mathsf{NeL}=\mathsf{ENT}$, where $\mathsf{ENT}$ が 'emph{all} bipartite entangled state (pure and mixed) の集合であることを示す。 これは、例えばヴェルナー状態のような絡み合った状態が局所であることが知られている非局所性の標準的な概念とは対照的である。 本質的に、共有ランダム性や量子多項式時間計算によって再現できない相関関係を生成する(効率的な)局所測定が存在することを示す。 (c)$\mathsf{NeL}=\mathsf{ENT}$が無条件であれば、$\mathsf{BQP}\neq\mathsf{PP}$が証明される。 言い換えれば、計算的に有界な敵に対して全ての二部交絡状態を証明する能力は、複雑性クラスを非自明に分離する。 (d)使用 (c) では,$\mathsf{pp}$ provers に対して可聴な 1 ラウンドデリゲート量子計算プロトコルのある種の自然クラスは存在できないことを示す。

関連論文リスト

• 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)

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

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