論文の概要: Hardness of approximation for ground state problems

• arxiv url: http://arxiv.org/abs/2411.04874v1
• Date: Thu, 07 Nov 2024 17:11:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-08 19:37:23.559740
• Title: Hardness of approximation for ground state problems
• Title（参考訳）: 地盤問題に対する近似の硬さ
• Authors: Sevag Gharibian, Carsten Hecht,
• Abstract要約: 基底状態のエネルギーに焦点をあてるのではなく、基底空間の計算特性を考えると、基底空間の計算特性のQCMA硬さを示すことができる。 本研究は,(1)基底状態接続問題 (GSCON) を近似するために N(1-eps) の範囲内でQCMA完全であり,(2) 局所ハミルトン基底状態の絡み合い量(GSE)を推定するために,同じ比内でQCMA完全であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: After nearly two decades of research, the question of a quantum PCP theorem for quantum Constraint Satisfaction Problems (CSPs) remains wide open. As a result, proving QMA-hardness of approximation for ground state energy estimation has remained elusive. Recently, it was shown [Bittel, Gharibian, Kliesch, CCC 2023] that a natural problem involving variational quantum circuits is QCMA-hard to approximate within ratio N^(1-eps) for any eps > 0 and N the input size. Unfortunately, this problem was not related to quantum CSPs, leaving the question of hardness of approximation for quantum CSPs open. In this work, we show that if instead of focusing on ground state energies, one considers computing properties of the ground space, QCMA-hardness of computing ground space properties can be shown. In particular, we show that it is (1) QCMA-complete within ratio N^(1-eps) to approximate the Ground State Connectivity problem (GSCON), and (2) QCMA-hard within the same ratio to estimate the amount of entanglement of a local Hamiltonian's ground state, denoted Ground State Entanglement (GSE). As a bonus, a simplification of our construction yields NP-completeness of approximation for a natural k-SAT reconfiguration problem, to be contrasted with the recent PCP-based PSPACE hardness of approximation results for a different definition of k-SAT reconfiguration [Karthik C.S. and Manurangsi, 2023, and Hirahara, Ohsaka, STOC 2024].
• Abstract（参考訳）: 20年近くにわたる研究の末、量子制約満足度問題(CSP)に対する量子PCP定理の問題は広く議論されている。 その結果、基底状態エネルギー推定のための近似のQMA硬さの証明は、まだ解明されていない。 近年、[Bittel, Gharibian, Kliesch, CCC 2023] は、変動量子回路を含む自然問題は、入力サイズが eps > 0 と N の比 N^(1-eps) で近似するQCMAハードであることが示されている。 残念なことに、この問題は量子 CSP とは無関係であり、量子 CSP の近似の硬さの問題が解き放たれた。 本研究では、基底状態のエネルギーに焦点をあてるのではなく、基底空間の計算特性を考えると、基底空間の計算特性のQCMA硬さを示すことができることを示す。 特に,(1)基底状態接続問題 (GSCON) を近似するために N^(1-eps) 内において QCMA 完全であり,(2) 局所ハミルトン基底状態の絡み合い量(GSE)を推定するために同じ比内で QCMA 完全であることを示す。 ここでは,k-SAT再構成の異なる定義に対するPCPベースのPSPACE計算結果との対比として,自然k-SAT再構成問題に対する近似のNP完全性が得られる(Karthik C.S. and Manurangsi, 2023, andhirahara, Ohsaka, STOC 2024]。

関連論文リスト

• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation [39.20075231137991]
  ハミルトンスペクトル測度の累積分布関数(CDF)の計算に対処する。 本稿では,CDFの反射点を識別する信号処理手法を提案する。 低結合次元のTruncated density-matrix renormalization group (DMRG) 初期状態を用いた26量子完全連結ハイゼンベルク模型の数値実験を行った。
  論文  参考訳（メタデータ） (2024-05-06T18:00:03Z)
