論文の概要: An Improved Classical Singular Value Transformation for Quantum Machine
Learning
- arxiv url: http://arxiv.org/abs/2303.01492v3
- Date: Thu, 3 Aug 2023 05:46:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-04 17:17:44.886490
- Title: An Improved Classical Singular Value Transformation for Quantum Machine
Learning
- Title(参考訳): 量子機械学習のための古典特異値変換の改良
- Authors: Ainesh Bakshi and Ewin Tang
- Abstract要約: 量子機械学習(QML)における量子スピードアップについて,量子特異値変換(QSVT)フレームワークを解析して検討する。
我々の重要な洞察は、行列安定性を計算するための反復的手法であるClenshaw繰り返しと、QSVTを古典的にシミュレートするスケッチ技術を組み合わせることである。
- 参考スコア(独自算出の注目度): 3.883460584034766
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study quantum speedups in quantum machine learning (QML) by analyzing the
quantum singular value transformation (QSVT) framework. QSVT, introduced by
[GSLW, STOC'19, arXiv:1806.01838], unifies all major types of quantum speedup;
in particular, a wide variety of QML proposals are applications of QSVT on
low-rank classical data. We challenge these proposals by providing a classical
algorithm that matches the performance of QSVT in this regime up to a small
polynomial overhead.
We show that, given a matrix $A \in \mathbb{C}^{m\times n}$, a vector $b \in
\mathbb{C}^{n}$, a bounded degree-$d$ polynomial $p$, and linear-time
pre-processing, we can output a description of a vector $v$ such that $\|v -
p(A) b\| \leq \varepsilon\|b\|$ in $\widetilde{\mathcal{O}}(d^{11}
\|A\|_{\mathrm{F}}^4 / (\varepsilon^2 \|A\|^4 ))$ time. This improves upon the
best known classical algorithm [CGLLTW, STOC'20, arXiv:1910.06151], which
requires $\widetilde{\mathcal{O}}(d^{22} \|A\|_{\mathrm{F}}^6 /(\varepsilon^6
\|A\|^6 ) )$ time, and narrows the gap with QSVT, which, after linear-time
pre-processing to load input into a quantum-accessible memory, can estimate the
magnitude of an entry $p(A)b$ to $\varepsilon\|b\|$ error in
$\widetilde{\mathcal{O}}(d\|A\|_{\mathrm{F}}/(\varepsilon \|A\|))$ time.
Our key insight is to combine the Clenshaw recurrence, an iterative method
for computing matrix polynomials, with sketching techniques to simulate QSVT
classically. We introduce several new classical techniques in this work,
including (a) a non-oblivious matrix sketch for approximately preserving
bi-linear forms, (b) a new stability analysis for the Clenshaw recurrence, and
(c) 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)において量子特異値変換(QSVT)フレームワークを解析することにより量子スピードアップを研究する。
GSLW, STOC'19, arXiv:1806.01838]によって導入されたQSVTは、全ての主要な量子スピードアップを統一する。
本稿では,この方式におけるQSVTの性能を,多項式オーバーヘッドを小さくする古典的アルゴリズムを提供することにより,これらの提案に挑戦する。
行列 $a \in \mathbb{c}^{m\times n}$, a vector $b \in \mathbb{c}^{n}$, a bounded degree-$d$ polynomial $p$, and linear-time pre-processing が与えられると、$\|vp(a) b\| \leq \varepsilon\|b\|$ in $\widetilde{\mathcal{o}}(d^{11} \|a\|_{\mathrm{f}}^4 / (\varepsilon^2 \|a\|^4 )$ time となるベクトル $v$ の記述を出力することができる。
CGLLTW, STOC'20, arXiv:1910.06151], $\widetilde{\mathcal{O}}(d^{22} \|A\|_{\mathrm{F}}^6 /(\varepsilon^6 \|A\|^6 ) )$ timeで改善され、量子アクセス可能なメモリに入力をロードするための線形時間前処理の後、$$p(A)b$から$\varepsilon\|b\|$の誤差を$\widetilde{\mathcal{O}}(d^{22} \|A\|_{\mathrm{F}}/(\varepsilon^6 \|A\|^6 )$ timeで推定できるQSVTとのギャップを狭める。
我々の重要な洞察は、行列多項式の反復的計算法であるクレンショー繰り返しと、QSVTを古典的にシミュレートするスケッチ技法を組み合わせることである。
我々は、この作品にいくつかの新しい古典的技法を導入する。
(a)双線型形式をほぼ保存するための非聖書行列スケッチ
b) clenshaw 再発に対する新しい安定性解析,および
(c) 有界関数のチェビシェフ級数展開に現れる係数の算術進行を有界化するための新しい手法。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。