Quantum Algorithms Database
Quantum Principal Component Analysis
A quantum algorithm for identifying the dominant patterns (principal components) in data, with potential exponential speedup under specific conditions.
Year
2014
Inventor(s)
Lloyd, Mohseni & Rebentrost
Speedup Type
Exponential Speedup
Difficulty
★★★★★
The Problem
Finding the most significant directions of variation in high-dimensional data — a fundamental task in data analysis and machine learning.
How It Works
Uses quantum phase estimation on a density matrix representing the data to extract eigenvalues and eigenvectors corresponding to principal components.
Real-World Impact
Largely theoretical at present — requires efficient quantum state preparation from classical data, which remains a significant practical bottleneck (sometimes called the 'input problem').