論文の概要: 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法の違いについて,いくつかの疑問を提起する。

関連論文リスト

• Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
  我々は$fracd|urangledtという形の非線形微分方程式に対する量子アルゴリズムを提案する。 また,Euler法に基づく古典的アルゴリズムを導入し,制限された場合の量子アルゴリズムへのコンパラブルなスケーリングを実現する。
  論文  参考訳（メタデータ） (2024-07-10T14:08:58Z)
• Nonlinear dynamics as a ground-state solution on quantum computers [39.58317527488534]
  量子ビットレジスタにおける空間と時間の両方を符号化する変分量子アルゴリズム(VQA)を提案する。 時空符号化により、1つの基底状態計算から全時間進化を得ることができる。
  論文  参考訳（メタデータ） (2024-03-25T14:06:18Z)
• 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)
• Improving the convergence of an iterative algorithm for solving arbitrary linear equation systems using classical or quantum binary optimization [39.58317527488534]
  本稿では,線形システムの解法を提案する。 線形系を二進最適化問題に変換し、元の問題の幾何学からインスピレーションを得る。 問題固有の幾何学の部分的知識を活用することで、元の問題をより小さく独立したサブプロブレムに分解できることを実証する。
  論文  参考訳（メタデータ） (2023-09-18T16:51:03Z)
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts [0.0]
  一般線型常微分方程式に対する解を量子状態に符号化するコストの非漸近計算を初めて与える。 古典力学の大規模クラスの安定性がそれらの高速なフォワードを可能にすることを示す。 ヒストリー状態は常に任意の安定線型系に対して複雑性$O(T1/2)$で出力できる。
  論文  参考訳（メタデータ） (2023-09-14T17:25:43Z)
• 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)
• Quantum algorithm for time-dependent differential equations using Dyson series [0.0]
  誤差と微分に複雑性の対数依存を持つ時間依存線形微分方程式を解くための量子アルゴリズムを提案する。 我々の方法は、線形方程式系のダイソン級数を符号化し、最適量子線型方程式解法によって解くことである。
  論文  参考訳（メタデータ） (2022-12-07T09:50:40Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。 グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
  論文  参考訳（メタデータ） (2021-06-02T12:50:56Z)
• Covariance-Free Sparse Bayesian Learning [62.24008859844098]
  共分散行列の明示的な反転を回避する新しいSBL推論アルゴリズムを導入する。 私たちの手法は、既存のベースラインよりも数千倍も高速です。 我々は,SBLが高次元信号回復問題に難なく対処できる新しいアルゴリズムについて紹介する。
  論文  参考訳（メタデータ） (2021-05-21T16:20:07Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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