論文の概要: On the complexity of implementing Trotter steps
- arxiv url: http://arxiv.org/abs/2211.09133v3
- Date: Thu, 11 May 2023 19:09:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-15 16:13:07.613571
- Title: On the complexity of implementing Trotter steps
- Title（参考訳）: トロッターステップの実装の複雑さについて
- Authors: Guang Hao Low, Yuan Su, Yu Tong, Minh C. Tran
- Abstract要約: 我々は,複雑性をサブ線形とした高速なトロッターステップを実現する手法を開発した。
また、ハミルトン係数の特定のブロックが低いとき、より高速なトロッターステップを実現する。
以上の結果から, ゲートの複雑度が低いトロッター合成ステップを実装する上で, ハミルトン構造特性を必要かつ十分なものにすることが示唆された。
- 参考スコア（独自算出の注目度）: 2.1369834525800138
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum dynamics can be simulated on a quantum computer by exponentiating
elementary terms from the Hamiltonian in a sequential manner. However, such an
implementation of Trotter steps has gate complexity depending on the total
Hamiltonian term number, comparing unfavorably to algorithms using more
advanced techniques. We develop methods to perform faster Trotter steps with
complexity sublinear in the number of terms. We achieve this for a class of
Hamiltonians whose interaction strength decays with distance according to power
law. Our methods include one based on a recursive block encoding and one based
on an average-cost simulation, overcoming the normalization-factor barrier of
these advanced quantum simulation techniques. We also realize faster Trotter
steps when certain blocks of Hamiltonian coefficients have low rank. Combining
with a tighter error analysis, we show that it suffices to use
$\left(\eta^{1/3}n^{1/3}+\frac{n^{2/3}}{\eta^{2/3}}\right)n^{1+o(1)}$ gates to
simulate uniform electron gas with $n$ spin orbitals and $\eta$ electrons in
second quantization in real space, asymptotically improving over the best
previous work. We obtain an analogous result when the external potential of
nuclei is introduced under the Born-Oppenheimer approximation. We prove a
circuit lower bound when the Hamiltonian coefficients take a continuum range of
values, showing that generic $n$-qubit $2$-local Hamiltonians with commuting
terms require at least $\Omega(n^2)$ gates to evolve with accuracy
$\epsilon=\Omega(1/poly(n))$ for time $t=\Omega(\epsilon)$. Our proof is based
on a gate-efficient reduction from the approximate synthesis of diagonal
unitaries within the Hamming weight-$2$ subspace, which may be of independent
interest. Our result thus suggests the use of Hamiltonian structural properties
as both necessary and sufficient to implement Trotter steps with lower gate
complexity.
- Abstract（参考訳）: 量子力学は、ハミルトニアンの初等項を逐次的に解いて量子コンピュータ上でシミュレーションすることができる。
しかし、そのようなトロッターステップの実装は、ハミルトニアン項全体の数に依存するゲート複雑性を持ち、より高度な手法を用いたアルゴリズムと比較すると不利である。
我々は,項数において複雑性をサブ線形とした高速なトロッターステップを実現する手法を開発した。
力則に従って相互作用強度が距離とともに減衰するハミルトニアンのクラスに対してこれを達成する。
提案手法は,再帰的ブロック符号化に基づくもの,平均コストシミュレーションに基づくもの,これら量子シミュレーション技術の正規化因子障壁を克服するものを含む。
また、ハミルトン係数の特定のブロックが低いとき、より高速なトロッターステップを実現する。
より厳密なエラー分析と組み合わせると、{\left(\eta^{1/3}n^{1/3}+\frac{n^{2/3}}{\eta^{2/3}}\right)n^{1+o(1)}$gatesを使って、実空間における第二量子化におけるスピン軌道と$\eta$電子による一様電子ガスをシミュレートし、以前の最良の仕事よりも漸近的に改善できることが分かる。
ボルン-オッペンハイマー近似の下で原子核の外部ポテンシャルが導入されたとき、類似の結果が得られる。
我々は、ハミルトニアン係数が連続値の範囲を取るとき、回路の低い境界を証明し、通勤項を持つ一般の$n$-qubit $2$-local Hamiltonianが、時間$t=\Omega(\epsilon)$に対して$\epsilon=\Omega(1/poly(n))$で進化するために少なくとも$\Omega(n^2)$ゲートを必要とすることを示す。
我々の証明は、ハミングウェイト内の対角ユニタリの近似合成から2$部分空間へのゲート効率の低下に基づく。
その結果, ゲート複雑性の低いトロッターステップを実装するのに必要かつ十分であるハミルトン構造特性を用いることが示唆された。
関連論文リスト
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - Efficient Quantum Simulation Algorithms in the Path Integral Formulation [0.5729426778193399]
我々は、経路積分定式化のハミルトン版に基づく2つの新しい量子アルゴリズムと、 $fracm2dotx2 - V(x)$ という形でラグランジアンに対して提供する。
我々のラグランジアンシミュレーションアルゴリズムは、連続極限において$D+1$次元の$eta$粒子を持つシステムに対して、$V(x)$が有界であれば$widetildeO(eta D t2/epsilon)$としてスケールする離散ラグランジアンを演算するオラクルに対して、多数のクエリを必要とすることを示す。
論文 参考訳（メタデータ） (2024-05-11T15:48:04Z) - Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。
我々は,$O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$クエリを,任意の$Gamma$に対するブロックエンコーディングに使用する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-04T17:58:01Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
我々は、我々の分割と形式主義の征服を通じて、大きな$Lambda$の量子化よりも優れたスケーリングと量子化を得られることを示す。
また,マルチコントロールされたXゲート群を実装する新しい方法を含む,ゲート最適化のための新しいアルゴリズムおよび回路レベル技術も提供する。
論文 参考訳（メタデータ） (2023-06-19T23:20:30Z) - Unbiased random circuit compiler for time-dependent Hamiltonian
simulation [8.694056486825318]
時間依存ハミルトニアンシミュレーションは量子コンピューティングにおいて重要な課題である。
我々はTDHSのための非バイアスランダムコンパイラを開発した。
相互作用図に基づくスピンモデルと分子系の断熱基底状態の数値シミュレーションを行う。
論文 参考訳（メタデータ） (2022-12-19T13:40:05Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
時間依存ハミルトニアンの下でのユニタリ進化は、量子ハードウェアにおけるシミュレーションの重要な構成要素である。
本稿では、トロッターステップを1ブロックの量子ゲートに圧縮するアルゴリズムを提案する。
この結果、ハミルトニアンのある種のクラスに対する固定深度時間進化がもたらされる。
論文 参考訳（メタデータ） (2021-08-06T19:38:01Z) - Parallel Quantum Algorithm for Hamiltonian Simulation [9.680246554758343]
大規模ハミルトニアン群の力学をシミュレートするために並列量子アルゴリズムを提案する。
量子回路深さで測定した並列量子シミュレーションアルゴリズムの実行時間は2倍(多値)の対数依存性を持つ。
本アルゴリズムの総ゲート深さは,並列設定における$operatornamepolylog (1/epsilon)$依存性を持つことを示す。
論文 参考訳（メタデータ） (2021-05-25T12:46:33Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z) - Exponentially faster implementations of Select(H) for fermionic
Hamiltonians [0.0]
本稿では、乗算制御されたユニタリな$textSelect(H) equiv sum_ellを実装する量子回路を構築するためのフレームワークを提案する。
$textSelect(H)$は、いくつかの量子アルゴリズムの主要なサブルーチンの1つである。
論文 参考訳（メタデータ） (2020-04-08T18:00:04Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。