Quantum-inspired classical algorithms for principal component analysis and supervised clustering.
Ewin Tang · arXiv (Cornell University) · 2018
We describe classical analogues to Lloyd et al.'s quantum algorithms for principal component analysis and nearest-centroid clustering. We introduce a classical algorithm model that assumes we can efficiently perform $\ell^2$-norm samples of input data, a natural analogue to quantum algorithms assuming efficient state preparation. In this model, our classical algorithms run in time polylogarithmic in input size, matching the runtime of the quantum algorithms with only polynomial slowdown. These algorithms indicate that their corresponding problems do not yield exponential quantum speedups.