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

• arxiv url: http://arxiv.org/abs/2411.03096v2
• Date: Tue, 08 Apr 2025 13:06:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-09 13:25:47.333067
• Title: On the Complexity of Pure-State Consistency of Local Density Matrices
• Title（参考訳）: 局所密度行列の純状態整合性の複雑さについて
• Authors: Jonas Kamminga, Dorian Rudolph,
• Abstract要約: 我々は、Aharanov と Regev [FOCS 2003] の複雑性クラス QMA+ の純粋状態類似体を定義し、PureSuperQMA と呼ぶ。 2-qubit還元密度行列の硬さを証明し、混合N-表現性はQMA完全であることを示す。 我々はこれを、PureCLDMがQMA(2)完全かどうかという長年の未解決問題に対する否定的な答えの証拠とみなす。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: In this work we investigate the computational complexity of the pure consistency of local density matrices (PureCLDM) and pure N-representability (Pure-N-Representability; analog of PureCLDM for bosonic or fermionic systems) problems. In these problems the input is a set of reduced density matrices and the task is to determine whether there exists a global pure state consistent with these reduced density matrices. While mixed CLDM, i.e. where the global state can be mixed, was proven to be 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 QMA(2) and QMA. Our contribution to the understanding of these problems is twofold. Firstly, we define a pure state analogue of the complexity class QMA+ of Aharanov and Regev [FOCS 2003], which we call PureSuperQMA. We prove that both pure-N-Representability and 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-Representability is QMA-complete. Secondly, we improve the upper bound on PureCLDM. Using methods from algebraic geometry, we prove that PureSuperQMA is in PSPACE. Our methods, and the PSPACE upper bound, are also valid for PureCLDM with exponential or even perfect precision, hence precisePureCLDM is not preciseQMA(2)=NEXP-complete, unless PSPACE=NEXP. We view this as evidence for a negative answer to the longstanding open question whether PureCLDM is QMA(2)-complete. The techniques we develop for our PSPACE upper bound are quite general. We are able to use them for various applications: from proving PSPACE upper bounds on other quantum problems to giving an efficient parallel (NC) algorithm for (non-convex) quadratically constrained quadratic programs with few constraints.
• Abstract（参考訳）: 本研究では,局所密度行列(Pure-N-Representability,Pure-N-Representability,PureCLDM,Pure-N-Representability,PureCLDM,Pure-N-Re presentability,Pure-N-Representability,Pure-N-Representability)問題の計算複雑性について検討する。 これらの問題では、入力は還元密度行列の集合であり、これらの還元密度行列と整合した大域純状態が存在するかどうかを判断する。 CLDM、すなわち世界状態が混合できる場所はBroadbentとGrilo [JoC 2022]によってQMA完全であることが証明されたが、純粋なバージョンの複雑さについてはほとんど知られていない。 作業前は,QMA(2)とQMAが最高値であった。 これらの問題の理解への私たちの貢献は2つあります。 まず、Aharanov と Regev [FOCS 2003] の複雑性クラス QMA+ の純粋状態類似体を定義する。 我々は,Pure-N-RepresentabilityとPureCLDMの両方が,この新しいクラスに対して完全であることを証明した。 その過程で, 2ビット還元密度行列の硬さを証明することでブロードベントとグリロを補足し, 混合N-表現性はQMA完全であることを示す。 次に,PureCLDMの上限値を改善する。 代数幾何学の手法を用いて、PureSuperQMAがPSPACEに含まれることを示す。 したがってPureCLDMはPSPACE=NEXPでない限り、精度はQMA(2)=NEXP完全ではない。 我々はこれを、PureCLDMがQMA(2)完全かどうかという長年の未解決問題に対する否定的な答えの証拠とみなす。 PSPACE上界の手法は非常に一般的である。 我々は、他の量子問題に対するPSPACE上界の証明から、(非凸)2次制約付き二次プログラムに対して、効率的な並列性(NC)アルゴリズムを与えるまで、様々な用途に利用することができる。

関連論文リスト

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

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

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