論文の概要: Improved quantum algorithm for A-optimal projection
- arxiv url: http://arxiv.org/abs/2006.05745v2
- Date: Thu, 5 Nov 2020 08:31:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-16 03:02:04.880060
- Title: Improved quantum algorithm for A-optimal projection
- Title（参考訳）: a最適投影のための改良量子アルゴリズム
- Authors: Shi-Jie Pan, Lin-Chun Wan, Hai-Ling Liu, Qing-Le Wang, Su-Juan Qin,
Qiao-Yan Wen and Fei Gao
- Abstract要約: 本稿では、Duan emphet al.のアルゴリズムの時間的複雑さを$(frackappa4ssqrtks epsilonsmathrmpolylog)$に補正する。
我々のアルゴリズムは、Duan emphet al.のアルゴリズムと比較して少なくとも1つのスピードアップを達成する。
- 参考スコア（独自算出の注目度）: 4.248054546466641
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Dimensionality reduction (DR) algorithms, which reduce the dimensionality of
a given data set while preserving the information of the original data set as
well as possible, play an important role in machine learning and data mining.
Duan \emph{et al}. proposed a quantum version of the A-optimal projection
algorithm (AOP) for dimensionality reduction [Phys. Rev. A 99, 032311 (2019)]
and claimed that the algorithm has exponential speedups on the dimensionality
of the original feature space $n$ and the dimensionality of the reduced feature
space $k$ over the classical algorithm. In this paper, we correct the time
complexity of Duan \emph{et al}.'s algorithm to $O(\frac{\kappa^{4s}\sqrt{k^s}}
{\epsilon^{s}}\mathrm{polylog}^s (\frac{mn}{\epsilon}))$, where $\kappa$ is the
condition number of a matrix that related to the original data set, $s$ is the
number of iterations, $m$ is the number of data points and $\epsilon$ is the
desired precision of the output state. Since the time complexity has an
exponential dependence on $s$, the quantum algorithm can only be beneficial for
high dimensional problems with a small number of iterations $s$. To get a
further speedup, we propose an improved quantum AOP algorithm with time
complexity $O(\frac{s \kappa^6
\sqrt{k}}{\epsilon}\mathrm{polylog}(\frac{nm}{\epsilon}) + \frac{s^2
\kappa^4}{\epsilon}\mathrm{polylog}(\frac{\kappa k}{\epsilon}))$ and space
complexity $O(\log_2(nk/\epsilon)+s)$. With space complexity slightly worse,
our algorithm achieves at least a polynomial speedup compared to Duan \emph{et
al}.'s algorithm. Also, our algorithm shows exponential speedups in $n$ and $m$
compared with the classical algorithm when both $\kappa$, $k$ and $1/\epsilon$
are $O(\mathrm{polylog}(nm))$.
- Abstract（参考訳）: 元のデータセットの情報を可能な限り保存しながら、与えられたデータセットの次元性を減少させる次元性低減(DR)アルゴリズムは、機械学習やデータマイニングにおいて重要な役割を果たす。
Duan \emph{et al}。
a-optimal projection algorithm (aop) for dimensionality reduction [phys. rev. a 99, 032311 (2019)] の量子版を提案し、元の特徴空間 $n$ の次元性と縮小された特徴空間 $k$ の次元性に指数関数的なスピードアップがあると主張した。
In this paper, we correct the time complexity of Duan \emph{et al}'s algorithm to $O(\frac{\kappa^{4s}\sqrt{k^s}} {\epsilon^{s}}\mathrm{polylog}^s (\frac{mn}{\epsilon})$, where $\kappa$ is the condition number of a matrix that the original data set, $s$ is the number of iterations, $m$ is the number of data points and $\epsilon$ is the desired precision of the output state。
時間複雑性は$s$に指数関数的に依存するので、量子アルゴリズムは少量の反復が$s$を持つ高次元問題に対してのみ有用である。
さらに高速化するために、時間複雑性$O(\frac{s \kappa^6 \sqrt{k}}{\epsilon}\mathrm{polylog}(\frac{nm}{\epsilon}) + \frac{s^2 \kappa^4}{\epsilon}\mathrm{polylog}(\frac{\kappa k}{\epsilon})$および空間複雑性$O(\log_2(nk/\epsilon)+s)$で改良された量子AOPアルゴリズムを提案する。
空間複雑性が少し悪くなると、我々のアルゴリズムは少なくともDuan \emph{et al}.のアルゴリズムと比較して多項式スピードアップを達成する。
また、このアルゴリズムは、$\kappa$, $k$, $1/\epsilon$が$o(\mathrm{polylog}(nm))$であるとき、従来のアルゴリズムと比較して指数関数的なスピードアップを示す。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - Algorithms for Sparse LPN and LSPN Against Low-noise [1.2143710013809321]
本研究では,古典的学習パリティ(LPN)問題の2つの変種に対する学習アルゴリズムについて検討する。
我々は,幅広いパラメータに対する技術状況を改善するための新しいアルゴリズムフレームワークを提供する。
論文 参考訳（メタデータ） (2024-07-27T08:57:04Z) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。