• Arbitrary Ground State Observables from Quantum Computed Moments [0.0]
  我々は、量子系の任意の基底状態観測可能量を推定するために量子計算モーメント(QCM)法を拡張した。 ハイゼンベルクモデルの基底状態磁化とスピンスピン相関を決定するためにQCMを用いた予備的な結果を示す。
  論文  参考訳（メタデータ） (2023-12-12T04:29:43Z)
• ADAPT-QSCI: Adaptive Construction of Input State for Quantum-Selected Configuration Interaction [0.0]
  量子多体ハミルトンの基底状態とそのエネルギーを計算するための量子古典ハイブリッドアルゴリズムを提案する。 提案手法はtextitADAPT-QSCI と呼ばれ,小分子に対して正確な基底状態エネルギーが得られることを示す。
  論文  参考訳（メタデータ） (2023-11-02T09:15:50Z)
• On the feasibility of performing quantum chemistry calculations on quantum computers [0.0]
  分子の基底状態を見つけるための2つの主要な量子アプローチを評価するための2つの基準を提案する。 最初の基準は変分量子固有解法(VQE)アルゴリズムに適用される。 第2の基準は量子位相推定(QPE)アルゴリズムに適用される。
  論文  参考訳（メタデータ） (2023-06-05T06:41:22Z)
• Many-Body Excited States with a Contracted Quantum Eigensolver [0.0]
  我々は、収縮量子固有解法(ES-CQE)に基づく励起状態アプローチを開発する。 ES-CQEは,強い電子相関と弱い電子相関の領域を網羅し,ほとんどの状態においてほぼ正確な精度を示す。
  論文  参考訳（メタデータ） (2023-05-16T17:53:07Z)
• Quantum Eigenvector Continuation for Chemistry Applications [57.70351255180495]
  我々は、既に計算済みの基底状態を利用することで、相当量の(量子)計算作業を省くことができることを示す。 いずれの場合も、比較的少数の基底状態を用いてPSSを捕捉できることが示される。
  論文  参考訳（メタデータ） (2023-04-28T19:22:58Z)
• Simulations of Frustrated Ising Hamiltonians with Quantum Approximate Optimization [0.0879626117219674]
  本稿では、量子近似最適化アルゴリズム(QAOA)を用いて、物質基底状態を作成するための代替手法について検討する。 正方形, シャストリー・サザーランド, 三角形格子の単位セル上の古典的イジングスピンモデルについて検討した。 トラップイオン量子コンピュータ上での計算のアプローチを実証し、理想的な理論値に近い確率でShastry-Sutherland単位セルの各基底状態の回復に成功した。
  論文  参考訳（メタデータ） (2022-06-10T20:25:40Z)
• Quantum Davidson Algorithm for Excited States [42.666709382892265]
  基底状態と励起状態の両方に対処するために量子クリロフ部分空間(QKS)法を導入する。 固有状態の残余を使ってクリロフ部分空間を拡大し、コンパクトな部分空間を定式化し、正確な解と密接に一致させる。 量子シミュレータを用いて、様々なシステムの励起状態特性を探索するために、新しいQDavidsonアルゴリズムを用いる。
  論文  参考訳（メタデータ） (2022-04-22T15:03:03Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• A Quantum Optimal Control Problem with State Constrained Preserving Coherence [68.8204255655161]
  非単体脱コヒーレンスチャネルを特徴とするマルコフ脱コヒーレンスを受ける3レベル$Lambda$型原子を考える。 我々は、デコヒーレンスレベルが予め定義された境界内にある状態制約で量子最適制御問題を定式化する。
  論文  参考訳（メタデータ） (2022-03-24T21:31:34Z)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  量子化学と材料は、量子コンピューティングの最も有望な応用の1つである。 これらの領域における産業関連問題とそれを解決する量子アルゴリズムとの整合性については、まだ多くの研究が続けられている。
  論文  参考訳（メタデータ） (2022-03-14T16:51:36Z)

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

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