論文の概要: Time-marching based quantum solvers for time-dependent linear
differential equations
- arxiv url: http://arxiv.org/abs/2208.06941v1
- Date: Sun, 14 Aug 2022 23:49:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-31 03:56:07.226665
- Title: Time-marching based quantum solvers for time-dependent linear
differential equations
- Title(参考訳): 時間依存線形微分方程式に対する時間マーチングに基づく量子解法
- Authors: Di Fang, Lin Lin, Yu Tong
- Abstract要約: タイムマーチング戦略は、古典コンピュータ上の時間依存微分方程式を解く自然な戦略である。
時間マーチングに基づく量子解法は、時間ステップ数に関して指数関数的に成功確率を逸脱させる可能性があることを示す。
これは、量子線型系アルゴリズムに基づくものに代わる量子微分方程式の解法を設計する道を提供する。
- 参考スコア(独自算出の注目度): 3.1952399274829775
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The time-marching strategy, which propagates the solution from one time step
to the next, is a natural strategy for solving time-dependent differential
equations on classical computers, as well as for solving the Hamiltonian
simulation problem on quantum computers. For more general linear differential
equations, a time-marching based quantum solver can suffer from exponentially
vanishing success probability with respect to the number of time steps and is
thus considered impractical. We solve this problem by repeatedly invoking a
technique called the uniform singular value amplification, and the overall
success probability can be lower bounded by a quantity that is independent of
the number of time steps. The success probability can be further improved using
a compression gadget lemma. This provides a path of designing quantum
differential equation solvers that is alternative to those based on quantum
linear systems algorithms (QLSA). We demonstrate the performance of the
time-marching strategy with a high-order integrator based on the truncated
Dyson series. The complexity of the algorithm depends linearly on the
amplification ratio, which quantifies the deviation from a unitary dynamics. We
prove that the linear dependence on the amplification ratio attains the query
complexity lower bound and thus cannot be improved in general. This algorithm
also surpasses existing QLSA based solvers in three aspects: (1) the
coefficient matrix $A(t)$ does not need to be diagonalizable. (2) $A(t)$ can be
non-smooth, and is only of bounded variation. (3) It can use fewer queries to
the initial state. Finally, we demonstrate the time-marching strategy with a
first-order truncated Magnus series, while retaining the aforementioned
benefits. Our analysis also raises some open questions concerning the
differences between time-marching and QLSA based methods for solving
differential equations.
- Abstract(参考訳): 時間マーチング戦略(英: time-marching strategy)は、古典的コンピュータ上の時間依存微分方程式を解くための自然な戦略であり、量子コンピュータ上のハミルトニアンシミュレーション問題を解くための自然な戦略である。
より一般的な線形微分方程式では、時間マーチングに基づく量子ソルバは、時間ステップの数に関して指数関数的に消滅する成功確率に苦しめられ、従って非現実的と見なされる。
本稿では,一様特異値増幅と呼ばれる手法を反復的に呼び出すことでこの問題を解決し,全体の成功確率を時間ステップ数に依存しない量で低くすることができる。
圧縮ガジェットレムマを用いて、成功確率をさらに向上することができる。
これは、量子線形システムアルゴリズム(QLSA)に基づくものに代わる量子微分方程式の解法を設計する道を提供する。
本稿では,休眠ダイソン系列に基づく高次積分器を用いて,時間マーチング戦略の性能を示す。
アルゴリズムの複雑さは、ユニタリダイナミクスからの偏差を定量化する増幅比に線形に依存する。
増幅比に対する線形依存がクエリの複雑性を低くし、一般には改善できないことを証明した。
このアルゴリズムはまた、既存のQLSAベースの解法を3つの側面で上回る: (1) 係数行列 $A(t)$ は対角化可能である必要はない。
(2) $a(t)$ は非スムースであり、有界な変動のみである。
(3)初期状態に対するクエリを少なくすることができる。
最後に,上述の利点を保ちつつ,一階切開マグナス系列による時間マーチング戦略を実証する。
また,微分方程式を解くための時間マーチング法とqlsa法の違いについて,いくつかの疑問を提起する。
関連論文リスト
- Further improving quantum algorithms for nonlinear differential
equations via higher-order methods and rescaling [0.0]
本稿では,Carleman線形化法に基づく既存量子アルゴリズムの3つの改良点について述べる。
線形化微分方程式の解法として高精度な手法を用いることで,誤差の対数的依存性と時間的近線形依存性を実現する。
再スケーリング技術はコストを大幅に削減し、そうでなければODEのシステムに対するCarleman順序で指数関数的になる。
論文 参考訳(メタデータ) (2023-12-15T03:52:44Z) - A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical
Initialization [107.07093621337084]
正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。
1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。
有名な座標降下法に基づく新しいN-Cut解法を提案する。
論文 参考訳(メタデータ) (2023-11-26T07:11:58Z) - An Inexact Feasible Quantum Interior Point Method for Linearly
Constrained Quadratic Optimization [0.0]
量子線形システムアルゴリズム(QLSA)は、線形システムの解法に依存するアルゴリズムを高速化する可能性がある。
本研究では, 線形制約付き2次最適化問題の解法において, 実効性のないQIPM(Inexact-Feasible QIPM)を提案する。
論文 参考訳(メタデータ) (2023-01-13T01:36:13Z) - Depth analysis of variational quantum algorithms for heat equation [0.0]
量子コンピュータ上での熱方程式を解くための3つの方法を考える。
ハミルトン分解におけるパウリ積の指数的な数は、量子速度を達成できない。
アンザッツ・ツリーのアプローチは行列の明示的な形式を利用しており、古典的アルゴリズムよりも有利である。
論文 参考訳(メタデータ) (2022-12-23T14:46:33Z) - Quantum algorithm for time-dependent differential equations using Dyson
series [0.0]
誤差と微分に複雑性の対数依存を持つ時間依存線形微分方程式を解くための量子アルゴリズムを提案する。
我々の方法は、線形方程式系のダイソン級数を符号化し、最適量子線型方程式解法によって解くことである。
論文 参考訳(メタデータ) (2022-12-07T09:50:40Z) - Accelerating the training of single-layer binary neural networks using
the HHL quantum algorithm [58.720142291102135]
Harrow-Hassidim-Lloyd (HHL) の量子力学的実装から有用な情報が抽出可能であることを示す。
しかし,本論文では,HHLの量子力学的実装から有用な情報を抽出し,古典的側面における解を見つける際の複雑性を低減することを目的としている。
論文 参考訳(メタデータ) (2022-10-23T11:58:05Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳(メタデータ) (2021-08-18T09:26:17Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Covariance-Free Sparse Bayesian Learning [62.24008859844098]
共分散行列の明示的な反転を回避する新しいSBL推論アルゴリズムを導入する。
私たちの手法は、既存のベースラインよりも数千倍も高速です。
我々は,SBLが高次元信号回復問題に難なく対処できる新しいアルゴリズムについて紹介する。
論文 参考訳(メタデータ) (2021-05-21T16:20:07Z) - Efficient quantum algorithm for dissipative nonlinear differential
equations [1.1988695717766686]
我々は、散逸的2次2次元常微分方程式の量子アルゴリズムを開発する。
我々のアルゴリズムは複雑性$T2 qmathrmpoly(log T, log n, log 1/epsilon)/epsilon$, ここでは$T$が進化時間、$epsilon$が許容エラー、$q$が解の崩壊を測定する。
論文 参考訳(メタデータ) (2020-11-06T04:27:00Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。