論文の概要: 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) 有界関数のチェビシェフ級数展開に現れる係数の算術進行を有界化するための新しい手法。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。