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$ is the dimension, $t$ is the evolution time and $\epsilon$ is the precision. We improve this result into $O((\log d)t^{ 1+\frac{ 1}{ k}}/\epsilon^{ \frac{ 1}{ k}})$ for arbitrary constant integer $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.
Categories: quant-ph