論文の概要: On the complexity of quantum partition functions
- arxiv url: http://arxiv.org/abs/2110.15466v2
- Date: Wed, 20 Sep 2023 21:23:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-22 20:35:20.860615
- Title: On the complexity of quantum partition functions
- Title(参考訳): 量子分割関数の複雑性について
- Authors: Sergey Bravyi, Anirban Chowdhury, David Gosset, Pawel Wocjan
- Abstract要約: 局所ハミルトニアンの近似量の計算複雑性について検討する。
$mathrmpoly(n)$ の古典的アルゴリズムは与えられた 2$-局所ハミルトニアンの自由エネルギーを近似する。
- 参考スコア(独自算出の注目度): 2.6937287784482313
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The partition function and free energy of a quantum many-body system
determine its physical properties in thermal equilibrium. Here we study the
computational complexity of approximating these quantities for $n$-qubit local
Hamiltonians. First, we report a classical algorithm with $\mathrm{poly}(n)$
runtime which approximates the free energy of a given $2$-local Hamiltonian
provided that it satisfies a certain denseness condition. Our algorithm
combines the variational characterization of the free energy and convex
relaxation methods. It contributes to a body of work on efficient approximation
algorithms for dense instances of optimization problems which are hard in the
general case, and can be viewed as simultaneously extending existing algorithms
for (a) the ground energy of dense $2$-local Hamiltonians, and (b) the free
energy of dense classical Ising models. Secondly, we establish polynomial-time
equivalence between the problem of approximating the free energy of local
Hamiltonians and three other natural quantum approximate counting problems,
including the problem of approximating the number of witness states accepted by
a QMA verifier. These results suggest that simulation of quantum many-body
systems in thermal equilibrium may precisely capture the complexity of a broad
family of computational problems that has yet to be defined or characterized in
terms of known complexity classes. Finally, we summarize state-of-the-art
classical and quantum algorithms for approximating the free energy and show how
to improve their runtime and memory footprint.
- Abstract(参考訳): 量子多体系の分配関数と自由エネルギーは熱平衡における物理的性質を決定する。
そこで,n$-qubit 局所ハミルトニアンの計算量を近似する計算量について検討する。
まず、与えられた2ドルの局所ハミルトニアンの自由エネルギーを近似する$\mathrm{poly}(n)$ランタイムを持つ古典的なアルゴリズムを報告し、ある密度条件を満たすことを述べる。
本アルゴリズムは自由エネルギーの変動特性と凸緩和法を組み合わせたものである。
これは、一般的な場合では難しい最適化問題の高密度なインスタンスに対する効率的な近似アルゴリズムの体系に寄与し、既存のアルゴリズムを同時に拡張すると見なすことができる。
(a)高密度な2ドル局所ハミルトンの基底エネルギー、そして
(b)高密度古典イジングモデルの自由エネルギー。
次に、局所ハミルトニアンの自由エネルギーを近似する問題と、qma検証者が受け入れる証人状態の数を近似する問題を含む、他の3つの自然量子近似計数問題との間に多項式時間同値性を確立する。
これらの結果は、熱平衡における量子多体系のシミュレーションが、まだ定義されていない、あるいは既知の複雑性クラスで特徴づけられる幅広い計算問題の複雑性を正確に捉えていることを示唆している。
最後に、自由エネルギーを近似するための最先端の古典的および量子的アルゴリズムを要約し、ランタイムとメモリフットプリントを改善する方法を示す。
関連論文リスト
- Dense outputs from quantum simulations [1.8076403084528587]
量子密度出力問題は、時間依存の量子力学から時間累積観測値を評価する過程である。
この問題は量子制御や分光計算などの応用で頻繁に発生する。
我々は、早期および完全フォールトトレラントな量子プラットフォームの両方で動作するように設計されたアルゴリズムを提示する。
論文 参考訳(メタデータ) (2023-07-26T18:16:51Z) - Variational quantum algorithms for scanning the complex spectrum of
non-Hermitian systems [0.0]
量子コンピュータ上で非エルミートハミルトニアンを解くための変分法を提案する。
エネルギーはコスト関数のパラメータとして設定され、全スペクトルを得るために調整することができる。
我々の研究は、近時雑音量子コンピュータ上で変動量子アルゴリズムを用いて非エルミート量子多体系を解くための道筋を示唆している。
論文 参考訳(メタデータ) (2023-05-31T12:50:22Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳(メタデータ) (2023-04-12T18:10:47Z) - Calculating the many-body density of states on a digital quantum
computer [58.720142291102135]
ディジタル量子コンピュータ上で状態の密度を推定する量子アルゴリズムを実装した。
我々は,量子H1-1トラップイオンチップ上での非可積分ハミルトニアン状態の密度を18ビットの制御レジスタに対して推定する。
論文 参考訳(メタデータ) (2023-03-23T17:46:28Z) - Sparse random Hamiltonians are quantumly easy [105.6788971265845]
量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。
本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。
位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
論文 参考訳(メタデータ) (2023-02-07T10:57:36Z) - Hybridized Methods for Quantum Simulation in the Interaction Picture [69.02115180674885]
本研究では,異なるシミュレーション手法をハイブリダイズし,インタラクション・ピクチャー・シミュレーションの性能を向上させるフレームワークを提案する。
これらのハイブリッド化手法の物理的応用は、電気遮断において$log2 Lambda$としてゲート複雑性のスケーリングをもたらす。
力学的な制約を受けるハミルトニアンシミュレーションの一般的な問題に対して、これらの手法は、エネルギーコストを課すために使われるペナルティパラメータ$lambda$とは無関係に、クエリの複雑さをもたらす。
論文 参考訳(メタデータ) (2021-09-07T20:01:22Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。
一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。
幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
論文 参考訳(メタデータ) (2021-04-01T19:06:00Z) - A Hybrid Quantum-Classical Hamiltonian Learning Algorithm [6.90132007891849]
ハミルトン学習は、量子デバイスと量子シミュレータの認定に不可欠である。
本研究では,ハミルトニアン作用素の係数を求めるために,ハイブリッド量子古典ハミルトン学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-03-01T15:15:58Z) - Iterative Quantum Assisted Eigensolver [0.0]
我々は、ハミルトニアン基底状態を近似するハイブリッド量子古典アルゴリズムを提供する。
我々のアルゴリズムは、現在の量子コンピュータに適した方法で、強力なKrylov部分空間法に基づいている。
論文 参考訳(メタデータ) (2020-10-12T12:25:16Z) - Using Quantum Annealers to Calculate Ground State Properties of
Molecules [0.0]
我々は、Isingモデルに基づく量子アニールを用いた分子ハミルトニアンの基底状態を見つけるための2つの異なる方法についてレビューした。
現代のアルゴリズムでは依然として性能が優れており、リソース要求のスケーリングは依然として課題である。
論文 参考訳(メタデータ) (2020-09-22T19:34:01Z) - Variational Monte Carlo calculations of $\mathbf{A\leq 4}$ nuclei with
an artificial neural-network correlator ansatz [62.997667081978825]
光核の基底状態波動関数をモデル化するためのニューラルネットワーク量子状態アンサッツを導入する。
我々は、Aleq 4$核の結合エネルギーと点核密度を、上位のピオンレス実効場理論から生じるものとして計算する。
論文 参考訳(メタデータ) (2020-07-28T14:52:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。