Improved quantum algorithm for A-optimal projection

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[kappa(4s)root k(s)/epsilon(s) polylog(s)(mn/epsilon)], where K 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 E 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[s kappa(6)root k/epsilon polylog(mn/epsilon) + s(2)kappa(4)/epsilon polylog(kappa k/epsilon)] and space complexity O[log(2) (nk/kappa) 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 kappa, k, and 1/epsilon are O[polylog(nm)].