論文の概要: 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$) のチェビシェフ基底における切断に基づいていることを示す。
次に、基本的な勾配降下アルゴリズムから始めるのではなく、最適なチェビシェフ反復法(加速勾配降下アルゴリズムと見なすことができる)を使い、量子解法が大幅に改善されることを示す。
関連論文リスト
- A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
古典的近位点法(PPA)に着想を得た量子線形系問題(QLSP)に対する新しい量子アルゴリズムを提案する。
提案手法は,既存のtexttimattQLSP_solverを経由した修正行列の逆変換が可能なメタアルゴリズムとみなすことができる。
ステップサイズ$eta$を慎重に選択することにより、提案アルゴリズムは線形システムに対して、以前のアプローチの適用性を阻害する条件数への依存を軽減するために、効果的に事前条件を定めることができる。
論文 参考訳（メタデータ） (2024-06-19T23:15:35Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。