論文の概要: An improved quantum-inspired algorithm for linear regression
- arxiv url: http://arxiv.org/abs/2009.07268v4
- Date: Mon, 27 Jun 2022 02:08:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-02 04:30:26.754289
- Title: An improved quantum-inspired algorithm for linear regression
- Title（参考訳）: 線形回帰のための改良量子インスパイアアルゴリズム
- Authors: Andr\'as Gily\'en and Zhao Song and Ewin Tang
- Abstract要約: 量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。
量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
- 参考スコア（独自算出の注目度）: 15.090593955414137
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give a classical algorithm for linear regression analogous to the quantum
matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review
Letters'09, arXiv:0811.3171] for low-rank matrices [Wossnig, Zhao, and Prakash,
Physical Review Letters'18, arXiv:1704.06174], when the input matrix $A$ is
stored in a data structure applicable for QRAM-based state preparation.
Namely, suppose we are given an $A \in \mathbb{C}^{m\times n}$ with minimum
non-zero singular value $\sigma$ which supports certain efficient $\ell_2$-norm
importance sampling queries, along with a $b \in \mathbb{C}^m$. Then, for some
$x \in \mathbb{C}^n$ satisfying $\|x - A^+b\| \leq \varepsilon\|A^+b\|$, we can
output a measurement of $|x\rangle$ in the computational basis and output an
entry of $x$ with classical algorithms that run in
$\tilde{\mathcal{O}}\big(\frac{\|A\|_{\mathrm{F}}^6\|A\|^6}{\sigma^{12}\varepsilon^4}\big)$
and
$\tilde{\mathcal{O}}\big(\frac{\|A\|_{\mathrm{F}}^6\|A\|^2}{\sigma^8\varepsilon^4}\big)$
time, respectively. This improves on previous "quantum-inspired" algorithms in
this line of research by at least a factor of
$\frac{\|A\|^{16}}{\sigma^{16}\varepsilon^2}$ [Chia, Gily\'en, Li, Lin, Tang,
and Wang, STOC'20, arXiv:1910.06151]. As a consequence, we show that quantum
computers can achieve at most a factor-of-12 speedup for linear regression in
this QRAM data structure setting and related settings. Our work applies
techniques from sketching algorithms and optimization to the quantum-inspired
literature. Unlike earlier works, this is a promising avenue that could lead to
feasible implementations of classical regression in a quantum-inspired
settings, for comparison against future quantum computers.
- Abstract（参考訳）: 低ランク行列 [wossnig, zhao, prakash, physical review letters'18, arxiv:1704.06174] に対して、入力行列 $a$ が qram ベースの状態準備に適用可能なデータ構造に格納されているとき、量子行列反転アルゴリズム [harrow, hassidim, lloyd, physical review letters'09, arxiv:0811.3171] に類似した線形回帰アルゴリズムを与える。
すなわち、$A \in \mathbb{C}^{m\times n}$ を最小零でない特異値 $\sigma$ とし、$b \in \mathbb{C}^m$ とともに、ある効率的な $\ell_2$-norm 重要なサンプリングクエリをサポートする。
すると、$x \in \mathbb{c}^n$ を満たす$\|x - a^+b\| \leq \varepsilon\|a^+b\|$ に対して、計算ベースで$|x\rangle$ の測定値を出力することができ、それぞれ$\tilde{\mathcal{o}}\big(\frac{\|a\|_{\mathrm{f}}^6\|a\|^6}{\sigma^{12}\varepsilon^4}\big)$および$\tilde{\mathcal{o}}\big(\frac{\|a\|_{\mathrm {f}}^6\|a\|^2}{\sigma^8\varepsilon^4}\big) で動作する古典的アルゴリズムで$x$ の入力を出力することができる。
これは、この研究における従来の量子インスパイアされたアルゴリズムを、少なくとも$\frac{\|A\|^{16}}{\sigma^{16}\varepsilon^2}$ [Chia, Gily\'en, Li, Lin, Tang, and Wang, STOC'20, arXiv:1910.06151] で改善する。
その結果、量子コンピュータは、このQRAMデータ構造設定と関連する設定において、線形回帰の最大12倍の高速化を達成できることを示した。
我々の研究は、スケッチアルゴリズムや最適化の技法を量子に着想を得た文献に適用している。
初期の作品とは異なり、これは将来の量子コンピュータと比較するために、量子にインスパイアされた設定で古典回帰を実現可能にする有望な方法である。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups
without Data-Dependent Parameters [10.602399256297032]
我々は,$widetildeO(epsilon-1sqrtnd1.5) + Mathrmpoly(d/epsilon)$timeで動作する量子アルゴリズムを開発した。
データ依存パラメータに依存しない古典的な下界上の2次量子スピードアップを提供する。
論文 参考訳（メタデータ） (2023-11-24T19:41:28Z) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。