論文の概要: On the Complexity of Pure-State Consistency of Local Density Matrices

• arxiv url: http://arxiv.org/abs/2411.03096v1
• Date: Tue, 05 Nov 2024 13:43:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-06 14:58:43.981162
• Title: On the Complexity of Pure-State Consistency of Local Density Matrices
• Title（参考訳）: 局所密度行列の純状態整合性の複雑さについて
• Authors: Jonas Kamminga, Dorian Rudolph,
• Abstract要約: 局所密度行列(mathsfPureCLDM$)および純$N$-representability(mathsfPure$-$N$-$mathsfRepresentability$)問題の純粋整合性について検討する。 この新しいクラスには$mathsfPure$-$N$-$mathsfRepresentability$と$mathsfPureCLDM$の両方が完了していることを証明します。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: In this work we investigate the computational complexity of the pure consistency of local density matrices ($\mathsf{PureCLDM}$) and pure $N$-representability ($\mathsf{Pure}$-$N$-$\mathsf{Representability}$) problems. In these problems the input is a set of reduced density matrices and the task is to determine whether there exists a global \emph{pure} state consistent with these reduced density matrices. While mixed $\mathsf{CLDM}$, i.e. where the global state can be mixed, was proven to be $\mathsf{QMA}$-complete by Broadbent and Grilo [JoC 2022], almost nothing was known about the complexity of the pure version. Before our work the best upper and lower bounds were $\mathsf{QMA}(2)$ and $\mathsf{QMA}$. Our contribution to the understanding of these problems is twofold. Firstly, we define a pure state analogue of the complexity class $\mathsf{QMA}^+$ of Aharanov and Regev [FOCS 2003], which we call $\mathsf{PureSuperQMA}$. We prove that both $\mathsf{Pure}$-$N$-$\mathsf{Representability}$ and $\mathsf{PureCLDM}$ are complete for this new class. Along the way we supplement Broadbent and Grilo by proving hardness for 2-qubit reduced density matrices and showing that mixed $N$-$\mathsf{Representability}$ is $\mathsf{QMA}$ complete. Secondly, we improve the upper bound on $\mathsf{PureCLDM}$. Using methods from algebraic geometry, we prove that $\mathsf{PureSuperQMA} \subseteq \mathsf{PSPACE}$. Our methods, and the $\mathsf{PSPACE}$ upper bound, are also valid for $\mathsf{PureCLDM}$ with exponential or even perfect precision, hence $\mathsf{precisePureCLDM}$ is not $\mathsf{preciseQMA}(2) = \mathsf{NEXP}$-complete, unless $\mathsf{PSPACE} = \mathsf{NEXP}$. We view this as evidence for a negative answer to the longstanding open question whether $\mathsf{PureCLDM}$ is $\mathsf{QMA}(2)$-complete.
• Abstract（参考訳）: 本研究では,局所密度行列の純粋整合性 (\mathsf{PureCLDM}$) と純$N$-representability (\mathsf{Pure}$-$N$-$\mathsf{Representability}$) の計算複雑性について検討する。 これらの問題において、入力は縮密度行列の集合であり、この縮密度行列と整合した大域的な 'emph{pure} 状態が存在するかどうかを判断する。 混合$\mathsf{CLDM}$、すなわち、大域的な状態が混合できる場合は、Broadbent と Grilo [JoC 2022] によって$\mathsf{QMA}$-completeであることが証明されたが、純粋なバージョンの複雑さについてはほとんど知られていない。 我々の研究の前には、最上位と下位の境界は$\mathsf{QMA}(2)$と$\mathsf{QMA}$であった。 これらの問題の理解への私たちの貢献は2つあります。 まず、複雑性クラス $\mathsf{QMA}^+$ of Aharanov and Regev [FOCS 2003] の純粋状態類似体を定義し、$\mathsf{PureSuperQMA}$ と呼ぶ。 この新しいクラスに対して、$\mathsf{Pure}$-$N$-$\mathsf{Representability}$と$\mathsf{PureCLDM}$の両方が完備であることを示す。 その過程で、Broadbent と Grilo を補うために、2-量子還元密度行列の硬さを証明し、混合$N$-$\mathsf{Representability}$が$\mathsf{QMA}$ completeであることを示す。 次に、$\mathsf{PureCLDM}$の上限を改善する。 代数幾何学の手法を用いて、$\mathsf{PureSuperQMA} \subseteq \mathsf{PSPACE}$を証明した。 したがって、$\mathsf{precisePureCLDM}$は$\mathsf{preciseQMA}(2) = \mathsf{NEXP}$-完全ではなく、$\mathsf{PSPACE} = \mathsf{NEXP}$である。 我々はこれを、$\mathsf{PureCLDM}$が$\mathsf{QMA}(2)$-完全であるかどうかという長い開問題に対する否定的な答えの証拠とみなす。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Quantum Sabotage Complexity [0.7812210699650152]
  ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。 f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
  論文  参考訳（メタデータ） (2024-08-22T17:57:58Z)
• Locality Regularized Reconstruction: Structured Sparsity and Delaunay Triangulations [7.148312060227714]
  線形表現学習は、その概念的単純さと、圧縮、分類、特徴抽出といったタスクにおける経験的有用性から、広く研究されている。 本研究では、正則化最小二乗回帰問題を解くことにより、$mathbfy$の局所再構成を形成する$mathbfw$を求める。 すべてのレベルの正則化と、$mathbfX$ の列が独自のデラウネー三角形を持つという穏やかな条件の下では、最適係数の非零成分の数は$d+1$ で上界となることを証明している。
  論文  参考訳（メタデータ） (2024-05-01T19:56:52Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs [4.130591018565202]
  Learning Errors With Errors(mathsfLWE$)問題は$(mathbfAmathbfs+mathbfe$)という形式の入力から$mathbfs$を見つけるように要求する 私たちは$mathsfLWE$の解決ではなく、インスタンスをサンプリングするタスクに注力しています。 我々の主な成果は、よく分散された$mathsfLWE$インスタンスをサンプリングする量子時間アルゴリズムである。
  論文  参考訳（メタデータ） (2024-01-08T10:55:41Z)
• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• StoqMA meets distribution testing [0.0]
  We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits。 いずれの変種も$mathsfStoqMA$は、任意の無作為な乱数ビットと完全音性を持たず、$mathsfNP$に含まれることを示す。 我々の結果は、$mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06]という階層構造を崩壊させる一歩を踏み出した。
  論文  参考訳（メタデータ） (2020-11-11T12:30:42Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)

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

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