論文の概要: Hamiltonian simulation for low-energy states with optimal time dependence

• arxiv url: http://arxiv.org/abs/2404.03644v2
• Date: Wed, 14 Aug 2024 04:17:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-15 17:56:45.959893
• Title: Hamiltonian simulation for low-energy states with optimal time dependence
• Title（参考訳）: 最適時間依存性を持つ低エネルギー状態に対するハミルトンシミュレーション
• Authors: Alexander Zlokapa, Rolando D. Somma,
• Abstract要約: 低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。 我々は,$O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$クエリを,任意の$Gamma$に対するブロックエンコーディングに使用する量子アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 45.02537589779136
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. Assuming access to a block-encoding of $H'=(H-E)/\lambda$ for some $E \in \mathbb R$, the goal is to implement an $\epsilon$-approximation to $e^{-itH}$ when the initial state is confined to the subspace corresponding to eigenvalues $[-1, -1+\Delta/\lambda]$ of $H'$. We present a quantum algorithm that uses $O(t\sqrt{\lambda\Gamma} + \sqrt{\lambda/\Gamma}\log(1/\epsilon))$ queries to the block-encoding for any $\Gamma$ such that $\Delta \leq \Gamma \leq \lambda$. When $\log(1/\epsilon) = o(t\lambda)$ and $\Delta/\lambda = o(1)$, this result improves over generic methods with query complexity $\Omega(t\lambda)$. Our quantum algorithm leverages spectral gap amplification and the quantum singular value transform. Using standard access models for $H$, we show that the ability to efficiently block-encode $H'$ is equivalent to $H$ being what we refer to as a "gap-amplifiable" Hamiltonian. This includes physically relevant examples such as frustration-free systems, and it encompasses all previously considered settings of low-energy simulation algorithms. We also provide lower bounds for low-energy simulation. In the worst case, we show that the low-energy condition cannot be used to improve the runtime of Hamiltonian simulation. For gap-amplifiable Hamiltonians, we prove that our algorithm is tight in the query model with respect to $t$, $\Delta$, and $\lambda$. In the practically relevant regime where $\log (1/\epsilon) = o(t\Delta)$ and $\Delta/\lambda = o(1)$, we also prove a matching lower bound in gate complexity (up to log factors). To establish the query lower bounds, we consider $\mathrm{PARITY}\circ\mathrm{OR}$ and degree bounds on trigonometric polynomials. To establish the lower bound on gate complexity, we use a circuit-to-Hamiltonian reduction acting on a low-energy state.
• Abstract（参考訳）: 低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。 ブロックエンコーディングを$H'=(H-E)/\lambda$ for some $E \in \mathbb R$と仮定すると、初期状態が固有値$[-1, -1+\Delta/\lambda]$のサブスペースに制限されたときに、$\epsilon$-approximation to $e^{-itH}$を実装することが目標である。 我々は、$O(t\sqrt{\lambda\Gamma} + \sqrt{\lambda/\Gamma}\log(1/\epsilon))$のブロックエンコーディングに対して$\Gamma$を$\Delta \leq \Gamma \lambda$とする量子アルゴリズムを提案する。 $\log(1/\epsilon) = o(t\lambda)$ と $\Delta/\lambda = o(1)$ とすると、クエリ複雑性を持つジェネリックメソッドよりも改善される。 我々の量子アルゴリズムはスペクトルギャップ増幅と量子特異値変換を利用する。 H$の標準的なアクセスモデルを用いて、$H'$を効率的にブロックエンコードする能力は、"ギャップアンプリケート"ハミルトニアンと呼ばれるものと同じであることを示す。 これにはフラストレーションのないシステムのような物理的に関係のある例が含まれており、これまで考慮されていた低エネルギーシミュレーションアルゴリズムのすべての設定を含んでいる。 また、低エネルギーシミュレーションのための下限も提供する。 最悪の場合、ハミルトニアンシミュレーションのランタイムを改善するために低エネルギー状態は利用できない。 ギャップを増幅するハミルトニアンに対しては、我々のアルゴリズムが$t$, $\Delta$, $\lambda$に関するクエリモデルに密着していることを証明する。 例えば、$\log (1/\epsilon) = o(t\Delta)$ と $\Delta/\lambda = o(1)$ は、ゲートの複雑さ(ログファクタまで)が一致することを証明する。 クエリの下界を確立するために、$\mathrm{PARITY}\circ\mathrm{OR}$ および三角多項式上の次数境界を考える。 ゲート複雑性の低い境界を確立するために、低エネルギー状態に作用するサーキット・ト・ハミルトニアン還元を用いる。

関連論文リスト

• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Learning many-body Hamiltonians with Heisenberg-limited scaling [3.460138063155115]
  N$-qubit 局所ハミルトニアンの相互作用を学習するためのハイゼンベルク限界を達成するアルゴリズムを提案する。 総進化時間$mathcalO(epsilon-1)$の後に、提案アルゴリズムは高い確率で$N$-qubit Hamiltonianのパラメータを$epsilon$-errorに効率的に推定することができる。
  論文  参考訳（メタデータ） (2022-10-06T16:30:51Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。 我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
  論文  参考訳（メタデータ） (2021-12-15T21:44:05Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。 このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-09-09T18:00:09Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians [0.0]
  本稿では、乗算制御されたユニタリな$textSelect(H) equiv sum_ellを実装する量子回路を構築するためのフレームワークを提案する。 $textSelect(H)$は、いくつかの量子アルゴリズムの主要なサブルーチンの1つである。
  論文  参考訳（メタデータ） (2020-04-08T18:00:04Z)
• Fast digital methods for adiabatic state preparation [0.0]
  ゲート型量子コンピュータにおいて,逆誤差の複雑多元対数を伴う断熱状態生成のための量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-08T18:00:01Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。 格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。 NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
  論文  参考訳（メタデータ） (2020-02-25T19:18:36Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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