論文の概要: A theory of quantum differential equation solvers: limitations and
fast-forwarding
- arxiv url: http://arxiv.org/abs/2211.05246v1
- Date: Wed, 9 Nov 2022 22:50:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-19 20:32:38.018362
- Title: A theory of quantum differential equation solvers: limitations and
fast-forwarding
- Title(参考訳): 量子微分方程式解法の理論:限界と高速フォワード
- Authors: Dong An, Jin-Peng Liu, Daochen Wang, Qi Zhao
- Abstract要約: 量子アルゴリズムは2種類の非量子性に起因する計算オーバーヘッドに悩まされている」。
次に、両タイプの非量子性を持たないODEは量子力学と等価であることを示す。
本稿では、ODEの特殊クラスを解くための高速フォワード量子アルゴリズムについて述べる。
- 参考スコア(独自算出の注目度): 19.080267236745623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the limitations and fast-forwarding of quantum algorithms for
solving linear ordinary differential equation (ODE) systems with particular
focus on non-quantum dynamics, where the coefficient matrix in the ODE is not
anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic
homogeneous linear ODEs, by proving worst-case lower bounds, we show that
quantum algorithms suffer from computational overheads due to two types of
``non-quantumness'': real part gap and non-normality of the coefficient matrix.
We then show that ODEs in the absence of both types of ``non-quantumness'' are
equivalent to quantum dynamics, and reach the conclusion that quantum
algorithms for quantum dynamics work best. We generalize our results to the
inhomogeneous case and find that existing generic quantum ODE solvers cannot be
substantially improved. To obtain these lower bounds, we propose a general
framework for proving lower bounds on quantum algorithms that are amplifiers,
meaning that they amplify the difference between a pair of input quantum
states. On the other hand, we show how to fast-forward quantum algorithms for
solving special classes of ODEs which leads to improved efficiency. More
specifically, we obtain quadratic to exponential improvements in terms of the
evolution time $T$ and the spectral norm of the coefficient matrix for the
following classes of ODEs: inhomogeneous ODEs with a negative definite
coefficient matrix, inhomogeneous ODEs with a coefficient matrix having an
eigenbasis that can be efficiently prepared on a quantum computer and
eigenvalues that can be efficiently computed classically, and the spatially
discretized inhomogeneous heat equation and advection-diffusion equation. We
give fast-forwarding algorithms that are conceptually different from existing
ones in the sense that they neither require time discretization nor solving
high-dimensional linear systems.
- Abstract(参考訳): 本研究では,非量子力学に着目した線形常微分方程式(ode)方程式の解法における量子アルゴリズムの限界と高速解法について検討する。
一方,一様線形 ode に対して,最悪の場合の下限を証明すれば,量子アルゴリズムは'非量子性' の実部ギャップと係数行列の非正規性 (non-normality of the coefficient matrix) という2つのタイプの'非量子性'によって計算上のオーバーヘッドを負うことが分かる。
両タイプの「非量子性」が存在しないodeは量子力学と同値であることを示し、量子力学の量子アルゴリズムが最善であるという結論に達した。
その結果を不均質な場合に一般化し、既存の一般的な量子 ode ソルバが大幅に改善できないことを見出す。
これらの下位境界を得るために、増幅器である量子アルゴリズムの下位境界を証明するための一般的な枠組みを提案し、入力された量子状態のペアの違いを増幅する。
一方,odeの特殊クラスを高速に解くための量子アルゴリズムを提案することで,効率が向上することを示す。
More specifically, we obtain quadratic to exponential improvements in terms of the evolution time $T$ and the spectral norm of the coefficient matrix for the following classes of ODEs: inhomogeneous ODEs with a negative definite coefficient matrix, inhomogeneous ODEs with a coefficient matrix having an eigenbasis that can be efficiently prepared on a quantum computer and eigenvalues that can be efficiently computed classically, and the spatially discretized inhomogeneous heat equation and advection-diffusion equation.
我々は、時間離散化や高次元線形システムの解法を必要としないという意味で、既存のものと概念的に異なる高速フォワードアルゴリズムを提供する。
関連論文リスト
- Hybrid quantum-classical and quantum-inspired classical algorithms for
solving banded circulant linear systems [0.8192907805418583]
帯状循環系に対する量子状態の組み合わせの凸最適化に基づく効率的なアルゴリズムを提案する。
帯状循環行列を巡回置換に分解することにより, 量子状態の組み合わせによる近似解を$K$とする。
我々は,従来のシミュレーションと実際のIBM量子コンピュータ実装を用いて本手法を検証し,熱伝達などの物理問題への適用性を示した。
論文 参考訳(メタデータ) (2023-09-20T16:27:16Z) - Quantum Solvable Nonlinear Differential Equations [2.36461933991449]
量子コンピュータ上で効率的に解ける非線形ODEのクラスを量子可解ODEと呼ぶ。
具体的には、Koopman-von-Neumann線型化を用いて、非線型ODEをハミルトン力学に写像し、写像されたハミルトンのノルムが保存され、写像されたハミルトンのノルムがスパースである条件を見つける。
量子可解ODEは、拡張短距離倉本モデルのような幅広い非線形ODEを含むことを示す。
論文 参考訳(メタデータ) (2023-05-01T04:22:56Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳(メタデータ) (2023-04-12T18:10:47Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum Kernel Methods for Solving Differential Equations [21.24186888129542]
量子カーネル法を用いて微分方程式(DE)の解法を提案する。
量子モデルをカーネル関数の重み付け和として構成し、特徴写像を用いて変数を符号化し、モデル微分を表現する。
論文 参考訳(メタデータ) (2022-03-16T18:56:35Z) - Variational Adiabatic Gauge Transformation on real quantum hardware for
effective low-energy Hamiltonians and accurate diagonalization [68.8204255655161]
変分アダバティックゲージ変換(VAGT)を導入する。
VAGTは、現在の量子コンピュータを用いてユニタリ回路の変動パラメータを学習できる非摂動型ハイブリッド量子アルゴリズムである。
VAGTの精度は、RigettiおよびIonQ量子コンピュータ上でのシミュレーションと同様に、トラフ数値シミュレーションで検証される。
論文 参考訳(メタデータ) (2021-11-16T20:50:08Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。
変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。
量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
論文 参考訳(メタデータ) (2021-08-09T18:00:05Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳(メタデータ) (2021-06-24T20:16:02Z) - Quantum Algorithms for Solving Ordinary Differential Equations via
Classical Integration Methods [1.802439717192088]
微分方程式を解くために,量子コンピュータの利用について検討する。
我々は、対応するデジタル量子回路を考案し、シミュレーションし、6$mathrmth$order Gauss-Legendreコロケーション法を実装し、実行する。
将来有望なシナリオとして、デジタル算術法は、逆問題に対する量子探索アルゴリズムの「オークル」として使用できる。
論文 参考訳(メタデータ) (2020-12-17T09:49:35Z) - Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular
Simulations on Quantum Computing Devices [0.0]
エネルギーの古典的方法の量子アナログである縮約固有値方程式の量子解法を導入する。
量子シミュレータと2つのIBM量子処理ユニットで計算を行う。
論文 参考訳(メタデータ) (2020-04-23T18:35:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。