Quantum ML

Quantum Principal Component Analysis

Quantum speedups for PCA

Quantum Principal Component Analysis leverages quantum algorithms to extract the principal components of a density matrix exponentially faster than classical PCA for low-rank approximations. By treating the covariance matrix as a quantum state, QPCA can reveal dominant eigenvectors and eigenvalues using quantum phase estimation.

Quantum Phase Estimation for PCA

Classical Principal Component Analysis requires computing the eigenvalues and eigenvectors of the covariance matrix Σ = E[(x - μ)(x - μ)ᵀ], an operation that costs O(d³) for d-dimensional data. For large datasets, this becomes prohibitive. Quantum PCA offers a potential exponential speedup by encoding the covariance matrix into a quantum state and using quantum phase estimation to read out its spectral properties.

The key insight is that if the data distribution is encoded as a quantum state ρ = Σ / tr(Σ), then simulating the unitary e^(-iρt) and applying quantum phase estimation yields the eigenvalues λ_j of ρ. The corresponding eigenvectors can be accessed by performing measurements in the eigenbasis. Because quantum phase estimation runs in time polynomial in the number of qubits and the desired precision, the overall complexity can be logarithmic in the dimension d.

Density matrix exponentiation is the subroutine that implements e^(-iρt) given multiple copies of the state ρ. By performing partial swap operations between the input state and ancilla registers prepared in ρ, one can effectively simulate the evolution under the Hamiltonian defined by ρ itself. The number of copies required scales as O(t² / ε) for precision ε, making the procedure efficient when many copies of the quantum dataset are available.

\rho = \frac{\Sigma}{\text{tr}(\Sigma)}

Density matrix

U = e^{-i \rho t}

Unitary evolution

\rho |v_j\rangle = \lambda_j |v_j\rangle, \quad \text{QPE}(U) |v_j\rangle |0\rangle = |v_j\rangle |\tilde{\lambda}_j\rangle

Phase estimation

•State Encoding: The normalized covariance matrix is treated as a density matrix ρ, which can be prepared via quantum RAM or by tracing out ancilla qubits in a purified state.
•Density Matrix Exponentiation: The operation e^(-iρt) is performed using multiple copies of ρ and repeated partial swaps, avoiding explicit classical matrix exponentiation.
•Low-Rank Advantage: QPCA is most powerful when the data has low effective rank, because the dominant eigenvalues can be estimated with fewer phase-estimation bits and fewer copies of ρ.
•Output Format: Rather than returning full classical eigenvectors, QPCA produces quantum states proportional to the principal components, suitable for downstream quantum algorithms.

Algorithmic Advantages and Limitations

The theoretical speedup of quantum PCA is compelling: for a d-dimensional dataset with rank r, classical PCA costs O(d² r) or O(d³) in the general case, while quantum PCA can run in O(log(d) r² / ε³) under idealized assumptions. This exponential separation in dimensionality suggests that quantum computers could analyze high-dimensional data—such as genomic sequences, high-resolution images, or financial portfolios—far beyond classical reach.

However, several caveats temper this optimism. First, preparing the quantum state ρ from classical data may require quantum RAM or specialized state-preparation circuits whose complexity depends on the data structure. Second, reading out the full eigenvectors classically still requires O(d) measurements, negating the exponential speedup if a classical description is needed. Third, current quantum hardware is limited to small qubit counts and significant noise, restricting practical QPCA to toy problems or hybrid approximations.

Despite these challenges, quantum PCA remains a landmark algorithm in quantum machine learning. It demonstrates that even linear algebra tasks, the workhorses of classical data science, can be reimagined through the lens of quantum computation. Variants such as quantum autoencoders and quantum singular value decomposition extend these ideas to broader unsupervised learning settings, paving the way for a future where quantum and classical data analysis pipelines are tightly integrated.

T_{QPCA} = O\left( \frac{\log(d) \cdot r^2}{\epsilon^3} \right)

Complexity

\Sigma = \mathbb{E}[(x - \mu)(x - \mu)^T]

Covariance matrix

•Logarithmic Dimension: The quantum runtime depends polylogarithmically on the data dimension d, an exponential improvement over classical methods for high-dimensional inputs.
•State Preparation Cost: The speedup assumes efficient quantum access to the data. Without quantum RAM, the cost of loading classical data may dominate the algorithmic gains.
•Readout Overhead: Extracting a classical description of an eigenvector requires O(d) measurements, so QPCA is best used as a quantum subroutine rather than a standalone classical tool.
•NISQ Variants: Near-term approximations use variational circuits to compress data onto fewer qubits, trading asymptotic guarantees for hardware feasibility.

Code in Action

Runnable implementations you can copy and experiment with.

Qiskit Quantum PCA via Density Matrix

This Qiskit example prepares an entangled two-qubit state, computes its density matrix, and extracts the eigenvalues of the reduced density matrix as a proxy for principal components.

quantum_pca_qiskit.py

from qiskit import QuantumCircuit
from qiskit.quantum_info import DensityMatrix, partial_trace
import numpy as np

# Prepare a correlated quantum state
qc = QuantumCircuit(2)
qc.h(0)
qc.cx(0, 1)
rho = DensityMatrix(qc)

# Reduced density matrix for qubit 0
rho_0 = partial_trace(rho, [1])
eigvals, eigvecs = np.linalg.eigh(rho_0.data)
print("Eigenvalues (principal components):", np.round(eigvals, 4))
print("Eigenvectors:", np.round(eigvecs, 4))

PennyLane Quantum PCA with Density Matrix

This PennyLane example prepares a Bell-like state and returns the full two-qubit density matrix. The eigenvalues and eigenvectors are computed classically to reveal the principal components of the quantum correlation structure.

quantum_pca_pennylane.py

import pennylane as qml
import pennylane.numpy as np

dev = qml.device("default.qubit", wires=2)

@qml.qnode(dev)
def prepare_bell_state():
    qml.Hadamard(wires=0)
    qml.CNOT(wires=[0, 1])
    return qml.density_matrix(wires=[0, 1])

rho = prepare_bell_state()
eigvals, eigvecs = np.linalg.eigh(rho)
print("Eigenvalues:", np.round(eigvals, 4))
print("Principal component:", np.round(eigvecs[:, -1], 4))

Explore next

Quantum Phase Estimation

Explore next

Quantum Support Vector Machine

from qiskit import QuantumCircuit from qiskit.quantum_info import DensityMatrix, partial_trace import numpy as np # Prepare a correlated quantum state qc = QuantumCircuit(2) qc.h(0) qc.cx(0, 1) rho = DensityMatrix(qc) # Reduced density matrix for qubit 0 rho_0 = partial_trace(rho, [1]) eigvals, eigvecs = np.linalg.eigh(rho_0.data) print("Eigenvalues (principal components):", np.round(eigvals, 4)) print("Eigenvectors:", np.round(eigvecs, 4))

import pennylane as qml import pennylane.numpy as np dev = qml.device("default.qubit", wires=2) @qml.qnode(dev) def prepare_bell_state(): qml.Hadamard(wires=0) qml.CNOT(wires=[0, 1]) return qml.density_matrix(wires=[0, 1]) rho = prepare_bell_state() eigvals, eigvecs = np.linalg.eigh(rho) print("Eigenvalues:", np.round(eigvals, 4)) print("Principal component:", np.round(eigvecs[:, -1], 4))