論文の概要: An Improved Classical Singular Value Transformation for Quantum Machine
Learning
- arxiv url: http://arxiv.org/abs/2303.01492v1
- Date: Thu, 2 Mar 2023 18:53:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-03 12:48:29.203171
- Title: An Improved Classical Singular Value Transformation for Quantum Machine
Learning
- Title(参考訳): 量子機械学習のための古典特異値変換の改良
- Authors: Ainesh Bakshi and Ewin Tang
- Abstract要約: 量子機械学習(QML)は、量子コンピュータのキラー応用を生み出す大きな可能性を示している。
本稿では,QSVTの性能を最小限のオーバーヘッドで一致させる古典的アルゴリズムを提案する。
本研究は,レグレッションシステムのための [CGL+'20,SM'21,GST'22,CCH+'22,レコメンデーションシステムのための [Tan'19,CGL+'20,CCH+'22] など,特定の問題に特化したいくつかの論文を改善した。
- 参考スコア(独自算出の注目度): 3.883460584034766
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum machine learning (QML) has shown great potential to produce killer
applications of quantum computers by introducing the possibility of large
quantum speedups for computationally intensive linear algebra tasks. The
quantum singular value transformation (QSVT), introduced by Gily\'en, Su, Low
and Wiebe, is a unifying framework to obtain QML algorithms. We provide a
classical algorithm that matches the performance of QSVT, up to a small
polynomial overhead. In particular, given a bounded matrix
$A\in\mathbb{C}^{m\times n}$, a vector $b\in\mathbb{C}^{n}$, and a bounded
degree-$d$ polynomial $p$, QSVT can output a measurement from the state
$|p(A)b\rangle$ in $O(d\|A\|_F )$ time. We show that for any $\epsilon >0$, we
can output a vector $v$ such that $\|v-p(A)b\|\le\epsilon$ in
$O(d^9\|A\|_F^4/\epsilon^2)$ time after linear-time pre-processing. This
improves upon the best known classical algorithm [CGL+'20], which requires
$O(d^{22}\|A\|_F^6/\epsilon^6)$ time.
Instantiating our algorithm with different polynomials, we obtain fast
quantum-inspired algorithms for regression/matrix inversion, recommendation
systems and Hamiltonian simulation. We improve upon several recent papers
specialized to specific problems, including [CGL+'20,SM'21,GST'22,CCH+'22} for
regression, and [Tan'19,CGL+'20,CCH+'22] for recommendation systems. Our key
insight is to combine the Clenshaw recurrence, an iterative method for
computing matrix polynomials, with sketching techniques to simulate QSVT
classically. The tools we introduce include (a) a non-oblivious matrix sketch
for approximately preserving bi-linear forms, (b) a non-oblivious asymmetric
approximate matrix product sketch based on $\ell_2^2$ sampling, (c) a new
stability analysis for the Clenshaw recurrence, and (d) a new technique to
bound arithmetic progressions of the coefficients appearing in the Chebyshev
expansion of bounded functions.
- Abstract(参考訳): 量子機械学習(QML)は、計算集約線形代数タスクのための大きな量子スピードアップを導入することで、量子コンピュータのキラー応用を生み出す大きな可能性を示している。
Gily\'en, Su, Low, Wiebeによって導入された量子特異値変換(QSVT)は、QMLアルゴリズムを得るための統一フレームワークである。
そこで本研究では,QSVTの性能を,多項式オーバーヘッドを小さくする古典的アルゴリズムを提案する。
特に、有界行列 $a\in\mathbb{c}^{m\times n}$、ベクトル $b\in\mathbb{c}^{n}$、および有界次数-$d$多項式 $p$ が与えられると、qsvt は$o(d\|a\|_f )$ time における$|p(a)b\rangle$ の状態から測定値を出力することができる。
任意の$\epsilon > 0$ に対して、ベクトル $v$ を$\|v-p(A)b\|\le\epsilon$ in $O(d^9\|A\|_F^4/\epsilon^2)$ が線形時間前処理の後に出力できることを示す。
これは最もよく知られた古典的アルゴリズム [cgl+'20] によって改善され、これには$o(d^{22}\|a\|_f^6/\epsilon^6)$時間が必要である。
アルゴリズムを異なる多項式でインスタンス化し,回帰・行列反転,レコメンデーションシステム,ハミルトニアンシミュレーションのための高速量子インスパイアアルゴリズムを得る。
cgl+'20,sm'21,gst'22,cch+'22},[tan'19,cgl+'20,cch+'22]などの特定の問題に特化した最近の論文を改善した。
我々の重要な洞察は、行列多項式の反復的計算法であるクレンショー繰り返しと、QSVTを古典的にシミュレートするスケッチ技法を組み合わせることである。
私たちが紹介するツールは
(a)双線型形式をほぼ保存するための非聖書行列スケッチ
(b)$\ell_2^2$サンプリングに基づく非聖書非対称近似行列のスケッチ
(c)クレンショー再発に対する新しい安定性解析、及び
(d) 有界関数のチェビシェフ展開に現れる係数の算術的進行を有界化する新しい手法。
関連論文リスト
- 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) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳(メタデータ) (2023-07-13T08:46:19Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳(メタデータ) (2023-01-04T04:15:40Z) - Quantum Speedups of Optimizing Approximately Convex Functions with
Applications to Logarithmic Regret Stochastic Convex Bandits [8.682187438614296]
量子アルゴリズムは、$F(x*)-min_xincal K F(x)leqepsilon$が$tildeO(n3)$が$F$となるような$x*incal K$を求める。
応用として、ゼロ階凸包帯に対して $tildeO(n5log2 T)$ regret の量子関数アルゴリズムを与える。
論文 参考訳(メタデータ) (2022-09-26T03:19:40Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳(メタデータ) (2022-01-31T22:19:49Z) - Quantum algorithms for spectral sums [79.28094304325116]
対称正定値行列(SPD)の最も一般的なスペクトル和を推定するための新しい量子アルゴリズムを提案し,解析する。
関数 $f$ と行列 $A に対して、スペクトル和は $S_f(A) :=textTr[f(A)] = sum_j f(lambda_j)$, ここで $lambda_j$ は固有値である。
論文 参考訳(メタデータ) (2020-11-12T16:29:45Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳(メタデータ) (2020-09-29T18:48:21Z) - An improved quantum-inspired algorithm for linear regression [15.090593955414137]
量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。
量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
論文 参考訳(メタデータ) (2020-09-15T17:58:25Z) - Variational Quantum Linear Solver [0.3774866290142281]
本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。
リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
論文 参考訳(メタデータ) (2019-09-12T17:28:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。