論文の概要: Quantum machine learning with subspace states
- arxiv url: http://arxiv.org/abs/2202.00054v2
- Date: Wed, 2 Feb 2022 17:54:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 05:05:07.780946
- Title: Quantum machine learning with subspace states
- Title（参考訳）: 部分空間状態を持つ量子機械学習
- Authors: Iordanis Kerenidis and Anupam Prakash
- Abstract要約: 量子部分空間状態に基づく量子線型代数の新しいアプローチを導入し,新しい3つの量子機械学習アルゴリズムを提案する。
1つ目は、分布 $Pr[S]= det(X_SX_ST)$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(dlog n)$である。
2つ目は、複素行列に対して$mathcalAk$の量子特異値推定アルゴリズムであり、このアルゴリズムの高速化は指数関数的である。
- 参考スコア（独自算出の注目度）: 8.22379888383833
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a new approach for quantum linear algebra based on quantum
subspace states and present three new quantum machine learning algorithms. The
first is a quantum determinant sampling algorithm that samples from the
distribution $\Pr[S]= det(X_{S}X_{S}^{T})$ for $|S|=d$ using $O(nd)$ gates and
with circuit depth $O(d\log n)$. The state of art classical algorithm for the
task requires $O(d^{3})$ operations \cite{derezinski2019minimax}. The second is
a quantum singular value estimation algorithm for compound matrices
$\mathcal{A}^{k}$, the speedup for this algorithm is potentially exponential.
It decomposes a $\binom{n}{k}$ dimensional vector of order-$k$ correlations
into a linear combination of subspace states corresponding to $k$-tuples of
singular vectors of $A$. The third algorithm reduces exponentially the depth of
circuits used in quantum topological data analysis from $O(n)$ to $O(\log n)$.
Our basic tool are quantum subspace states, defined as $|Col(X)\rangle =
\sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle$ for matrices $X \in
\mathbb{R}^{n \times d}$ such that $X^{T} X = I_{d}$, that encode
$d$-dimensional subspaces of $\mathbb{R}^{n}$. We develop two efficient state
preparation techniques, the first using Givens circuits uses the representation
of a subspace as a sequence of Givens rotations, while the second uses
efficient implementations of unitaries $\Gamma(x) = \sum_{i} x_{i} Z^{\otimes
(i-1)} \otimes X \otimes I^{n-i}$ with $O(\log n)$ depth circuits that we term
Clifford loaders.
- Abstract（参考訳）: 量子部分空間状態に基づく量子線型代数の新しいアプローチを導入し,新しい3つの量子機械学習アルゴリズムを提案する。
1つ目は、分布 $\Pr[S]= det(X_{S}X_{S}^{T})$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(d\log n)$ からサンプリングする量子行列式サンプリングアルゴリズムである。
このタスクの古典的アルゴリズムは、$O(d^{3})$ operation \cite{derezinski2019minimax} を必要とする。
2つ目は、合成行列 $\mathcal{a}^{k}$ に対する量子特異値推定アルゴリズムであり、このアルゴリズムの高速化は潜在的に指数関数的である。
これは、オーダー-$k$相関の$\binom{n}{k}$ 次元ベクトルを、a$の特異ベクトルの$k$-タプルに対応する部分空間状態の線型結合に分解する。
第3のアルゴリズムは、量子トポロジカルデータ解析で使用される回路の深さを指数関数的に$O(n)$から$O(\log n)$に下げる。
我々の基本的なツールは量子部分空間状態であり、$|Col(X)\rangle = \sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle$ for matrices $X \in \mathbb{R}^{n \times d}$, that $X^{T} X = I_{d}$, which encode $d$-dimensional subspaces of $\mathbb{R}^{n}$と定義される。
1つは与えられた回転の列として部分空間の表現を使い、もう1つはユニタリの効率的な実装である$\gamma(x) = \sum_{i} x_{i} z^{\otimes (i-1)} \otimes x \otimes i^{n-i}$ with $o(\log n)$ depth circuits that we called clifford loaders. である。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Improved quantum data analysis [1.8416014644193066]
我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。
また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
論文 参考訳（メタデータ） (2020-11-22T01:22:37Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Quantum-classical algorithms for skewed linear systems with optimized
Hadamard test [10.386115383285288]
我々は、過度に決定された場合と過度に決定された場合のスキュード線形系に対するハイブリッド量子古典アルゴリズムについて論じる。
我々の入力モデルは、線形系を定義する行列の列または行が多対数深さの量子回路によって与えられるようなものである。
本稿では,各次元における実時間多対数性を持つ分解線形系の特殊ケースに対するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-28T12:59:27Z) - An improved quantum-inspired algorithm for linear regression [15.090593955414137]
量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。
量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-15T17:58:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。