論文の概要: 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つの自然量子近似計数問題との間に多項式時間同値性を確立する。
これらの結果は、熱平衡における量子多体系のシミュレーションが、まだ定義されていない、あるいは既知の複雑性クラスで特徴づけられる幅広い計算問題の複雑性を正確に捉えていることを示唆している。
最後に、自由エネルギーを近似するための最先端の古典的および量子的アルゴリズムを要約し、ランタイムとメモリフットプリントを改善する方法を示す。
関連論文リスト
- Optimizing random local Hamiltonians by dissipation [44.99833362998488]
簡単な量子ギブスサンプリングアルゴリズムが最適値の$Omega(frac1k)$-fraction近似を達成することを証明した。
この結果から, 局所スピンおよびフェルミオンモデルに対する低エネルギー状態の発見は量子的に容易であるが, 古典的には非自明であることが示唆された。
論文 参考訳（メタデータ） (2024-11-04T20:21:16Z) - Solving Free Fermion Problems on a Quantum Computer [0.0]
指数関数的に改善されたポリログ$(N)$コストで量子アルゴリズムによって解くことができる、相互作用しないフェルミオン問題をいくつか提示する。
シミュレーションアルゴリズムは,自由なボソンシステムを含む他の有望な対象に一般化可能であることを示す。
論文 参考訳（メタデータ） (2024-09-06T18:25:03Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
NPにおける制約満足度問題の特徴は近似硬度であり、最悪の場合、十分な品質の近似解を見つけることは指数関数的に困難である。
ハミルトニアン時間進化に基づくアルゴリズムでは、原型的にハードなMAX-3-XORSAT問題クラスを通してこの問題を探索する。
近似系におけるランダムなハイパーグラフに対して、エネルギーを$E = N_mathrmunsat-N_mathrmsat$と定義すれば、スペクトルフィルタリングされた量子最適化は$E leq q_mで状態を返す。
論文 参考訳（メタデータ） (2023-12-11T04:15:55Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。