論文の概要: Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
- arxiv url: http://arxiv.org/abs/2410.21833v1
- Date: Tue, 29 Oct 2024 07:56:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-30 13:38:55.288061
- Title: Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
- Title（参考訳）: 局所ハミルトニアンの基底状態エネルギーの定数近似のための古典的アルゴリズム
- Authors: François Le Gall,
- Abstract要約: 我々は、任意の$k$局所ハミルトニアンが$n$ qubitsで作用する基底状態エネルギーの近似を計算する古典的アルゴリズムを構築する。
基底状態エネルギーの定数近似が古典的に$mathrmpolyleft (1/chi,nright)$ time と $mathrmpoly(n)$ space で計算可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.39886149789339326
- License:
- Abstract: We construct classical algorithms computing an approximation of the ground state energy of an arbitrary $k$-local Hamiltonian acting on $n$ qubits. We first consider the setting where a good ``guiding state'' is available, which is the main setting where quantum algorithms are expected to achieve an exponential speedup over classical methods. We show that a constant approximation of the ground state energy can be computed classically in $\mathrm{poly}\left(1/\chi,n\right)$ time and $\mathrm{poly}(n)$ space, where $\chi$ denotes the overlap between the guiding state and the ground state (as in prior works in dequantization, we assume sample-and-query access to the guiding state). This gives a significant improvement over the recent classical algorithm by Gharibian and Le Gall (SICOMP 2023), and matches (up a to polynomial overhead) both the time and space complexities of quantum algorithms for constant approximation of the ground state energy. We also obtain classical algorithms for higher-precision approximation. For the setting where no guided state is given (i.e., the standard version of the local Hamiltonian problem), we obtain a classical algorithm computing a constant approximation of the ground state energy in $2^{O(n)}$ time and $\mathrm{poly}(n)$ space. To our knowledge, before this work it was unknown how to classically achieve these bounds simultaneously, even for constant approximation. We also discuss complexity-theoretic aspects of our results and their implications for the quantum PCP conjecture.
- Abstract（参考訳）: 我々は、任意の$k$局所ハミルトニアンが$n$ qubitsで作用する基底状態エネルギーの近似を計算する古典的アルゴリズムを構築する。
量子アルゴリズムが古典的手法よりも指数的なスピードアップを達成することが期待される主要な設定である。
基底状態エネルギーの定数近似が古典的には $\mathrm{poly}\left(1/\chi,n\right)$ time と $\mathrm{poly}(n)$ space で計算可能であることを示す。
これにより、Gharibian と Le Gall による最近の古典的アルゴリズム (SICOMP 2023) よりも大幅に改善され、基底状態エネルギーの定数近似のための量子アルゴリズムの時間と空間の複雑さを(多項式のオーバーヘッドまで)一致させる。
また、高精度近似のための古典的アルゴリズムも取得する。
誘導状態が与えられない場合(例えば、局所ハミルトン問題の標準版)、基底状態エネルギーの定数近似を時間と$\mathrm{poly}(n)$空間で計算する古典的アルゴリズムを得る。
私たちの知る限り、この研究の前には、定数近似でさえも、これらの境界を古典的に同時に達成する方法が分からなかった。
また、この結果の複雑性理論的な側面と、量子PCP予想へのその影響についても論じる。
関連論文リスト
- 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) - Beating Grover search for low-energy estimation and state preparation [0.23034630097498876]
多体ハミルトニアンの基底状態エネルギーの推定は、量子物理学の多くの分野において中心的な課題である。
この研究において、量子アルゴリズムは、任意の$k$ボディハミルトン$H$を与えられた場合、基底状態エネルギーの見積もりを計算する。
論文 参考訳（メタデータ） (2024-07-03T12:47:06Z) - Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
量子多体物理学における基本的な問題は、局所ハミルトニアンの基底状態を見つけることである。
基底状態特性を学習するためのシステムサイズ$n$とは無関係に,一定のサンプル複雑性を実現する2つのアプローチを導入する。
論文 参考訳（メタデータ） (2024-05-28T18:00:32Z) - A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
我々は、ハミルトン群の基底状態を解決するための量子アルゴリズムを与える。
我々のアルゴリズムに現れた指数的スピードアップのメカニズムは、オープン量子系における散逸に由来する。
論文 参考訳（メタデータ） (2024-01-25T05:01:02Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - 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) - Sparse random Hamiltonians are quantumly easy [105.6788971265845]
量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。
本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。
位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
論文 参考訳（メタデータ） (2023-02-07T10:57:36Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian
Problems [3.553493344868414]
k-局所ハミルトン問題は古典的制約満足問題(k-CSP)の一般化である
極大絡み合いのインスタンスである厳密な二次インスタンスに対しては、古典的な 0.764 時間 0.764 近似を提供する。
これらは近似するのが最も難しい例であると推測する。
我々の研究は、最近開発されたCSPの古典近似解析技術を採用しており、量子情報科学者と古典計算機科学者の両方にアクセスできることを意図している。
論文 参考訳（メタデータ） (2020-12-22T20:41:34Z) - Quantum Assisted Eigensolver [0.0]
本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。
アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
論文 参考訳（メタデータ） (2020-09-23T08:33:18Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。