論文の概要: Faster quantum-inspired algorithms for solving linear systems
- arxiv url: http://arxiv.org/abs/2103.10309v2
- Date: Sat, 15 Apr 2023 21:53:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-19 01:32:30.387220
- Title: Faster quantum-inspired algorithms for solving linear systems
- Title（参考訳）: 線形系を解くための高速量子インスパイアアルゴリズム
- Authors: Changpeng Shao and Ashley Montanaro
- Abstract要約: そこで本研究では,データ構造を$x$で出力する古典的アルゴリズムにより,エントリへのサンプリングとクエリが可能であることを示す。
この出力は、量子線型解法の出力の古典的なアナログと見なすことができる。
- 参考スコア（独自算出の注目度）: 0.05076419064097732
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We establish an improved classical algorithm for solving linear systems in a
model analogous to the QRAM that is used by quantum linear solvers. Precisely,
for the linear system $A\x = \b$, we show that there is a classical algorithm
that outputs a data structure for $\x$ allowing sampling and querying to the
entries, where $\x$ is such that $\|\x - A^{+}\b\|\leq \epsilon \|A^{+}\b\|$.
This output can be viewed as a classical analogue to the output of quantum
linear solvers. The complexity of our algorithm is $\widetilde{O}(\kappa_F^4
\kappa^2/\epsilon^2 )$, where $\kappa_F = \|A\|_F\|A^{+}\|$ and $\kappa =
\|A\|\|A^{+}\|$. This improves the previous best algorithm [Gily{\'e}n, Song
and Tang, arXiv:2009.07268] of complexity $\widetilde{O}(\kappa_F^6
\kappa^6/\epsilon^4)$. Our algorithm is based on the randomized Kaczmarz
method, which is a particular case of stochastic gradient descent. We also find
that when $A$ is row sparse, this method already returns an approximate
solution $\x$ in time $\widetilde{O}(\kappa_F^2)$, while the best quantum
algorithm known returns $\ket{\x}$ in time $\widetilde{O}(\kappa_F)$ when $A$
is stored in the QRAM data structure. As a result, assuming access to QRAM and
if $A$ is row sparse, the speedup based on current quantum algorithms is
quadratic.
- Abstract（参考訳）: 量子線形解法で用いられるQRAMに類似したモデルで線形系を解くための古典的アルゴリズムを改良した。
正確には、線形システム $A\x = \b$ に対して、$\x$ に対してデータ構造を出力する古典的アルゴリズムがあることを示し、$\x$ は$\|\x - A^{+}\b\|\leq \epsilon \|A^{+}\b\|$ である。
この出力は量子線形解法の出力の古典的な類似物と見なすことができる。
アルゴリズムの複雑さは$\widetilde{O}(\kappa_F^4 \kappa^2/\epsilon^2 )$, $\kappa_F = \|A\|_F\|A^{+}\|$, $\kappa = \|A\|\|A^{+}\|$である。
これにより、以前の最良のアルゴリズム (Gily{\'e}n, Song and Tang, arXiv:2009.07268] の複雑さ$\widetilde{O}(\kappa_F^6 \kappa^6/\epsilon^4)$ が改善される。
このアルゴリズムは確率勾配降下の特別な場合であるランダム化Kaczmarz法に基づいている。
また、$a$ が行スパースである場合、このメソッドはすでに近似解 $\x$ in time $\widetilde{o}(\kappa_f^2)$ を返しますが、既知の最良の量子アルゴリズムは$\ket{\x}$ in time $\widetilde{o}(\kappa_f)$ をqramデータ構造に格納すると返します。
その結果、QRAMへのアクセスと$A$が行スパースであれば、現在の量子アルゴリズムに基づくスピードアップは二次的である。
関連論文リスト
- Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。
本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。
微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
論文 参考訳（メタデータ） (2024-10-23T18:00:01Z) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文 参考訳（メタデータ） (2023-11-06T16:00:07Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。
我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文 参考訳（メタデータ） (2022-12-29T19:26:12Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - An improved quantum-inspired algorithm for linear regression [15.090593955414137]
量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。
量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-15T17:58:25Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。