論文の概要: Complexity Classification of Product State Problems for Local Hamiltonians

• arxiv url: http://arxiv.org/abs/2401.06725v1
• Date: Fri, 12 Jan 2024 17:51:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-15 18:46:07.721831
• Title: Complexity Classification of Product State Problems for Local Hamiltonians
• Title（参考訳）: 局所ハミルトニアンにおける製品状態問題の複雑度分類
• Authors: John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang and Justin Yirka
• Abstract要約: 我々は、許容される2-量子相互作用の任意の固定集合によって定義されるハミルトン多様体の最小エネルギー積状態を見つける複雑さを分類する。 積状態の最小エネルギーを推定することは、全ての許容相互作用が 1-局所であり、NP-完全でない場合に限る。
• 参考スコア（独自算出の注目度）: 1.0124625066746595
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Product states, unentangled tensor products of single qubits, are a ubiquitous ansatz in quantum computation, including for state-of-the-art Hamiltonian approximation algorithms. A natural question is whether we should expect to efficiently solve product state problems on any interesting families of Hamiltonians. We completely classify the complexity of finding minimum-energy product states for Hamiltonians defined by any fixed set of allowed 2-qubit interactions. Our results follow a line of work classifying the complexity of solving Hamiltonian problems and classical constraint satisfaction problems based on the allowed constraints. We prove that estimating the minimum energy of a product state is in P if and only if all allowed interactions are 1-local, and NP-complete otherwise. Equivalently, any family of non-trivial two-body interactions generates Hamiltonians with NP-complete product-state problems. Our hardness constructions only require coupling strengths of constant magnitude. A crucial component of our proofs is a collection of hardness results for a new variant of the Vector Max-Cut problem, which should be of independent interest. Our definition involves sums of distances rather than squared distances and allows linear stretches. A corollary of our classification is a new proof that optimizing product states in the Quantum Max-Cut model (the quantum Heisenberg model) is NP-complete.
• Abstract（参考訳）: 積状態(英: product states, unentangled tensor products of single qubits)は、最先端のハミルトニアン近似アルゴリズムを含む量子計算におけるユビキタスアンサッツである。 自然の疑問は、ハミルトンの興味深いファミリーの製品状態の問題を効率的に解決するかどうかである。 許容される2量子ビット相互作用の任意の固定集合によって定義されるハミルトニアンの最小エネルギー積状態を見つける複雑さを完全に分類する。 その結果、ハミルトン問題を解く複雑さと、許容される制約に基づいて古典的な制約満足度問題を分類した。 積状態の最小エネルギーを推定することは、全ての許容相互作用が 1-局所であり、NP-完全でない場合に限る。 同様に、非自明な2体相互作用の族は、NP完全積状態問題を持つハミルトニアンを生成する。 我々の硬さ構造は、一定の大きさの結合強度しか必要としない。 我々の証明の重要な構成要素は、ベクトルマックス・カット問題の新しい変種に対する硬度結果の収集である。 我々の定義は、二乗距離よりも距離の和を含み、直線的なストレッチを可能にする。 我々の分類は、量子マックスカットモデル(量子ハイゼンベルクモデル)における積状態の最適化がnp完全であることを示す新しい証明である。

関連論文リスト

• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。 この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
  論文  参考訳（メタデータ） (2024-11-04T20:21:16Z)
• Quasi-quantum states and the quasi-quantum PCP theorem [0.21485350418225244]
  準量子状態上の$k$-局所ハミルトニアンを解くことは、古典的な$k$-局所CSP上の代入の分布を最適化することと同値であることを示す。 我々の主な結果は、準量子状態上の$k$-局所ハミルトニアンに対するPCP定理である。
  論文  参考訳（メタデータ） (2024-10-17T13:43:18Z)
• Coherence generation with Hamiltonians [44.99833362998488]
  我々は、ユニタリ進化を通して量子コヒーレンスを生成する方法を探究する。 この量は、ハミルトニアンによって達成できるコヒーレンスの最大微分として定義される。 我々は、ハミルトニアンによって誘導される最大のコヒーレンス微分につながる量子状態を特定する。
  論文  参考訳（メタデータ） (2024-02-27T15:06:40Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  量子Max-$d$-Cut問題(Quantum Max-$d$-Cut problem)は、プロジェクターに付随する期待エネルギーを、全ての局所相互作用上の2つの$d$-dimensional quditsの非対称部分空間に最大化する量子状態を見つけることである。 我々は,非自明な性能保証を実現するために,有界な純度を持つ混合状態の積状態解を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-09-19T22:53:17Z)
• On The Study Of Partial Qubit Hamiltonian For Efficient Molecular Simulation Using Variational Quantum Eigensolvers [0.0]
  簡単な分子の部分量子ハミルトニアンから情報を抽出し、より効率的な変分量子固有解法を設計するための新しいアプローチを提案する。 この研究の結果は、量子コンピューティングの分野における潜在的な進歩と、量子化学におけるその実装を実証する可能性を持っている。
  論文  参考訳（メタデータ） (2023-08-24T03:25:05Z)
• Extension of exactly-solvable Hamiltonians using symmetries of Lie algebras [0.0]
  我々は、モデストサイズのリー代数を構成する作用素の線型結合がリー代数対称性の行列式によって置換可能であることを示す。 新しい可解ハミルトニアン類は、対称性の中間回路の測定結果に依存するゲートを持つ量子回路を用いて効率的に測定することができる。
  論文  参考訳（メタデータ） (2023-05-29T17:19:56Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。 本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。 位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
  論文  参考訳（メタデータ） (2023-02-07T10:57:36Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians [0.15229257192293202]
  量子局所ハミルトニアンの基底状態エネルギーと自由エネルギーは、量子多体物理学の基本的な量である。 我々はQuantum $k$-Local Hamiltonians の族において、これらの量に対する古典的で付加的な積-状態近似を求める新しい手法を開発した。
  論文  参考訳（メタデータ） (2022-10-17T00:55:35Z)
• Simultaneous Stoquasticity [0.0]
  確率ハミルトニアンは、局所ハミルトニアン問題の計算複雑性において重要な役割を果たしている。 2つ以上のハミルトニアンがユニタリ変換によって同時に確率的になるかどうかという問題に対処する。
  論文  参考訳（メタデータ） (2022-02-17T19:08:30Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)

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

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