QPE-Based Learning

QPE-Based Learning#

Using quantum phase estimation for eigenvalue problems in ML: principal component analysis, recommendation systems.

Quantum phase estimation (QPE) is a fundamental subroutine that extracts eigenvalues of unitary operators. When combined with Hamiltonian simulation, QPE enables quantum algorithms for principal component analysis, recommendation systems, and other eigenvalue-based ML methods with exponential speedups under specific conditions. These algorithms require fault-tolerant quantum computers but represent some of the strongest theoretical results in QML.

Quantum Phase Estimation#

Given a unitary \(U\) with eigenvector \(|u\rangle\) and eigenvalue \(e^{2\pi i \varphi}\), QPE estimates the phase \(\varphi\) to \(t\) bits of precision.

Algorithm Steps#

Prepare \(t\) ancilla qubits in \(|0\rangle\) and the target register in \(|u\rangle\).
Apply Hadamard gates to all ancilla qubits.
Apply controlled-\(U^{2^j}\) from ancilla qubit \(j\) to the target register, for \(j = 0, 1, \ldots, t-1\).
Apply the inverse Quantum Fourier Transform (QFT\(^\dagger\)) to the ancilla register.
Measure the ancilla register to obtain a \(t\)-bit approximation of \(\varphi\).

The output state before measurement is approximately:

\[|\tilde{\varphi}\rangle|u\rangle\]

where \(\tilde{\varphi}\) is the \(t\)-bit binary representation of \(\varphi\). The success probability is at least \(4/\pi^2 \approx 0.405\) for obtaining the best \(t\)-bit approximation, and can be boosted to \(1 - \epsilon\) with \(O(\log(1/\epsilon))\) additional ancilla qubits.

Complexity#

QPE requires \(O(2^t)\) applications of controlled-\(U\). The precision scales as \(|\varphi - \tilde{\varphi}| \leq 2^{-t}\). When \(U = e^{-iHt}\) for a Hamiltonian \(H\), the eigenvalues of \(H\) are extracted as phases.

Quantum PCA#

Classical PCA computes the eigendecomposition of the covariance matrix \(\Sigma = \frac{1}{N}\sum_i \mathbf{x}_i \mathbf{x}_i^T\) and projects data onto the top eigenvectors. For a \(d \times d\) covariance matrix, classical eigendecomposition costs \(O(d^3)\).

Quantum Algorithm (Lloyd, Mohseni, Rebentrost 2014)#

Quantum PCA achieves an exponential speedup under specific conditions:

Input: Multiple copies of the quantum state \(\rho = \sum_i \lambda_i |\lambda_i\rangle\langle\lambda_i|\) (a density matrix encoding the covariance structure).
Density matrix exponentiation: Use copies of \(\rho\) to implement \(e^{-i\rho t}\) via swap operations and partial traces.
Phase estimation: Apply QPE with \(U = e^{-i\rho t}\) to extract eigenvalues \(\lambda_i\).
Output: Eigenvalues and corresponding eigenstates.

The runtime is \(O(\log d)\) in the matrix dimension, an exponential speedup over the classical \(O(d^3)\).

Warning

The exponential speedup assumes quantum access to the data (copies of \(\rho\) prepared by a quantum process). If the data is classical and must be loaded into quantum states, state preparation requires \(O(d)\) operations, which may negate the speedup. This caveat, identified by Tang (2019), led to “dequantized” classical algorithms with similar performance for low-rank data.

Quantum Recommendation Systems#

The quantum recommendation system (Kerenidis and Prakash, 2016) uses QPE to perform low-rank matrix reconstruction exponentially faster than classical SVD.

Problem Setting#

Given a sparse preference matrix \(A\) (users \(\times\) items) with \(m\) entries, recommend items to users by approximating \(A\) with a low-rank matrix \(A_k\) (keeping the top \(k\) singular values).

Quantum Algorithm#

Prepare quantum states encoding rows of \(A\) using QRAM.
Apply QPE to extract singular values and vectors.
Project onto the top-\(k\) subspace.
Sample to obtain recommendations.

Runtime: \(O(\text{poly}(k) \cdot \text{polylog}(mn))\), compared to \(O(mn \cdot k)\) classically.

Dequantization#

Tang (2019) showed that if sampling access to \(A\) is available (the ability to sample rows proportional to their norms), a classical algorithm achieves \(O(\text{poly}(k) \cdot \text{polylog}(mn))\) runtime as well. This dequantization result demonstrated that the quantum advantage came from the input model (QRAM), not from quantum computation per se.

Lessons from dequantization

