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

Abstract

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.

6 pages + 7 pages (supplemental material). Title used to be "Quantum-inspired classical algorithms for principal component analysis and supervised clustering"

References in corpus (9)

• The density-matrix renormalization group in the age of matrix product states
• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Matrix product states represent ground states faithfully
• Quantum Data Fitting
• Sketching as a Tool for Numerical Linear Algebra
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum-inspired algorithms in practice
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning

Cited by in corpus (69)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum advantage in learning from experiments
• Quantum Machine Learning for Chemistry and Physics
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Quantum-inspired algorithms in practice
• Noisy intermediate-scale quantum computers
• Neutral Atom Quantum Computing Hardware: Performance and End-User Perspective
• q-means: A quantum algorithm for unsupervised machine learning
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Towards provably efficient quantum algorithms for large-scale machine-learning models
• Quantum Algorithms for Deep Convolutional Neural Networks
• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ansätze
• An improved quantum-inspired algorithm for linear regression
• Configurable sublinear circuits for quantum state preparation
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Practical Quantum K-Means Clustering: Performance Analysis and Applications in Energy Grid Classification
• Double sparse quantum state preparation
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Fock State-enhanced Expressivity of Quantum Machine Learning Models
• Quantum Mixed State Compiling
• Quantum Capsule Networks
• Entangled Datasets for Quantum Machine Learning
• Quantum State Tomography using Quantum Machine Learning
• Sublinear quantum algorithms for training linear and kernel-based classifiers
• Quantum kernels to learn the phases of quantum matter
• How quantum computing can enhance biomarker discovery
• Potential quantum advantage for simulation of fluid dynamics
• Fast Quantum Algorithms for Trace Distance Estimation
• Dequantizing quantum machine learning models using tensor networks
• Quantum advantage for differential equation analysis
• Quantum-Inspired Classical Algorithms for Singular Value Transformation
• Quantum Expectation-Maximization for Gaussian Mixture Models
• "Quantum supremacy" revisited: Low-complexity, deterministic solutions of the original Deutsch-Jozsa problem in classical physical systems
• Entanglement-induced provable and robust quantum learning advantages
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Quantum algorithms for escaping from saddle points
• Qudit Machine Learning
• Quantum and Quantum-Inspired Stereographic K Nearest-Neighbour Clustering
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• Quantum data encoding as a distinct abstraction layer in the design of quantum circuits
• Quantum-inspired canonical correlation analysis for exponentially large dimensional data
• An HHL-Based Algorithm for Computing Hitting Probabilities of Quantum Random Walks
• Sparse random Hamiltonians are quantumly easy
• Coherence Fraction in Grover Search Algorithm
• Partition Function Estimation: Quantum and Quantum-Inspired Algorithms
• Quantum Computing for Data Centric Engineering and Science
• Experimental Virtual Quantum Broadcasting
• Sample-based Hamiltonian and Lindbladian simulation: Non-asymptotic analysis of sample complexity
• $T$-depth-optimized Quantum Search with Quantum Data-access Machine
• Quantum-Inspired Classical Algorithm for Principal Component Regression
• Efficient explicit circuit for quantum state preparation of piecewise continuous functions
• Quantum evolution kernel : Machine learning on graphs with programmable arrays of qubits
• A quantum-inspired algorithm for approximating statistical leverage scores
• Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
• A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices
• Quantum-inspired protocol for measuring the degree of similarity between spatial shapes
• Optimal Qubit Mapping Search for Encoding Classical Data into Matrix Product State Representation with Minimal Loss
• Quantum circuit-like learning: A fast and scalable classical machine-learning algorithm with similar performance to quantum circuit learning
• Quantum-Inspired Classical Algorithm for Slow Feature Analysis
• Finding eigenvectors with a quantum variational algorithm
• Lower bounds for quantum-inspired classical algorithms via communication complexity
• Ensuring superior learning outcomes and data security for authorized learner
• Multi-channel convolutional neural quantum embedding
• Sample-size-reduction of quantum states for the noisy linear problem
• Quantum Machine Learning For Classical Data
• Quantum Computation
• Exponentially accelerated relaxation and quantum Mpemba effect in open quantum systems