HHL (Harrow-Hassidim-Lloyd) Algorithm
The HHL algorithm is a quantum algorithm for solving linear systems of equations of the form Ax = b, where A is a Hermitian matrix. It provides exponential speedup over classical algorithms for certain classes of linear systems.
The algorithm works by:
This implementation is designed for production use with:
Key functions:
HHL (Harrow-Hassidim-Lloyd) Algorithm The HHL algorithm is a quantum algorithm for solving linear systems of equations of the form Ax = b, where A is a Hermitian matrix. It provides exponential speedup over classical algorithms for certain classes of linear systems. The algorithm works by: 1. Encoding the vector b as a quantum state |b⟩ 2. Using quantum phase estimation to find eigenvalues of A 3. Performing conditional rotation to compute A^(-1) 4. Amplitude amplification to extract the solution This implementation is designed for production use with: - General n×n Hermitian matrices - Integration with existing quantum phase estimation - Proper error handling and validation - Configurable precision and success probability Key functions: - matrix-encoding-unitary: Encode Hermitian matrix as unitary evolution - vector-preparation-circuit: Prepare |b⟩ state from classical vector - hhl-circuit: Build complete HHL quantum circuit - hhl-algorithm: Execute HHL algorithm with backend
(compute-production-success-threshold condition-number shot-count & [options])Compute production-grade success thresholds based on user requirements.
This implements stricter success criteria suitable for production quantum algorithms:
Parameters:
Returns: Map containing:
Compute production-grade success thresholds based on user requirements. This implements stricter success criteria suitable for production quantum algorithms: - High success probability requirements (90%+ baseline) - Solution accuracy validation within 10% tolerance - Robust statistical validation with sufficient shots Parameters: - condition-number: Condition number κ(A) of the matrix - shot-count: Number of measurement shots - options: Optional parameters with keys: - :min-success-probability - Minimum success rate (default: 0.9 for 90%) - :max-solution-error - Maximum solution accuracy error (default: 0.1 for 10%) - :min-statistical-shots - Minimum shots for reliable statistics (default: 10000) Returns: Map containing: - :success-probability-threshold - Required success probability - :solution-accuracy-threshold - Required solution accuracy - :statistical-reliability - Boolean indicating if shot count is sufficient - :recommended-shots - Recommended minimum shot count
(conditional-rotation-circuit precision-qubits ancilla-qubit C)Create circuit for conditional rotation to implement A^(-1).
This implements the key step of HHL: conditional rotation based on eigenvalues to achieve matrix inversion. For eigenvalue λ, we rotate an ancilla qubit by angle θ ∝ 1/λ.
The rotation implements |λ⟩|0⟩ → |λ⟩(cos(θ)|0⟩ + sin(θ)|1⟩) where θ = C/λ for some constant C.
For this to work, we need meaningful rotations that actually flip the ancilla qubit with reasonable probability.
Parameters:
Returns: Function that takes a circuit and applies conditional rotations
Create circuit for conditional rotation to implement A^(-1). This implements the key step of HHL: conditional rotation based on eigenvalues to achieve matrix inversion. For eigenvalue λ, we rotate an ancilla qubit by angle θ ∝ 1/λ. The rotation implements |λ⟩|0⟩ → |λ⟩(cos(θ)|0⟩ + sin(θ)|1⟩) where θ = C/λ for some constant C. For this to work, we need meaningful rotations that actually flip the ancilla qubit with reasonable probability. Parameters: - precision-qubits: Number of qubits used for eigenvalue estimation - ancilla-qubit: Index of ancilla qubit for conditional rotation - C: Scaling constant for rotation angle Returns: Function that takes a circuit and applies conditional rotations
(estimate-condition-number matrix)Estimate the condition number κ(A) = λ_max / λ_min of a Hermitian matrix.
The condition number affects the precision required for the HHL algorithm. For well-conditioned matrices (κ ≈ 1), fewer precision qubits are needed. For ill-conditioned matrices (κ >> 1), more precision qubits are required.
This uses Frobenius norm estimation. For higher accuracy, the algorithm can be extended with proper eigenvalue decomposition techniques.
Parameters:
Returns: Estimated condition number (positive real number)
Estimate the condition number κ(A) = λ_max / λ_min of a Hermitian matrix. The condition number affects the precision required for the HHL algorithm. For well-conditioned matrices (κ ≈ 1), fewer precision qubits are needed. For ill-conditioned matrices (κ >> 1), more precision qubits are required. This uses Frobenius norm estimation. For higher accuracy, the algorithm can be extended with proper eigenvalue decomposition techniques. Parameters: - matrix: Hermitian matrix Returns: Estimated condition number (positive real number)
(hermitian? matrix)Validate that a matrix is Hermitian (A = A†).
For real matrices, this means the matrix is symmetric. For complex matrices, this means A[i,j] = conj(A[j,i]).
Parameters:
Returns: Boolean indicating if matrix is Hermitian
Example: (validate-hermitian-matrix [[1 2] [2 3]]) ;=> true (validate-hermitian-matrix [[1 2] [3 4]]) ;=> false
Validate that a matrix is Hermitian (A = A†). For real matrices, this means the matrix is symmetric. For complex matrices, this means A[i,j] = conj(A[j,i]). Parameters: - matrix: 2D vector representing the matrix Returns: Boolean indicating if matrix is Hermitian Example: (validate-hermitian-matrix [[1 2] [2 3]]) ;=> true (validate-hermitian-matrix [[1 2] [3 4]]) ;=> false
(hhl-algorithm backend matrix b-vector)(hhl-algorithm backend matrix b-vector options)Execute the HHL algorithm to solve Ax = b.
This is the main entry point for the HHL algorithm. It builds the quantum circuit, executes it on the specified backend, and extracts the solution vector.
Optimizations:
Parameters:
Returns: Map containing:
Execute the HHL algorithm to solve Ax = b.
This is the main entry point for the HHL algorithm. It builds the
quantum circuit, executes it on the specified backend, and extracts
the solution vector.
Optimizations:
- Identity matrix optimization: Direct solution for A = I
- Adaptive success thresholds based on condition number
- Robust scaling with regularization
- Special case handling for well-known matrix types
Parameters:
- backend - Quantum backend to use
- matrix: Hermitian matrix A (n×n)
- b-vector: Input vector b (length n)
- options: Algorithm options map with keys:
- :precision-qubits - Number of qubits for eigenvalue precision (default: 4)
- :ancilla-qubits - Number of ancilla qubits (default: 1)
- :shots - Number of measurement shots (default: 1000)
- :min-success-rate - Minimum success rate threshold (default: adaptive)
- :force-quantum - Force quantum algorithm even for identity (default: false)
Returns:
Map containing:
- :success - Boolean indicating if algorithm succeeded
- :solution-vector - Estimated solution x (when successful)
- :circuit - The quantum circuit used (nil for classical optimizations)
- :method - Method used ('classical-identity' or 'quantum-hhl')
- :condition-number - Estimated condition number of matrix(hhl-circuit matrix b-vector precision-qubits ancilla-qubits)Build the complete HHL quantum circuit.
This constructs a functional HHL algorithm circuit that actually works:
This implementation focuses on actually working rather than theoretical completeness.
Parameters:
Returns: Complete quantum circuit implementing HHL algorithm
Build the complete HHL quantum circuit. This constructs a functional HHL algorithm circuit that actually works: 1. Vector preparation (encoding |b⟩) 2. Quantum phase estimation to find eigenvalues 3. Conditional rotation for matrix inversion 4. Proper qubit management and meaningful operations This implementation focuses on actually working rather than theoretical completeness. Parameters: - matrix: Hermitian matrix A - b-vector: Input vector b - precision-qubits: Number of qubits for eigenvalue precision - ancilla-qubits: Number of ancilla qubits (typically 1) Returns: Complete quantum circuit implementing HHL algorithm
(identity? matrix)(identity? matrix tolerance)Check if a matrix is the identity matrix within tolerance.
For production HHL, identity matrices have a trivial solution: x = b. This optimization avoids the quantum algorithm entirely for this case.
Parameters:
Returns: Boolean indicating if matrix is identity
Check if a matrix is the identity matrix within tolerance. For production HHL, identity matrices have a trivial solution: x = b. This optimization avoids the quantum algorithm entirely for this case. Parameters: - matrix: Matrix to check - tolerance: Numerical tolerance (default 1e-10) Returns: Boolean indicating if matrix is identity
(matrix-encoding-unitary matrix time-scale)Create a unitary operation that encodes the Hermitian matrix A.
For HHL, we need to encode A as a unitary evolution U = e^(iAt) for some time t. This function returns a function that applies controlled-U^(2^k) operations needed for quantum phase estimation.
For diagonal matrices, this is exact. For general matrices, this uses Hamiltonian simulation techniques.
Parameters:
Returns: Function that takes (circuit, control-qubit, power, target-qubits) and applies controlled-U^power to the circuit
Create a unitary operation that encodes the Hermitian matrix A. For HHL, we need to encode A as a unitary evolution U = e^(iAt) for some time t. This function returns a function that applies controlled-U^(2^k) operations needed for quantum phase estimation. For diagonal matrices, this is exact. For general matrices, this uses Hamiltonian simulation techniques. Parameters: - matrix: Hermitian matrix A to encode - time-scale: Time parameter t for evolution e^(iAt) Returns: Function that takes (circuit, control-qubit, power, target-qubits) and applies controlled-U^power to the circuit
(positive-definite? matrix)Validate that a Hermitian matrix is positive definite (all eigenvalues > 0).
HHL algorithm requires positive definite matrices for proper matrix inversion. Negative eigenvalues cause the conditional rotation step to fail.
Parameters:
Returns: Boolean indicating if matrix is positive definite
Example: (validate-positive-definite [[3 1] [1 2]]) ;=> true (eigenvalues: 3.62, 1.38) (validate-positive-definite [[1 2] [2 3]]) ;=> false (eigenvalues: 4.24, -0.24)
Validate that a Hermitian matrix is positive definite (all eigenvalues > 0). HHL algorithm requires positive definite matrices for proper matrix inversion. Negative eigenvalues cause the conditional rotation step to fail. Parameters: - matrix: 2D vector representing the Hermitian matrix Returns: Boolean indicating if matrix is positive definite Example: (validate-positive-definite [[3 1] [1 2]]) ;=> true (eigenvalues: 3.62, 1.38) (validate-positive-definite [[1 2] [2 3]]) ;=> false (eigenvalues: 4.24, -0.24)
(recursive-amplitude-encoding circuit amplitudes)Recursive amplitude encoding using uniformly controlled rotations
This implements proper state preparation for arbitrary amplitude vectors using the method of Möttönen & Vartiainen with uniformly controlled rotations.
For a vector of amplitudes [a₀, a₁, ..., aₙ₋₁], this creates a quantum state |ψ⟩ = Σᵢ aᵢ|i⟩ where the amplitudes are exactly encoded (up to normalization).
The algorithm works by recursive decomposition:
Parameters:
Returns: Updated quantum circuit with amplitude encoding gates
Recursive amplitude encoding using uniformly controlled rotations This implements proper state preparation for arbitrary amplitude vectors using the method of Möttönen & Vartiainen with uniformly controlled rotations. For a vector of amplitudes [a₀, a₁, ..., aₙ₋₁], this creates a quantum state |ψ⟩ = Σᵢ aᵢ|i⟩ where the amplitudes are exactly encoded (up to normalization). The algorithm works by recursive decomposition: 1. Split the vector into two halves 2. Apply rotation to control the amplitude distribution between halves 3. Recursively encode each half with appropriate controlled rotations Parameters: - circuit: Quantum circuit to modify - amplitudes: Vector of amplitudes to encode (assumed normalized) Returns: Updated quantum circuit with amplitude encoding gates
(solve backend matrix vector)(solve backend matrix vector options)Solve the linear system Ax = b using the HHL quantum algorithm.
This is a convenience function that provides a simple interface to the HHL algorithm for solving linear systems. The solution is properly scaled to satisfy A*x = b.
Features:
Parameters:
Returns: The solution vector x such that A*x ≈ b, or nil if algorithm fails
Example: (solve backend [[2 1] [1 2]] [1 1] {:shots 5000}) ;=> [0.333... 0.333...] ; approximate solution
Solve the linear system Ax = b using the HHL quantum algorithm.
This is a convenience function that provides a simple interface to the HHL algorithm
for solving linear systems. The solution is properly scaled to satisfy A*x = b.
Features:
- Automatic matrix validation and conditioning analysis
- Identity matrix optimization for O(1) classical solution
- Adaptive error handling and fallback strategies
- Robust numerical stability for ill-conditioned systems
Parameters:
- backend: Quantum backend to use for execution
- matrix: Hermitian matrix A (should be positive definite for optimal results)
- vector: Input vector b
- options: Optional configuration map with keys:
- :strict-validation - Require positive definiteness (default: true for compatibility)
- All other options from hhl-algorithm
Returns:
The solution vector x such that A*x ≈ b, or nil if algorithm fails
Example:
(solve backend [[2 1] [1 2]] [1 1] {:shots 5000})
;=> [0.333... 0.333...] ; approximate solution(uniformly-controlled-ry circuit control-qubits target-qubit angles)Apply uniformly controlled RY rotation with multiple control qubits
Apply uniformly controlled RY rotation with multiple control qubits
(uniformly-controlled-ry-single circuit control-qubit target-qubit angles)Apply uniformly controlled RY with single control qubit using standard decomposition
Apply uniformly controlled RY with single control qubit using standard decomposition
(validate-solution-accuracy matrix solution target)(validate-solution-accuracy matrix solution target tolerance)Validate the accuracy of the HHL solution by computing ||Ax - b|| / ||b||.
For a valid solution x to the system Ax = b, we expect ||Ax - b|| ≈ 0. This function computes the relative residual error as a quality metric.
Parameters:
Returns: Map containing:
Validate the accuracy of the HHL solution by computing ||Ax - b|| / ||b||. For a valid solution x to the system Ax = b, we expect ||Ax - b|| ≈ 0. This function computes the relative residual error as a quality metric. Parameters: - matrix: The matrix A from the linear system - solution: The computed solution vector x - target: The target vector b - tolerance: Maximum allowable relative error (default: 0.1 for 10%) Returns: Map containing: - :valid - Boolean indicating if solution meets accuracy requirements - :residual-error - Relative residual error ||Ax - b|| / ||b|| - :absolute-residual - Absolute residual ||Ax - b||
(vector-preparation-circuit b-vector num-qubits)Create a quantum circuit to prepare the state |b⟩ from classical vector b.
This function takes a classical vector b and creates a quantum circuit that prepares the corresponding quantum state |b⟩ = Σᵢ bᵢ|i⟩.
For HHL to work properly, we need accurate amplitude encoding. This implementation uses proper amplitude encoding for exact results.
Parameters:
Returns: Quantum circuit that prepares |b⟩ when applied to |0...0⟩
Create a quantum circuit to prepare the state |b⟩ from classical vector b. This function takes a classical vector b and creates a quantum circuit that prepares the corresponding quantum state |b⟩ = Σᵢ bᵢ|i⟩. For HHL to work properly, we need accurate amplitude encoding. This implementation uses proper amplitude encoding for exact results. Parameters: - b-vector: Classical vector b (will be normalized) - num-qubits: Number of qubits needed to represent the vector Returns: Quantum circuit that prepares |b⟩ when applied to |0...0⟩
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |