Quantum Numerical Methods

Quantum Linear Systems

The HHL algorithm (Harrow-Hassidim-Lloyd, 2009) solves linear systems on a quantum computer:

1. Encode as a quantum state
2. Use quantum phase estimation to find eigenvalues of
3. Apply controlled rotations to encode
4. Uncompute to obtain

Complexity: where is the condition number and is the precision.

This provides exponential speedup over classical for sparse systems.

Quantum Phase Estimation for Eigenvalues

Quantum phase estimation (QPE) extracts eigenvalues of a unitary :

1. Prepare eigenstate with eigenvalue
2. Apply controlled- operations
3. Inverse QFT to extract

The eigenvalue is encoded in the ancilla register with precision using ancilla qubits.

HHL Algorithm Detail

The HHL algorithm steps:

1. Encode in QPE register
2. QPE extracts eigenvalues into ancilla register
3. Controlled rotation:
4. Uncompute QPE to disentangle ancilla
5. Measure ancilla: if , remaining register is

The algorithm requires qubits and gates for sparse .

Limitations of HHL

HHL limitations:

1. Input encoding: preparing may be as hard as solving
2. Output encoding: result is in quantum state, not classical vector
3. Sparsity requirement: must be efficiently implementable as Hamiltonian
4. Condition number: runtime scales as
5. Non-sparse matrices: not applicable for dense matrices

These limitations mean HHL is not a universal speedup for linear systems.

Variational Quantum Linear Solver

Variational quantum linear solver (VQLS) addresses HHL limitations:

1. Prepare ansatz
2. Minimize
3. Use hybrid quantum-classical optimization

Advantages: no input encoding requirement, NISQ-compatible, no phase estimation needed.

Quantum Algorithms for Differential Equations

Quantum algorithms for ODEs/PDEs:

1. Hamiltonian simulation: evolve
2. Linear systems: solve for differential operators
3. Variational methods: parameterized circuits for PDE solutions

The Schrodinger equation is naturally quantum, giving exponential speedup for quantum simulations.

Python: HHL Simulation

import numpy as np

def hhl_simulation(A, b):
    # Simplified HHL algorithm simulation.
    # Classical simulation of HHL
    # 1. Diagonalize A
    eigenvalues, eigenvectors = np.linalg.eigh(A)

    # 2. Express b in eigenbasis
    b_eig = eigenvectors.conj().T @ b

    # 3. Invert eigenvalues (with regularization)
    epsilon = 1e-10
    inv_eigenvalues = np.where(np.abs(eigenvalues) > epsilon, 1/eigenvalues, 0)

    # 4. Compute x in eigenbasis
    x_eig = inv_eigenvalues * b_eig

    # 5. Transform back
    x = eigenvectors @ x_eig
    return x

# Test: solve Ax = b
A = np.array([[2, 1], [1, 3]], dtype=complex)
b = np.array([1, 0], dtype=complex)
x = hhl_simulation(A, b)
print(f"Ax = {A @ x}")
print(f"b  = {b}")
print(f"Error: {np.linalg.norm(A @ x - b):.2e}")

HHL Algorithm Analysis

The HHL algorithm solves in time:

1. Encode in QPE register
2. QPE extracts eigenvalues of
3. Controlled rotation:
4. Uncompute QPE
5. Measure: obtain

Variational Quantum Linear Solver

VQLS addresses HHL limitations:

1. Prepare ansatz
2. Minimize
3. Use parameter-shift rule for gradients
4. Classical optimization updates

Advantages: no input encoding, NISQ-compatible, no phase estimation needed.