論文の概要: Complexity Classification of Product State Problems for Local Hamiltonians
- arxiv url: http://arxiv.org/abs/2401.06725v2
- Date: Mon, 06 Jan 2025 18:38:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-07 17:02:26.178231
- Title: Complexity Classification of Product State Problems for Local Hamiltonians
- Title（参考訳）: 局所ハミルトニアンにおける製品状態問題の複雑度分類
- Authors: John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, Justin Yirka,
- Abstract要約: 我々は、許容される2-量子相互作用の任意の固定集合によって定義されるハミルトン多様体の最小エネルギー積状態を見つける複雑さを分類する。
積状態の最小エネルギーを推定することは、全ての許容相互作用が 1-局所であり、NP-完全でない場合に限る。
- 参考スコア（独自算出の注目度）: 0.94371657253557
- License:
- 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. We similarly give a proof that the original Vector Max-Cut problem is NP-complete in 3 dimensions. This implies that optimizing over product states for Quantum Max-Cut (the quantum Heisenberg model) is NP-complete, even when every term is guaranteed to have positive unit weight.
- Abstract（参考訳）: 単一量子ビットの無絡テンソル積である積状態は、最先端のハミルトン近似アルゴリズムを含む量子計算においてユビキタスなアンザッツである。
自然の疑問は、ハミルトンの興味深いファミリーの製品状態の問題を効率的に解決するかどうかである。
我々は、許容される2-量子相互作用の任意の固定集合によって定義されるハミルトニアンの最小エネルギー積状態を見つける複雑さを、完全に分類する。
本研究は、ハミルトン問題と古典的制約満足度問題を許容された制約に基づいて解くことの複雑さを分類する一連の作業に続くものである。
積状態の最小エネルギーを推定することは、全ての許容相互作用が 1-局所であり、NP-完全でない場合に限る。
同様に、非自明な2体相互作用の族は、NP完全積状態問題を持つハミルトニアンを生成する。
我々の硬さ構造は、一定の大きさの結合強度しか必要としない。
我々の証明の重要な構成要素は、ベクター・マックス・カッツ問題の新しい変種に対する難解な結果の収集である。
我々の定義では、二乗距離よりも距離の和が関係しており、線形展開が可能である。
同様に、元のベクトルMax-Cut問題が3次元で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) - Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture [0.0]
我々は最近定義されたガイドド局所ハミルトン問題における「マーリン化」バージョンについて検討する。
これらの問題には、入力の一部として提供される指針状態はなく、単に存在するという約束が伴うだけである。
誘導状態の両クラスに対する誘導可能な局所ハミルトン問題は、逆多項式の精度設定において$mathsfQCMA$-completeであることを示す。
論文 参考訳（メタデータ） (2023-02-22T19:00:00Z) - 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) - Concentration bounds for quantum states and limitations on the QAOA from
polynomial approximations [17.209060627291315]
i) 浅い量子回路の出力状態、 [DPMRF22] からのオープン質問に答える、 (ii) 射影行列積状態、 [DPMRF22] からのオープン質問に答える、 (iii) 密なハミルトン進化の出力状態、すなわち、$eiota H(p) cdots eiota H(1) |psirangle for any $n$-qubit product state $|psirangle$。
論文 参考訳（メタデータ） (2022-09-06T18:00:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。