Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
This work challenges the perceived quantum advantage in machine learning by highlighting that speedups may be incremental and dependent on specific input models, impacting researchers in quantum computing and classical algorithm design.
The paper introduces a classical input model analogous to quantum state preparation, showing that classical algorithms for principal component analysis and nearest-centroid clustering achieve only polynomial slowdown compared to quantum versions, suggesting that quantum exponential speedups are due to input assumptions rather than inherent quantum advantage.
A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Tang, STOC'19], we introduce such a model, where we assume we can efficiently perform $\ell^2$-norm samples of input data, a natural analogue to quantum algorithms that assume efficient state preparation of classical data. Though this model produces less practical algorithms than the (stronger) standard model of classical computation, it captures versions of many of the features and nuances of quantum linear algebra algorithms. With this model, we describe classical analogues to Lloyd, Mohseni, and Rebentrost's quantum algorithms for principal component analysis [Nat. Phys. 10, 631 (2014)] and nearest-centroid clustering [arXiv:1307.0411]. Since they are only polynomially slower, these algorithms suggest that the exponential speedups of their quantum counterparts are simply an artifact of state preparation assumptions.