論文の概要: Improving quantum linear system solvers via a gradient descent
perspective
- arxiv url: http://arxiv.org/abs/2109.04248v1
- Date: Thu, 9 Sep 2021 13:16:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-15 18:26:41.438574
- Title: Improving quantum linear system solvers via a gradient descent
perspective
- Title(参考訳): 勾配勾配勾配を用いた量子線形系解法の改良
- Authors: Sander Gribling, Iordanis Kerenidis, D\'aniel Szil\'agyi
- Abstract要約: 我々は凸最適化の観点から量子線形系解法を再考する。
これにより、実行時にかなりの定数のイテレーションが発生します。
本研究では,子・子・子・ソマの最適量子線形系解法が勾配降下アルゴリズムとどのように関係しているかを示す。
- 参考スコア(独自算出の注目度): 3.0969191504482247
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Solving systems of linear equations is one of the most important primitives
in quantum computing that has the potential to provide a practical quantum
advantage in many different areas, including in optimization, simulation, and
machine learning. In this work, we revisit quantum linear system solvers from
the perspective of convex optimization, and in particular gradient descent-type
algorithms. This leads to a considerable constant-factor improvement in the
runtime (or, conversely, a several orders of magnitude smaller error with the
same runtime/circuit depth).
More precisely, we first show how the asymptotically optimal quantum linear
system solver of Childs, Kothari, and Somma is related to the gradient descent
algorithm on the convex function $\|A\vec x - \vec b\|_2^2$: their linear
system solver is based on a truncation in the Chebyshev basis of the
degree-$(t-1)$ polynomial (in $A$) that maps the initial solution $\vec{x}_1 :=
\vec{b}$ to the $t$-th iterate $\vec{x}_t$ in the basic gradient descent
algorithm. Then, instead of starting from the basic gradient descent algorithm,
we use the optimal Chebyshev iteration method (which can be viewed as an
accelerated gradient descent algorithm) and show that this leads to
considerable improvements in the quantum solver.
- Abstract(参考訳): 線形方程式のシステムを解くことは、最適化、シミュレーション、機械学習など、様々な分野において実用的な量子アドバンテージを提供する可能性を持つ量子コンピューティングにおける最も重要なプリミティブの1つである。
本研究では,凸最適化,特に勾配降下型アルゴリズムの観点から,量子線形系解法を再検討する。
これにより、ランタイム(あるいは、逆に、同じランタイム/サーキットの深さで、数桁小さなエラー)が大幅に改善される。
より正確には、まず、子供の漸近的最適量子線形系ソルバが、凸関数 $\|a\vec x - \vec b\|_2^2$: 彼らの線形系ソルバが、最初の解 $\vec{x}_1 := \vec{b}$ to the $t$-th iterate $\vec{x}_t$ を基本勾配降下アルゴリズムで写像する次数-$(t-1)$ polynomial (in $a$) のチェビシェフ基底における切断に基づいていることを示す。
次に、基本的な勾配降下アルゴリズムから始めるのではなく、最適なチェビシェフ反復法(加速勾配降下アルゴリズムと見なすことができる)を使い、量子解法が大幅に改善されることを示す。
関連論文リスト
- Increasing the dimension of linear systems solved by classical or
quantum binary optimization: A new method to solve large linear equation
systems [41.94295877935867]
本稿では,二進最適化問題として記述された線形システムの解法を提案する。
この手順は問題を効率的に解決し、大きな線形系を扱えるようにする。
論文 参考訳(メタデータ) (2023-09-18T16:51:03Z) - GRAPE optimization for open quantum systems with time-dependent
decoherence rates driven by coherent and incoherent controls [77.34726150561087]
グラディエントアセンセントパルス工学(GRAPE)法は量子制御の最適化に広く用いられている。
我々は、コヒーレント制御と非コヒーレント制御の両方によって駆動されるオープン量子系の目的関数を最適化するために、GRAPE法を採用する。
状態-状態遷移問題に対する数値シミュレーションによりアルゴリズムの効率を実証する。
論文 参考訳(メタデータ) (2023-07-17T13:37:18Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳(メタデータ) (2023-05-19T00:07:32Z) - Pure Quantum Gradient Descent Algorithm and Full Quantum Variational
Eigensolver [0.7149735232319818]
勾配勾配勾配勾配法は広く採用されている最適化法である。
単一オラクル計算のみを必要とする新しい量子ベース勾配計算法を提案する。
我々は量子勾配降下法をうまく実装し、変分量子固有解法(VQE)に適用した。
論文 参考訳(メタデータ) (2023-05-07T05:52:41Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
アルゴリズムの複雑さは$O(rm polylog(n/epsilon))$であり、これは次元$n$の最適古典アルゴリズムよりも指数関数的に改善される。
我々のアルゴリズムは指数関数的にQNSEの解を加速し、あらゆる非線形問題に適用できる。
論文 参考訳(メタデータ) (2021-12-03T00:27:16Z) - Quantum homotopy perturbation method for nonlinear dissipative ordinary
differential equations [0.25782420501870296]
我々は$n$次元非線形散逸型常微分方程式(ODE)を解くための量子アルゴリズムを提案する。
我々のアルゴリズムは、最高の古典的アルゴリズムや以前の量子アルゴリズムを$n$または$epsilon$で指数関数的に改善する。
論文 参考訳(メタデータ) (2021-11-15T01:34:43Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳(メタデータ) (2021-08-18T09:26:17Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳(メタデータ) (2020-02-10T23:23:04Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。