An Improved Algorithm for Quantum Principal Component Analysis

Principal component analysis is an important dimension reduction technique in machine learning. In [S. Lloyd, M. Mohseni and P. Rebentrost, Nature Physics 10, 631-633, (2014)], a quantum algorithm to implement principal component analysis on quantum computer was obtained by computing the Hamiltonian simulation of unknown density operators. The complexity is $O((\log d)t^2/\epsilon)$,where$d$isthedimension,$t$istheevolutiontimeand$\epsilon$istheprecision\mathrm{.}Weimprovethisresultinto$O((\log d)t^{1+\frac{1}{k}}/\epsilon^{\frac{1}{k}})$forarbitraryconstantinteger$k\geq 1$. As a result, we show that the Hamiltonian simulation of low-rank dense Hermitian matrices can be implemented in the same time.