論文の概要: On the Impossibility of General Parallel Fast-forwarding of Hamiltonian
Simulation
- arxiv url: http://arxiv.org/abs/2305.12444v1
- Date: Sun, 21 May 2023 12:30:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-23 20:23:52.406282
- Title: On the Impossibility of General Parallel Fast-forwarding of Hamiltonian
Simulation
- Title（参考訳）: ハミルトニアンシミュレーションの一般並列高速転送の不可能性について
- Authors: Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting
Lin, Yu-Ching Shen
- Abstract要約: ハミルトンシミュレーションは量子コンピューティングの分野で最も重要な問題の1つである。
既存のシミュレーションアルゴリズムでは、進化時間$T$で少なくとも線形に実行する必要がある。
高速ハミルトニアンシミュレーションが並列性の力で達成できるかどうかは興味深い。
- 参考スコア（独自算出の注目度）: 4.925967492198012
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Hamiltonian simulation is one of the most important problems in the field of
quantum computing. There have been extended efforts on designing algorithms for
faster simulation, and the evolution time $T$ for the simulation turns out to
largely affect algorithm runtime. While there are some specific types of
Hamiltonians that can be fast-forwarded, i.e., simulated within time $o(T)$,
for large enough classes of Hamiltonians (e.g., all local/sparse Hamiltonians),
existing simulation algorithms require running time at least linear in the
evolution time $T$. On the other hand, while there exist lower bounds of
$\Omega(T)$ circuit size for some large classes of Hamiltonian, these lower
bounds do not rule out the possibilities of Hamiltonian simulation with large
but "low-depth" circuits by running things in parallel. Therefore, it is
intriguing whether we can achieve fast Hamiltonian simulation with the power of
parallelism.
In this work, we give a negative result for the above open problem, showing
that sparse Hamiltonians and (geometrically) local Hamiltonians cannot be
parallelly fast-forwarded. In the oracle model, we prove that there are
time-independent sparse Hamiltonians that cannot be simulated via an oracle
circuit of depth $o(T)$. In the plain model, relying on the random oracle
heuristic, we show that there exist time-independent local Hamiltonians and
time-dependent geometrically local Hamiltonians that cannot be simulated via an
oracle circuit of depth $o(T/n^c)$, where the Hamiltonians act on $n$-qubits,
and $c$ is a constant.
- Abstract（参考訳）: ハミルトンシミュレーションは量子コンピューティングの分野で最も重要な問題の1つである。
シミュレーションを高速化するためのアルゴリズム設計の努力は拡大しており、シミュレーションに要する進化時間t$はアルゴリズムのランタイムに大きな影響を与えている。
時間$o(T)$でシミュレートされるような、高速にフォワードできるいくつかの特定の種類のハミルトンアンが存在するが(例えば、すべての局所・スパースハミルトンアン)、既存のシミュレーションアルゴリズムは、進化時間$T$で少なくともランニング時間を必要とする。
一方、ハミルトニアンのいくつかの大きなクラスには、$\Omega(T)$回路サイズが低い境界が存在するが、これらの下限は、物事を平行に実行することによって、大きなが「より深い」回路を持つハミルトニアンシミュレーションの可能性を排除していない。
したがって、並列性の力で高速ハミルトンシミュレーションを実現できるかどうかは興味深い。
本研究では、上記の開問題に対して負の結果を与え、疎ハミルトニアンおよび(幾何学的に)局所ハミルトニアンが平行に高速に進行できないことを示す。
オラクルモデルでは、深さ$o(T)$のオラクル回路ではシミュレートできない時間非依存のスパースハミルトンが存在することを証明している。
普通のモデルでは、ランダムなオラクルのヒューリスティックに依拠して、時間に依存しない局所ハミルトニアンと時間に依存した幾何学的局所ハミルトニアンが存在して、深さ$o(t/n^c)$のオラクル回路でシミュレートできないことを示し、そこでハミルトニアンは$n$-qubitsで作用し、$c$は定数である。
関連論文リスト
- New random compiler for Hamiltonians via Markov Chains [0.08192907805418585]
アディアバティックアルゴリズムのような多くの量子アルゴリズムは、ハミルトン進化をシミュレートする必要がある。
我々は,第1次ランダム化トロッターに似た新しいコンパイラを開発したが,そのフレームワークは間違いなくシンプルである。
大規模なランダム化スキームと時間依存重みをサポートするため、より多用途である。
論文 参考訳（メタデータ） (2024-11-10T14:57:25Z) - Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
量子多体物理学における基本的な問題は、局所ハミルトニアンの基底状態を見つけることである。
基底状態特性を学習するためのシステムサイズ$n$とは無関係に,一定のサンプル複雑性を実現する2つのアプローチを導入する。
論文 参考訳（メタデータ） (2024-05-28T18:00:32Z) - Hamiltonian Property Testing [0.8192907805418583]
局所性は多くの物理的時間進化の基本的な特徴である。
未知のハミルトニアンが局所的であるかどうかを厳格に検証するプロトコルは知られていない。
論文 参考訳（メタデータ） (2024-03-05T13:44:28Z) - Simplifying the simulation of local Hamiltonian dynamics [0.0]
局所ハミルトン群、$H_k$は量子多体系における非自明な$k$ボディ相互作用を記述する。
我々は、同じ物理をシミュレートする$H_k$と$H_k'$の例を導出する既知の方法を構築する。
我々は、与えられた$H_k$ハミルトニアンを最大精度で、与えられた$H_k$ハミルトニアンの短時間ダイナミクスをシミュレートする、$k'$-ローカルハミルトニアンを探索する方法を提案する。
論文 参考訳（メタデータ） (2023-10-10T22:31:45Z) - Hamiltonian simulation with random inputs [74.82351543483588]
ランダム初期状態を持つハミルトンシミュレーションの平均ケース性能の理論
数値的な証拠は、この理論がコンクリート模型の平均誤差を正確に特徴づけていることを示唆している。
論文 参考訳（メタデータ） (2021-11-08T19:08:42Z) - 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) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。
一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。
幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
論文 参考訳（メタデータ） (2021-04-01T19:06:00Z) - Quantum algorithm for time-dependent Hamiltonian simulation by
permutation expansion [6.338178373376447]
時間依存ハミルトニアンの力学シミュレーションのための量子アルゴリズムを提案する。
アルゴリズムのコストはハミルトニアン周波数に依存しないことを示す。
論文 参考訳（メタデータ） (2021-03-29T05:02:02Z) - 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) - Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
ランダム量子回路は古典的にシミュレートするのは難しいと見なされる。
典型例の近似シミュレーションは, 正確なシミュレーションとほぼ同程度に困難であることを示す。
また、十分に浅いランダム回路はより一般的に効率的にシミュレーション可能であると推測する。
論文 参考訳（メタデータ） (2019-12-31T19:00:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。