The dequantization of quantum recommendation systems was a watershed moment for QML. It showed that: (1) quantum speedups must be carefully attributed to quantum computation vs. input model, (2) sampling access can sometimes substitute for quantum superposition, and (3) low-rank structure in the data enables classical algorithms to match quantum performance.

QPE for Kernel Methods#

QPE can accelerate kernel methods by enabling efficient computation of kernel matrices for certain structured kernels:

Spectral kernels: For kernels defined by functions of the eigenvalues of a matrix (e.g., \(k(A) = e^{-\beta A}\)), QPE extracts the eigenvalues and the function is applied coherently.
Graph kernels: Kernels based on the spectrum of graph Laplacians can be computed via QPE on the Laplacian unitary.

Code Examples#

Qiskit

from qiskit.circuit import QuantumCircuit
from qiskit.circuit.library import QFT
import numpy as np

def qpe_circuit(unitary_gate, n_counting=3, n_target=1):
    """Build a QPE circuit."""
    n_total = n_counting + n_target
    qc = QuantumCircuit(n_total, n_counting)

    # Initialize target in eigenstate (|1> for Z gate example)
    qc.x(n_counting)

    # Hadamard on counting qubits
    for i in range(n_counting):
        qc.h(i)

    # Controlled-U^(2^j)
    for j in range(n_counting):
        power = 2 ** j
        for _ in range(power):
            qc.cp(unitary_gate, j, n_counting)

    # Inverse QFT on counting qubits
    qft_inv = QFT(n_counting, inverse=True)
    qc.append(qft_inv, range(n_counting))

    # Measure counting qubits
    qc.measure(range(n_counting), range(n_counting))
    return qc

# QPE for phase gate with phase pi/4
qc = qpe_circuit(np.pi / 4, n_counting=3)
print(qc)

Cirq

import cirq
import numpy as np

def qpe_circuit(phase, n_counting=3):
    counting = cirq.LineQubit.range(n_counting)
    target = cirq.LineQubit(n_counting)
    circuit = cirq.Circuit()

    # Target in eigenstate
    circuit.append(cirq.X(target))

    # Hadamard on counting qubits
    circuit.append(cirq.H.on_each(*counting))

    # Controlled phase gates
    for j in range(n_counting):
        power = 2 ** j
        circuit.append(
            cirq.ControlledGate(cirq.ZPowGate(exponent=power * phase / np.pi))
            .on(counting[j], target)
        )

    # Inverse QFT (simplified)
    for i in range(n_counting):
        for j in range(i):
            circuit.append(
                cirq.CZPowGate(exponent=-1/2**(i-j)).on(counting[j], counting[i])
            )
        circuit.append(cirq.H(counting[i]))

    circuit.append(cirq.measure(*counting, key='phase'))
    return circuit

circuit = qpe_circuit(np.pi / 4)
print(circuit)

PennyLane

import pennylane as qml
from pennylane import numpy as np

n_counting = 3
n_total = n_counting + 1
dev = qml.device("default.qubit", wires=n_total)

@qml.qnode(dev)
def qpe(phase):
    target = n_counting  # last wire

    # Target eigenstate
    qml.PauliX(wires=target)

    # Hadamard on counting qubits
    for i in range(n_counting):
        qml.Hadamard(wires=i)

    # Controlled rotations
    for j in range(n_counting):
        power = 2 ** j
        qml.ControlledPhaseShift(power * phase, wires=[j, target])

    # Inverse QFT
    qml.adjoint(qml.QFT)(wires=range(n_counting))

    return qml.probs(wires=range(n_counting))

phase = np.pi / 4  # eigenvalue e^{i*pi/4}
probs = qpe(phase)
estimated = np.argmax(probs) / 2**n_counting
print(f"True phase/(2pi): {phase/(2*np.pi):.4f}")
print(f"Estimated:        {estimated:.4f}")

PyQuil

from pyquil import Program
from pyquil.gates import H, X, CPHASE, MEASURE
import numpy as np

n_counting = 3
target = n_counting

prog = Program()
ro = prog.declare('ro', 'BIT', n_counting)

# Target eigenstate
prog += X(target)

# Hadamard on counting qubits
for i in range(n_counting):
    prog += H(i)

# Controlled phase rotations
phase = np.pi / 4
for j in range(n_counting):
    power = 2 ** j
    prog += CPHASE(power * phase, j, target)

# Simplified inverse QFT
for i in range(n_counting - 1, -1, -1):
    for j in range(i - 1, -1, -1):
        prog += CPHASE(-np.pi / 2**(i-j), j, i)
    prog += H(i)

for i in range(n_counting):
    prog += MEASURE(i, ro[i])

print(prog)