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

arXiv: https://arxiv.org/abs/1811.00414 · HTML: https://mlsanity.com/paper/1811.00414/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2018.

## Built on by (most cited first, 30 of 34)

- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Towards provably efficient quantum algorithms for large-scale machine-learning models](https://mlsanity.com/paper/2303.03428/) (2023)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance](https://mlsanity.com/paper/2401.11351/) (2024)
- [Entangled Datasets for Quantum Machine Learning](https://mlsanity.com/paper/2109.03400/) (2021)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Fock State-enhanced Expressivity of Quantum Machine Learning Models](https://mlsanity.com/paper/2107.05224/) (2021)
- [Quantum Transformer: Accelerating model inference via quantum linear algebra](https://mlsanity.com/paper/2402.16714/) (2024)
- [A unifying framework for differentially private quantum algorithms](https://mlsanity.com/paper/2307.04733/) (2023)
- [Quantum State Tomography using Quantum Machine Learning](https://mlsanity.com/paper/2308.10327/) (2023)
- [Differential Privacy Amplification in Quantum and Quantum-inspired Algorithms](https://mlsanity.com/paper/2203.03604/) (2022)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [Quantum computing and artificial intelligence: status and perspectives](https://mlsanity.com/paper/2505.23860/) (2025)
- [Topological data analysis on noisy quantum computers](https://mlsanity.com/paper/2209.09371/) (2022)
- [Diffusion Models for Earth Observation Use-cases: from cloud removal to urban change detection](https://mlsanity.com/paper/2311.06222/) (2023)
- [Entanglement-induced provable and robust quantum learning advantages](https://mlsanity.com/paper/2410.03094/) (2024)
- [Quantum Capsule Networks](https://mlsanity.com/paper/2201.01778/) (2022)
- [Provably efficient variational generative modeling of quantum many-body systems via quantum-probabilistic information geometry](https://mlsanity.com/paper/2206.04663/) (2022)
- [Deep Crowd Anomaly Detection: State-of-the-Art, Challenges, and Future Research Directions](https://mlsanity.com/paper/2210.13927/) (2022)
- [Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms](https://mlsanity.com/paper/2304.04932/) (2023)
- [Quantum Machine Learning For Classical Data](https://mlsanity.com/paper/2105.03684/) (2021)
- [Covariance matrix preparation for quantum principal component analysis](https://mlsanity.com/paper/2204.03495/) (2022)
- [A Quantum Approximation Scheme for k-Means](https://mlsanity.com/paper/2308.08167/) (2023)
- [Data is often loadable in short depth: Quantum circuits from tensor networks for finance, images, fluids, and proteins](https://mlsanity.com/paper/2309.13108/) (2023)
- [Assessing Quantum Advantage for Gaussian Process Regression](https://mlsanity.com/paper/2505.22502/) (2025)
- [Empowering Credit Scoring Systems with Quantum-Enhanced Machine Learning](https://mlsanity.com/paper/2404.00015/) (2024)
- [Advances in Machine Learning: Where Can Quantum Techniques Help?](https://mlsanity.com/paper/2507.08379/) (2025)
- [Multi-channel convolutional neural quantum embedding](https://mlsanity.com/paper/2509.22355/) (2025)
- [Filtered Spectral Projection for Quantum Principal Component Analysis](https://mlsanity.com/paper/2603.13441/) (2026)
- [Quantum Machine Learning for Remote Sensing: Exploring potential and challenges](https://mlsanity.com/paper/2311.07626/) (2023)

## Abstract (arXiv)

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 ℓ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.