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
2013 (arXiv); 2014 (Nature Physics)
Inventor(s)
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost
Speedup Type
Exponential Speedup
Difficulty
★★★★★
Overview
Quantum principal component analysis, or qPCA, extracts the dominant eigenvalues and eigenvectors of a density matrix, which plays the role of a covariance matrix in classical PCA. If the data is provided as quantum states, qPCA can find the principal components in time polynomial in the logarithm of the dimension, an exponential speedup over the classical cost, which grows polynomially with the dimension.
The speedup comes with conditions. The data must be available as multiple copies of a quantum state that encodes the covariance matrix, the matrix should be low rank, and the output is a quantum state or a handful of sampled eigenvalues, not the full set of components. Since 2018, classical algorithms with comparable access to the data have matched much of the claimed advantage.
The problem it solves
Finding the most significant directions of variation in high-dimensional data — a fundamental task in data analysis and machine learning.
History and background
Lloyd, Mohseni, and Rebentrost posted the algorithm in 2013 and published it in Nature Physics in 2014, as part of a wave of quantum machine learning proposals that included HHL-based regression and quantum support vector machines. The paper introduced density matrix exponentiation, a method of applying e to the minus i rho t to a state using copies of rho, which has since become a general tool for quantum algorithms.
A first experimental proof of principle used a nuclear magnetic resonance device in 2016 and a photonic experiment followed in 2017 for tiny two-dimensional problems. In 2018 and 2019, Ewin Tang developed quantum-inspired classical algorithms for recommendation systems, principal component analysis, and clustering, showing that with a classical analogue of quantum state access, low-rank data can be handled in time polylogarithmic in the dimension. That result narrowed the scope of the exponential advantage.
How it works
Uses quantum phase estimation on a density matrix representing the data to extract eigenvalues and eigenvectors corresponding to principal components.
In classical PCA, you compute the covariance matrix of the data and find its eigenvectors with the largest eigenvalues. Those directions explain most of the variation in the data. In qPCA, the covariance matrix, normalized to have unit trace, is a density matrix rho, the mathematical object that describes a quantum state.
Quantum phase estimation could reveal the eigenvalues of rho if we could apply the unitary e to the i rho t. This is not an ordinary operation, but it can be approximated using repeated swap operations between a register holding the target state and fresh copies of rho. Each swap applies a small piece of the evolution, and about t squared over epsilon copies produce a unitary with error epsilon. This is density matrix exponentiation.
Using that unitary in phase estimation, the state is projected onto eigenvectors of rho, with probabilities given by the eigenvalues. The largest eigenvalues occur most often, so sampling reveals the principal components, and the post-measurement state is the corresponding eigenvector.
Step by step
- Encode the data's covariance structure as a density matrix rho, for example by preparing random data points as states and tracing out the index, which requires quantum random access to the data.
- Prepare a register in a state on which to run the algorithm, such as a copy of rho itself.
- Apply density matrix exponentiation to approximate e to the minus i rho t, using swap operations between the register and many fresh copies of rho.
- Run quantum phase estimation with this unitary to write eigenvalues of rho into an ancilla register.
- Measure the eigenvalue register to obtain an eigenvalue, which occurs with probability equal to that eigenvalue, and collapse the register into the corresponding eigenvector.
- Repeat to sample the dominant eigenvalues and eigenvectors, then use them for dimension reduction or state classification.
A worked example
Suppose a data set has a million dimensions but is dominated by two directions that explain nearly all variance, so rho has rank close to 2. Classical PCA would compute and diagonalize a matrix with a million rows and columns, or use randomized methods that still scan the data.
The quantum algorithm would run phase estimation on rho and would see one of two large eigenvalues almost every time, with the associated eigenvector left in the register. The cost scales with the logarithm of the dimension, but it requires that the data be loaded into quantum states beforehand, and the result is a quantum state that can only be sampled.
Complexity and resources
| Item | Detail |
|---|---|
| Quantum runtime | O(log d) for dimension d, with copies of rho scaling as t squared over epsilon |
| Classical PCA | Polynomial in d, for example O(d squared) to O(d cubed) for the full matrix |
| Quantum-inspired classical algorithm | Polylogarithmic in d for low-rank data given sampling access, with larger polynomial dependence on rank and error |
| Input assumption | Fast quantum or QRAM access to the data, which is itself costly |
| Output | Quantum states or sampled eigenvalues, not the full components |
What hardware it needs
- Fault-tolerant hardware with a large quantum memory, or QRAM, to prepare the data states.
- Deep circuits for phase estimation and many copies of rho.
- A way to extract useful classical information from the output states.
Applications
- Dimension reduction and feature extraction for large data sets, if state preparation is cheap.
- Analyzing the spectrum of quantum states, such as entanglement spectroscopy and quantum tomography, where data is already quantum.
- Serving as a subroutine in quantum machine learning pipelines such as quantum clustering and classification.
Limitations and caveats
- The exponential speedup is not preserved when the data is classical and must be loaded.
- Quantum-inspired classical algorithms reduce the advantage for low-rank data.
- Outputs are quantum states, so downstream steps must also be quantum or use sampling.
- The cost of QRAM may be prohibitive.
Common misconceptions
- qPCA does not deliver the principal components as a classical list. It yields quantum states and sampled eigenvalues.
- It does not make classical machine learning faster in practice. The theoretical gains depend on assumptions that rarely hold.
How it compares
- Classical randomized PCA scales near-linearly in the number of nonzero entries, which is competitive for most real data.
- HHL shares the input and output limitations and the same dequantization story.
- Quantum kernel methods try to find advantage by exploiting data with quantum structure.
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').
Why it matters
qPCA introduced density matrix exponentiation and led to a rich line of research in quantum machine learning. It is also a case study of how classical researchers can erode a quantum speedup by finding a better algorithm.
For learners, it is a clear example of the importance of the input and output model in judging a quantum algorithm.
Frequently asked questions
What does quantum PCA do?
It finds the principal eigenvalues and eigenvectors of a density matrix, using phase estimation and density matrix exponentiation.
Is it exponentially faster than classical PCA?
In its original model, yes, but under strong assumptions about data access. Quantum-inspired classical algorithms match much of the advantage for low-rank data.
What is density matrix exponentiation?
A technique that applies the unitary e to the i rho t, using swap operations with copies of the state rho, so that rho can be used as a Hamiltonian.
Who dequantized qPCA?
Ewin Tang, in 2018 and 2019, gave classical algorithms with comparable runtime for low-rank problems given sampling access.
Can qPCA run on current hardware?
Only in tiny demonstrations. Real applications need fault tolerance and quantum memory.
Keep learning
- Related algorithm: HHL Algorithm
- Related algorithm: Quantum Phase Estimation (QPE)
- Related algorithm: Quantum Support Vector Machine
- Related algorithm: Quantum k-Means Clustering
This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.