論文の概要: 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) 有界関数のチェビシェフ展開に現れる係数の算術的進行を有界化する新しい手法。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。