論文の概要: Optimal Lower Bounds for Hamiltonian Simulation

• arxiv url: http://arxiv.org/abs/2607.19852v1
• Date: Wed, 22 Jul 2026 07:41:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-23 18:51:38.016355
• Title: Optimal Lower Bounds for Hamiltonian Simulation
• Title（参考訳）: ハミルトニアンシミュレーションのための最適下界
• Abstract要約: ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。 任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
• 参考スコア（独自算出の注目度）: 42.227880669333835
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For Hamiltonian $H = \sum_j h_j$, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms $\|h_j\|$, time $t$, and trace-distance error $ε$. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case $\|h_j\|$ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in $1/ε$, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.
• Abstract（参考訳）: ハミルトニアン $H = \sum_j h_j$ に対して、ゲート上の漸近的に狭い下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明する。 我々の境界は任意の項ノルム $\|h_j\|$, time $t$, trace-distance error $ε$ である。 一致する上界(複合qDRIFT)は、大項の高次トロッター化と小項の無作為な一階トロッター化からなる。 時間進化におけるパリティや他のブール関数の計算をエンコードするために、最悪の場合 $\|h_j\|$ を選択する以前の作業とは異なり、我々の証明は初等的で、局所的に有界な古典的ハミルトニアンに基づいている。 我々の研究は、多くの物理系(例えば、パワーロー相互作用)において、ブロックエンコーディングモデルのようなコヒーレントなオラクルクエリを数えることによる複雑さとは対照的に、ゲートカウントは1/ε$で多項式的にスケールする必要があることを示唆している。

関連論文リスト

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  我々は、ハミルトニアン復号量子干渉計(HDQI)を紹介する。 HDQIはコヒーレントな測定とパウリ群のシンプレクティック表現を利用して、ギブスサンプリングとハミルトン・ベリアンを減少させる。 そこで,HDQI はギブズ状態を任意の温度で効率的に生成し,物理的にモチベーションを持つハミルトニアンのクラスに適応することを示した。
  論文  参考訳（メタデータ） (2025-10-09T08:06:15Z)
• Optimal quantum simulation of linear non-unitary dynamics [0.31439717339537293]
  有界時間依存演算子$-A$によって生成される時間進化をシミュレートする量子アルゴリズムを提案する。 本稿では,最近のLinear-Combination-of-Hamiltonian-Simulation (LCHS)フレームワークを一般化する。
  論文  参考訳（メタデータ） (2025-08-26T17:58:27Z)
• Computational Complexity of Non-Hermitian Quantum Systems [0.0]
  条件付き時間進化は、量子システムが監視され、1つのポストセレクトが測定記録に記録されるときに起こる。 我々は、ポストセレクションと任意の非エルミート・ハミルトンの同値性を確立する。 非エルミート物理学は、量子優位性を保証することも、効率的な古典的シミュレーションを妨げない。
  論文  参考訳（メタデータ） (2025-06-03T22:35:28Z)
• Quantum singular value transformation without block encodings: Near-optimal complexity with minimal ancilla [18.660349597156266]
  量子特異値変換(Quantum Singular Value Transformation, QSVT)は,最もよく知られた量子アルゴリズムをカプセル化する統一フレームワークである。 その結果,量子アルゴリズムの新しいフレームワークが確立され,ハードウェアのオーバヘッドが大幅に低減され,ほぼ最適性能が維持された。
  論文  参考訳（メタデータ） (2025-04-03T08:24:15Z)
• 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)
• Composite QDrift-Product Formulas for Quantum and Classical Simulations in Real and Imaginary Time [0.18374319565577155]
  最近の研究は、与えられたシミュレーション問題に対してハミルトニアン$H$をサブセットに分割する合成チャネルを実装するのが有利であることを示した。 このアプローチは想像上の時間で成り立ち、量子モンテカルロ計算の古典的アルゴリズムの候補となる。 一定の誤差耐性を満たすために,$e-iH_j t$および$e-H_j beta$のゲート数を数えることにより,アルゴリズムコストの正確な数値シミュレーションを行う。
  論文  参考訳（メタデータ） (2023-06-28T21:31:26Z)
• On the complexity of implementing Trotter steps [2.1369834525800138]
  我々は,複雑性をサブ線形とした高速なトロッターステップを実現する手法を開発した。 また、ハミルトン係数の特定のブロックが低いとき、より高速なトロッターステップを実現する。 以上の結果から, ゲートの複雑度が低いトロッター合成ステップを実装する上で, ハミルトン構造特性を必要かつ十分なものにすることが示唆された。
  論文  参考訳（メタデータ） (2022-11-16T19:00:01Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• Hamiltonian simulation with random inputs [74.82351543483588]
  ランダム初期状態を持つハミルトンシミュレーションの平均ケース性能の理論 数値的な証拠は、この理論がコンクリート模型の平均誤差を正確に特徴づけていることを示唆している。
  論文  参考訳（メタデータ） (2021-11-08T19:08:42Z)

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

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