Improved quantum algorithm for A-optimal projection

Abstract

Dimensionality reduction algorithms, which reduce the dimensionality of a given data set whereas preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan 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 the algorithm of Duan et al. to $O\left[\frac{{\ensuremath{\kappa}}^{4s}\sqrt{{k}^{s}}}{{\ensuremath{\epsilon}}^{s}}{\mathrm{polylog}}^{s}\left(\frac{mn}{\ensuremath{\epsilon}}\right)\right]$, where $\ensuremath{\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 $\ensuremath{\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\left[\frac{s{\ensuremath{\kappa}}^{6}\sqrt{k}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{nm}{\ensuremath{\epsilon}}\right)+\frac{{s}^{2}{\ensuremath{\kappa}}^{4}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{\ensuremath{\kappa}k}{\ensuremath{\epsilon}}\right)\right]$ and space complexity $O[{log}_{2}(nk/\ensuremath{\epsilon})+s]$. With space complexity slightly worse, our algorithm achieves, at least, a polynomial speedup compared to the algorithm of Duan et al.. Also, our algorithm shows exponential speedups in $n$ and $m$ compared with the classical algorithm when $\ensuremath{\kappa},\phantom{\rule{0.28em}{0ex}}k$, and $1/\ensuremath{\epsilon}$ are $O[\mathrm{polylog}(nm)]$.

Topics & Concepts