Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions

Understand

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.