Quantum Principal Component Analysis Only Achieves an Exponential Speedup Because of Its State Preparation Assumptions

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 2019.], we introduce such a model, where we assume we can efficiently perform {\ensuremath{\ell}}^{2}norm samples of input data, a natural analog to quantum algorithms that assume efficient state preparation of classical data. Though this model produces...