論文の概要: 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-28 17:07:44.620222
• 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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)$-完全であるかどうかという長い開問題に対する否定的な答えの証拠とみなす。

関連論文リスト

• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  本稿では,QUBO行列におけるテクステミシンメトリの概念を紹介する。 提案アルゴリズムは結合数と回路深さを最大45%削減することを示した。
  論文  参考訳（メタデータ） (2024-12-18T12:05:18Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Enhanced Krylov Methods for Molecular Hamiltonians via Tensor Hypercontraction [2.2022550150705804]
  本稿では, Ab 分子ハミルトニアンに対するテンソルハイパーコントラクション (THC) 形式に基づく行列積演算子 (MPO) の構成について述べる。 このようなMPO構造により、クリロフ部分空間法のメモリ要求とコストスケーリングが劇的に低下する。
  論文  参考訳（メタデータ） (2024-09-19T12:34:06Z)
• 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)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• 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)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement [0.0]
  サビッチの定理は、NPSPACE計算はPSPACEでシミュレートできると述べている。 SQCMASPACE=NEXP のように、サビッチの定理の量子アナログが成り立たないことを示す。 SQCMASPACE を[Chailloux, Sattath, 2012] のスパース分離ハミルトン問題に組み込む方法を示す (QMA(2)-complete for 1/poly promise gap)。
  論文  参考訳（メタデータ） (2022-06-10T17:35:10Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Non-Markovian Stochastic Schr\"odinger Equation: Matrix Product State Approach to the Hierarchy of Pure States [65.25197248984445]
  開有限温度における非マルコフ力学に対する行列積状態(HOMPS)の階層を導出する。 HOMPSの有効性と効率性はスピン-ボソンモデルと長鎖に対して示され、各部位は構造化された強非マルコフ環境に結合する。
  論文  参考訳（メタデータ） (2021-09-14T01:47:30Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• 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)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  変分量子アルゴリズム (VQA) の中心成分は状態準備回路(英語版)であり、アンザッツ(英語版)または変分形式(英語版)とも呼ばれる。 ここでは、対称性を破るユニタリを組み込んだ「解」を導入することで、このアプローチが必ずしも有利であるとは限らないことを示す。 この研究は、より一般的な対称性を破るアンスの開発に向けた第一歩となり、物理学や化学問題への応用に繋がる。
  論文  参考訳（メタデータ） (2020-08-03T18:00:05Z)
• 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)

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

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