論文の概要: Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems

• arxiv url: http://arxiv.org/abs/2307.06627v2
• Date: Thu, 30 Nov 2023 12:33:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-01 23:25:01.667052
• Title: Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems
• Title（参考訳）: 線形系を解くための高速かつ実用的な量子インスパイアされた古典アルゴリズム
• Authors: Qian Zuo and Tongyang Li
• Abstract要約: 線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。 我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
• 参考スコア（独自算出の注目度）: 11.929584800629673
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix $A\in\mathbb{R}^{m\times n}$ and a vector $b\in\mathbb{R}^m$, we propose classical algorithms that produce a data structure for the solution $x\in\mathbb{R}^{n}$ of the linear system $Ax=b$ with the ability to sample and query its entries. The resulting $x$ satisfies $\|x-A^{+}b\|\leq\epsilon\|A^{+}b\|$, where $\|\cdot\|$ is the spectral norm and $A^+$ is the Moore-Penrose inverse of $A$. Our algorithm has time complexity $\widetilde{O}(\kappa_F^4/\kappa\epsilon^2)$ in the general case, where $\kappa_{F} =\|A\|_F\|A^+\|$ and $\kappa=\|A\|\|A^+\|$ are condition numbers. Compared to the prior state-of-the-art result [Shao and Montanaro, arXiv:2103.10309v2], our algorithm achieves a polynomial speedup in condition numbers. When $A$ is $s$-sparse, our algorithm has complexity $\widetilde{O}(s \kappa\log(1/\epsilon))$, matching the quantum lower bound for solving linear systems in $\kappa$ and $1/\epsilon$ up to poly-logarithmic factors [Harrow and Kothari]. When $A$ is $s$-sparse and symmetric positive-definite, our algorithm has complexity $\widetilde{O}(s\sqrt{\kappa}\log(1/\epsilon))$. Technically, our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems, where we propose two new methods with speedups: quantum-inspired Kaczmarz method with momentum and quantum-inspired coordinate descent method with momentum. Their analysis exploits careful decomposition of the momentum transition matrix and the application of novel spectral norm concentration bounds for independent random matrices. Finally, we also conduct numerical experiments for our algorithms on both synthetic and real-world datasets, and the experimental results support our theoretical claims.
• Abstract（参考訳）: 線形系を解くための高速で実用的な量子インスピレーション付き古典アルゴリズムを提案する。 具体的には、行列 $a\in\mathbb{r}^{m\times n}$ とベクトル $b\in\mathbb{r}^m$ に対するサンプリングとクエリアクセスを与えられたとき、線形系の $x\in\mathbb{r}^{n}$ の解に対してデータ構造を生成する古典的なアルゴリズムを提案し、そのエントリをサンプリングしてクエリすることができる。 x$ は $\|x-A^{+}b\|\leq\epsilon\|A^{+}b\|$ を満たすが、$\|\cdot\|$ はスペクトルノルムであり、$A^+$ は$A$ のムーア=ペンローズ逆である。 我々のアルゴリズムは時間複雑性$\widetilde{O}(\kappa_F^4/\kappa\epsilon^2)$で、$\kappa_{F} =\|A\|_F\|A^+\|$と$\kappa=\|A\|\|A^+\|$は条件数である。 shao and montanaro, arxiv:2103.10309v2] の以前の結果と比較すると, このアルゴリズムは条件数で多項式の高速化を実現する。 a$ が $s$-sparse の場合、アルゴリズムは$\widetilde{o}(s \kappa\log(1/\epsilon))$ を持ち、$\kappa$ と $1/\epsilon$ の線形系を解くための量子下限を多対数因子 [harrow と kothari] に一致させる。 a$ が $s$-sparse で対称な正定値であれば、アルゴリズムは$\widetilde{o}(s\sqrt{\kappa}\log(1/\epsilon))$ を持つ。 技術的には、重粒子運動量法を線形系を解くために量子インスパイアされた古典的アルゴリズムに適用し、運動量を持つ量子インスパイアされたカッツマルツ法と運動量を持つ量子インスパイアされた座標降下法という2つの新しい手法を提案する。 これらの解析は運動量遷移行列の注意深く分解し、新しいスペクトルノルム濃度境界を独立なランダム行列に適用する。 最後に, 合成および実世界の両方のデータセット上で, アルゴリズムの数値実験を行い, 実験結果から理論的主張を裏付ける。

関連論文リスト

• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。 また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-04T11:03:48Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Quantum machine learning with subspace states [8.22379888383833]
  量子部分空間状態に基づく量子線型代数の新しいアプローチを導入し,新しい3つの量子機械学習アルゴリズムを提案する。 1つ目は、分布 $Pr[S]= det(X_SX_ST)$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(dlog n)$である。 2つ目は、複素行列に対して$mathcalAk$の量子特異値推定アルゴリズムであり、このアルゴリズムの高速化は指数関数的である。
  論文  参考訳（メタデータ） (2022-01-31T19:34:47Z)
• Faster quantum-inspired algorithms for solving linear systems [0.05076419064097732]
  そこで本研究では,データ構造を$x$で出力する古典的アルゴリズムにより,エントリへのサンプリングとクエリが可能であることを示す。 この出力は、量子線型解法の出力の古典的なアナログと見なすことができる。
  論文  参考訳（メタデータ） (2021-03-18T15:12:44Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• An improved quantum-inspired algorithm for linear regression [15.090593955414137]
  量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。 量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-15T17:58:25Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。 このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-09-09T18:00:09Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。 最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-30T10:42:48Z)

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

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