論文の概要: An Improved Classical Singular Value Transformation for Quantum Machine
Learning
- arxiv url: http://arxiv.org/abs/2303.01492v2
- Date: Mon, 6 Mar 2023 07:15:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 12:20:24.322969
- Title: An Improved Classical Singular Value Transformation for Quantum Machine
Learning
- Title（参考訳）: 量子機械学習のための古典特異値変換の改良
- Authors: Ainesh Bakshi and Ewin Tang
- Abstract要約: 低ランク入力におけるQSVTの性能を最小限のオーバーヘッドでマッチングする古典的アルゴリズムを提案する。
我々は、回帰、レコメンデーションシステム、ハミルトンシミュレーションのための高速量子インスピレーションアルゴリズムを得る。
- 参考スコア（独自算出の注目度）: 3.883460584034766
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum machine learning (QML) has shown great potential to produce large
quantum speedups for linear algebra tasks. The quantum singular value
transformation (QSVT), introduced by [GSLW, STOC'19, arXiv:1806.01838], is a
unifying framework to obtain QML algorithms. We provide a classical algorithm
that matches the performance of QSVT on low-rank inputs, up to small polynomial
overhead. Under quantum memory assumptions, given a bounded matrix
$A\in\mathbb{C}^{m\times n}$, vector $b\in\mathbb{C}^{n}$, and bounded
degree-$d$ polynomial $p$, QSVT can output a measurement from the state
$|p(A)b\rangle$ in $O(d\|A\|_F)$ time after linear-time pre-processing. We show
that, in the same setting, for any $\varepsilon>0$, we can output a vector $v$
such that $\|v - p(A) b\|\leq\varepsilon\|b\|$ in
$O(d^9\|A\|_F^4/\varepsilon^2)$ time after linear-time pre-processing. This
improves upon the best known classical algorithm [CGLLTW, STOC'20,
arXiv:1910.06151], which requires $O(d^{22}\|A\|_F^6/\varepsilon^6)$ time.
Instantiating the aforementioned algorithm with different polynomials, we
obtain fast quantum-inspired algorithms for regression, recommendation systems,
and Hamiltonian simulation. We improve in numerous parameter settings on prior
work, including those that use problem-specialized approaches. 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 in this work include (a) a matrix sketch for approximately
preserving bi-linear forms, (b) an 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 series expansion of bounded functions,
each of which may be of independent interest.
- Abstract（参考訳）: 量子機械学習(QML)は線形代数問題に対して大きな量子スピードアップを生み出す大きな可能性を示している。
GSLW, STOC'19, arXiv:1806.01838] によって導入された量子特異値変換(QSVT)は、QMLアルゴリズムを得るための統一フレームワークである。
低ランク入力におけるQSVTの性能を,多項式オーバーヘッドを小さくする古典的アルゴリズムを提案する。
量子メモリの仮定の下では、有界行列 $a\in\mathbb{c}^{m\times n}$, vector $b\in\mathbb{c}^{n}$, and bounded degree-$d$ polynomial $p$, qsvt は線形時間前処理後に$|p(a)b\rangle$ in $o(d\|a\|_f)$ time から測定値を出力することができる。
同じ設定で、任意の$\varepsilon>0$に対して、$\|v - p(A) b\|\leq\varepsilon\|b\|$ in $O(d^9\|A\|_F^4/\varepsilon^2)$ を線形時間前処理の後に出力できる。
これは、$O(d^{22}\|A\|_F^6/\varepsilon^6)$timeを必要とする最もよく知られた古典的アルゴリズム [CGLLTW, STOC'20, arXiv:1910.06151] により改善される。
上記のアルゴリズムを異なる多項式で検証し、回帰、レコメンデーションシステム、ハミルトニアンシミュレーションのための高速量子インスピレーションアルゴリズムを得る。
我々は,問題特化アプローチを含む,先行作業における多数のパラメータ設定を改善した。
我々の重要な洞察は、行列多項式の反復的計算法であるクレンショー繰り返しと、QSVTを古典的にシミュレートするスケッチ技法を組み合わせることである。
この作業で導入されたツールは、
(a)双線型形式をほぼ保存するためのマトリクススケッチ
(b)$\ell_2^2$サンプリングに基づく非対称近似行列積のスケッチ
(c)クレンショー再発に対する新しい安定性解析、及び
(d) 有界関数のチェビシェフ級数展開に現れる係数の算術進行を有界化するための新しい手法。
関連論文リスト
- A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - 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) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。