Quantum Approximate Optimization Algorithm (QAOA) Implementation
QAOA is a quantum-classical hybrid algorithm for solving combinatorial optimization problems. It uses alternating application of a problem Hamiltonian and a mixer Hamiltonian to explore the solution space and find approximate solutions.
Key Features:
Algorithm Flow:
The algorithm targets NP-hard combinatorial optimization problems and provides quantum advantage for certain problem instances.
Quantum Approximate Optimization Algorithm (QAOA) Implementation QAOA is a quantum-classical hybrid algorithm for solving combinatorial optimization problems. It uses alternating application of a problem Hamiltonian and a mixer Hamiltonian to explore the solution space and find approximate solutions. Key Features: - Problem Hamiltonian construction for MaxCut, Max-SAT, and TSP - Mixer Hamiltonian (typically X-gates on all qubits) - Alternating evolution structure: U(β,γ) = e^(-iβH_M)e^(-iγH_P) - Integration with classical optimization for parameter tuning - Performance analysis and approximation ratio calculation Algorithm Flow: 1. Initialize equal superposition state |+⟩^n 2. Apply p layers of alternating evolution U(β_i,γ_i) 3. Measure expectation value of the problem Hamiltonian 4. Use classical optimizer to update parameters (β,γ) 5. Repeat until convergence or maximum iterations The algorithm targets NP-hard combinatorial optimization problems and provides quantum advantage for certain problem instances.
(analyze-qaoa-parameters optimization-result)Analyze QAOA parameter landscape and patterns.
Parameters:
Returns: Map with parameter analysis
Analyze QAOA parameter landscape and patterns. Parameters: - optimization-result: Result from QAOA optimization Returns: Map with parameter analysis
(calculate-approximation-ratio qaoa-solution classical-optimum problem-type)Calculate approximation ratio for optimization problems.
Parameters:
Returns: Approximation ratio (for maximization: qaoa/classical, for minimization: classical/qaoa)
Calculate approximation ratio for optimization problems. Parameters: - qaoa-solution: Solution value from QAOA - classical-optimum: Known or estimated classical optimum - problem-type: Type of problem (:max-cut, :max-sat, :tsp) Returns: Approximation ratio (for maximization: qaoa/classical, for minimization: classical/qaoa)
(custom-ising-hamiltonian h-fields j-couplings)Create a custom Ising model Hamiltonian.
General Ising model: H = Σᵢ hᵢZᵢ + Σᵢⱼ Jᵢⱼ ZᵢZⱼ
Parameters:
Returns: Collection of Pauli terms representing the Ising Hamiltonian
Create a custom Ising model Hamiltonian. General Ising model: H = Σᵢ hᵢZᵢ + Σᵢⱼ Jᵢⱼ ZᵢZⱼ Parameters: - h-fields: Vector of local magnetic fields [h₀ h₁ ... hₙ₋₁] - j-couplings: Collection of coupling terms [[i j Jᵢⱼ], ...] Returns: Collection of Pauli terms representing the Ising Hamiltonian
(decode-max-cut-solution index num-qubits graph)Decode measurement outcomes for MaxCut problem.
Parameters:
Returns: Map with decoded MaxCut solution information
Decode measurement outcomes for MaxCut problem. Parameters: - index: Integer index from measurement - num-qubits: Number of qubits to determine bit vector length - graph: Collection of edges as [vertex1 vertex2 weight] tuples Returns: Map with decoded MaxCut solution information
(decode-max-sat-solution index num-qubits clauses)Decode measurement outcomes for MaxSAT problem.
Parameters:
Returns: Map with decoded MaxSAT solution information
Decode measurement outcomes for MaxSAT problem. Parameters: - index: Integer index from measurement - num-qubits: Number of qubits to determine bit vector length - clauses: Collection of Boolean clauses Returns: Map with decoded MaxSAT solution information
(decode-tsp-solution index num-qubits distance-matrix)Decode measurement outcomes for TSP problem.
Parameters:
Returns: Map with decoded TSP solution information
Decode measurement outcomes for TSP problem. Parameters: - index: Integer index from measurement - num-qubits: Number of qubits to determine bit vector length (should be n²) - distance-matrix: n×n matrix of distances between cities Returns: Map with decoded TSP solution information
(extract-best-solution solutions problem-type)Extract the best solution from a collection of decoded solutions.
Parameters:
Returns: Best solution according to the problem objective
Extract the best solution from a collection of decoded solutions. Parameters: - solutions: Collection of solution maps with objective values - problem-type: Type of problem to determine maximization vs minimization Returns: Best solution according to the problem objective
(extract-solution-from-frequencies measurement-frequencies
problem-type
problem-instance
shots
num-qubits
&
{:keys [classical-optimum]})Extract problem-specific solutions from measurement frequency data.
This function provides a hardware-compatible way to extract QAOA solutions using measurement frequencies directly from the backend results, which is more efficient than converting to individual outcome strings.
Parameters:
Returns: Map with problem-specific solution analysis
Extract problem-specific solutions from measurement frequency data.
This function provides a hardware-compatible way to extract QAOA solutions
using measurement frequencies directly from the backend results, which is
more efficient than converting to individual outcome strings.
Parameters:
- measurement-frequencies: Map of {outcome-index count} from backend
- problem-type: Type of problem (:max-cut, :max-sat, :tsp)
- problem-instance: Problem-specific data (graph, clauses, distance matrix)
- shots: Total number of measurement shots
- num-qubits: Number of qubits
- classical-optimum: Known classical optimum (optional)
Returns:
Map with problem-specific solution analysis(hamiltonian-evolution-circuit hamiltonian evolution-time num-qubits)Create a quantum circuit for time evolution under a Hamiltonian.
For a Hamiltonian H and evolution time t, this creates the circuit implementing e^(-iHt). For Pauli string Hamiltonians, this decomposes into products of rotations and CNOT gates.
Parameters:
Returns: Quantum circuit implementing the evolution
Create a quantum circuit for time evolution under a Hamiltonian. For a Hamiltonian H and evolution time t, this creates the circuit implementing e^(-iHt). For Pauli string Hamiltonians, this decomposes into products of rotations and CNOT gates. Parameters: - hamiltonian: Collection of Pauli terms - evolution-time: Evolution time parameter - num-qubits: Number of qubits Returns: Quantum circuit implementing the evolution
(max-cut-hamiltonian graph num-vertices)Create a MaxCut problem Hamiltonian for a given graph.
The MaxCut problem aims to find a partition of vertices that maximizes the number of edges crossing the partition. The problem Hamiltonian is:
H_P = Σ_{(i,j)∈E} w_{ij} * (1 - Z_i Z_j) / 2
Where w_{ij} is the edge weight between vertices i and j. The ground state corresponds to the maximum cut.
Parameters:
Returns: Collection of Pauli terms representing the MaxCut Hamiltonian
Example: (max-cut-hamiltonian [[0 1 1.0] [1 2 2.0] [0 2 1.5]] 3) ;=> Hamiltonian for triangle graph with weighted edges
Create a MaxCut problem Hamiltonian for a given graph.
The MaxCut problem aims to find a partition of vertices that maximizes
the number of edges crossing the partition. The problem Hamiltonian is:
H_P = Σ_{(i,j)∈E} w_{ij} * (1 - Z_i Z_j) / 2
Where w_{ij} is the edge weight between vertices i and j.
The ground state corresponds to the maximum cut.
Parameters:
- graph: Collection of edges as [vertex1 vertex2 weight] tuples
- num-vertices: Number of vertices in the graph (determines number of qubits)
Returns:
Collection of Pauli terms representing the MaxCut Hamiltonian
Example:
(max-cut-hamiltonian [[0 1 1.0] [1 2 2.0] [0 2 1.5]] 3)
;=> Hamiltonian for triangle graph with weighted edges(max-sat-hamiltonian clauses num-variables)Create a Maximum Satisfiability (Max-SAT) Hamiltonian.
Max-SAT aims to satisfy the maximum number of Boolean clauses. Each clause is a disjunction (OR) of literals, where a literal is either a variable xᵢ or its negation ¬xᵢ.
The Hamiltonian assigns energy 0 to satisfied clauses and 1 to unsatisfied clauses, so minimizing energy maximizes satisfaction.
Encoding: Each Boolean variable maps to one qubit where |0⟩ = false, |1⟩ = true. For a clause C = (l₁ ∨ l₂ ∨ ... ∨ lₖ), the penalty Hamiltonian is: H_C = ∏ᵢ (1 - lᵢ) where lᵢ = (1+Zᵢ)/2 for positive literal xᵢ = (1-Zᵢ)/2 for negative literal ¬xᵢ
Parameters:
Returns: Collection of Pauli terms representing the Max-SAT Hamiltonian
Example: (max-sat-hamiltonian [[0 1] [:not-0 2] [1 :not-2]] 3) ;=> Hamiltonian for (x₀ ∨ x₁) ∧ (¬x₀ ∨ x₂) ∧ (x₁ ∨ ¬x₂)
Create a Maximum Satisfiability (Max-SAT) Hamiltonian.
Max-SAT aims to satisfy the maximum number of Boolean clauses.
Each clause is a disjunction (OR) of literals, where a literal
is either a variable xᵢ or its negation ¬xᵢ.
The Hamiltonian assigns energy 0 to satisfied clauses and 1 to
unsatisfied clauses, so minimizing energy maximizes satisfaction.
Encoding: Each Boolean variable maps to one qubit where |0⟩ = false, |1⟩ = true.
For a clause C = (l₁ ∨ l₂ ∨ ... ∨ lₖ), the penalty Hamiltonian is:
H_C = ∏ᵢ (1 - lᵢ) where lᵢ = (1+Zᵢ)/2 for positive literal xᵢ
= (1-Zᵢ)/2 for negative literal ¬xᵢ
Parameters:
- clauses: Collection of clauses, where each clause is a collection
of literals. For positive literals use positive integers,
for negative literals use keywords like :not-0, :not-1, etc.
or maps like {:variable 0 :negated true}
- num-variables: Number of Boolean variables (determines number of qubits)
Returns:
Collection of Pauli terms representing the Max-SAT Hamiltonian
Example:
(max-sat-hamiltonian [[0 1] [:not-0 2] [1 :not-2]] 3)
;=> Hamiltonian for (x₀ ∨ x₁) ∧ (¬x₀ ∨ x₂) ∧ (x₁ ∨ ¬x₂)(qaoa-ansatz-circuit problem-hamiltonian
mixer-hamiltonian
parameters
num-qubits)Create a QAOA ansatz circuit with alternating problem and mixer evolution.
The QAOA ansatz consists of p layers of alternating evolution: U(β,γ) = ∏ᵢ₌₁ᵖ e^(-iβᵢH_M) e^(-iγᵢH_P)
Where H_P is the problem Hamiltonian and H_M is the mixer Hamiltonian.
Parameters:
Returns: Quantum circuit implementing the QAOA ansatz
Create a QAOA ansatz circuit with alternating problem and mixer evolution. The QAOA ansatz consists of p layers of alternating evolution: U(β,γ) = ∏ᵢ₌₁ᵖ e^(-iβᵢH_M) e^(-iγᵢH_P) Where H_P is the problem Hamiltonian and H_M is the mixer Hamiltonian. Parameters: - problem-hamiltonian: Problem Hamiltonian (collection of Pauli terms) - mixer-hamiltonian: Mixer Hamiltonian (collection of Pauli terms) - parameters: Vector of [γ₁ β₁ γ₂ β₂ ... γₚ βₚ] parameters - num-qubits: Number of qubits Returns: Quantum circuit implementing the QAOA ansatz
(qaoa-circuit-constructor options)Create circuit construction function for QAOA.
This function serves as the circuit-constructor for the variational-algorithm template. It captures the problem and mixer Hamiltonians and returns a function that constructs QAOA circuits given parameters.
Parameters:
Returns: Function that takes parameters and returns a QAOA circuit
Create circuit construction function for QAOA. This function serves as the circuit-constructor for the variational-algorithm template. It captures the problem and mixer Hamiltonians and returns a function that constructs QAOA circuits given parameters. Parameters: - options: QAOA configuration map containing all necessary configuration Returns: Function that takes parameters and returns a QAOA circuit
(qaoa-hamiltonian-constructor options)Create problem Hamiltonian for QAOA based on the problem type and configuration.
This function serves as the hamiltonian-constructor for the variational-algorithm template. It handles all supported QAOA problem types and creates the appropriate Hamiltonian.
Parameters:
Returns: Collection of Pauli terms representing the problem Hamiltonian
Create problem Hamiltonian for QAOA based on the problem type and configuration. This function serves as the hamiltonian-constructor for the variational-algorithm template. It handles all supported QAOA problem types and creates the appropriate Hamiltonian. Parameters: - options: QAOA configuration map containing: - :problem-type - Type of problem (:max-cut, :max-sat, :tsp, :custom) - :problem-instance - Problem-specific data structure - :num-qubits - Number of qubits (for some problem types) - :problem-hamiltonian - Pre-constructed Hamiltonian (for :custom type) Returns: Collection of Pauli terms representing the problem Hamiltonian
(qaoa-mixer-hamiltonian-constructor options)Create mixer Hamiltonian for QAOA.
This function creates the mixer Hamiltonian, defaulting to the standard X mixer but allowing for custom mixers based on the configuration.
Parameters:
Returns: Collection of Pauli terms representing the mixer Hamiltonian
Create mixer Hamiltonian for QAOA. This function creates the mixer Hamiltonian, defaulting to the standard X mixer but allowing for custom mixers based on the configuration. Parameters: - options: QAOA configuration map containing: - :num-qubits - Number of qubits - :mixer-hamiltonian - Custom mixer Hamiltonian (optional) - :mixer-type - Type of mixer (:standard, :xy) (optional, default: :standard) Returns: Collection of Pauli terms representing the mixer Hamiltonian
(qaoa-objective problem-hamiltonian
mixer-hamiltonian
num-qubits
backend
options)Create the objective function for QAOA optimization.
This function creates the objective function that:
Parameters:
Returns: Function that takes parameters and returns energy expectation value
Create the objective function for QAOA optimization. This function creates the objective function that: 1. Takes QAOA parameters [γ₁ β₁ γ₂ β₂ ...] as input 2. Constructs the QAOA ansatz circuit with those parameters 3. Executes the circuit on the backend or simulator 4. Calculates the problem Hamiltonian expectation value 5. Returns the energy (to be minimized by the optimizer) Parameters: - problem-hamiltonian: Problem Hamiltonian to minimize - mixer-hamiltonian: Mixer Hamiltonian (optional, defaults to standard X mixer) - num-qubits: Number of qubits - backend: Quantum backend for circuit execution (can be nil for direct simulation) - options: Execution options (shots, etc.) Returns: Function that takes parameters and returns energy expectation value
(qaoa-parameter-count options)Calculate the number of parameters for QAOA.
This function serves as the parameter-count function for the variational-algorithm template. QAOA requires 2 parameters per layer: γ (gamma) and β (beta).
Parameters:
Returns: Number of parameters (2 * num-layers)
Calculate the number of parameters for QAOA. This function serves as the parameter-count function for the variational-algorithm template. QAOA requires 2 parameters per layer: γ (gamma) and β (beta). Parameters: - options: QAOA configuration map containing :num-layers Returns: Number of parameters (2 * num-layers)
(qaoa-parameter-initialization options)Initialize QAOA parameters using sophisticated strategies.
This function provides QAOA-specific parameter initialization that's more sophisticated than the generic random initialization in the template.
Parameters:
Returns: Vector of initial parameters [γ₁ β₁ γ₂ β₂ ...]
Initialize QAOA parameters using sophisticated strategies. This function provides QAOA-specific parameter initialization that's more sophisticated than the generic random initialization in the template. Parameters: - options: QAOA configuration map Returns: Vector of initial parameters [γ₁ β₁ γ₂ β₂ ...]
(qaoa-result-processor base-result options)Process and enhance QAOA results with algorithm-specific analysis.
This function serves as the result-processor for the variational-algorithm template. It adds QAOA-specific analysis including parameter extraction, approximation ratios, and problem-specific solution quality metrics.
Enhanced to include hardware-compatible solution extraction using measurement outcomes.
Parameters:
Returns: Enhanced result map with QAOA-specific analysis and problem-specific solutions
Process and enhance QAOA results with algorithm-specific analysis. This function serves as the result-processor for the variational-algorithm template. It adds QAOA-specific analysis including parameter extraction, approximation ratios, and problem-specific solution quality metrics. Enhanced to include hardware-compatible solution extraction using measurement outcomes. Parameters: - base-result: Base optimization result from the template - options: QAOA configuration options (including :backend for measurement-based solutions) Returns: Enhanced result map with QAOA-specific analysis and problem-specific solutions
(quantum-approximate-optimization-algorithm backend options)Main QAOA algorithm implementation using the variational algorithm template.
This function orchestrates the QAOA process using the enhanced variational-algorithm template, providing improved optimization features, convergence monitoring, and standardized result analysis while maintaining full backward compatibility.
Key Enhancements from Template Integration:
Supported problem types:
Supported optimization methods:
Parameters:
Returns: Enhanced map containing QAOA results and comprehensive analysis
Example: (quantum-approximate-optimization-algorithm backend {:problem-type :max-cut :problem-instance [[0 1 1.0] [1 2 1.0] [0 2 1.0]] ; Triangle graph :num-qubits 3 :num-layers 2 :optimization-method :adam :max-iterations 100 :tolerance 1e-6})
Main QAOA algorithm implementation using the variational algorithm template.
This function orchestrates the QAOA process using the enhanced variational-algorithm
template, providing improved optimization features, convergence monitoring, and
standardized result analysis while maintaining full backward compatibility.
Key Enhancements from Template Integration:
- Advanced convergence monitoring with intelligent stopping criteria
- Enhanced optimization methods with gradient support where applicable
- Standardized result analysis and performance metrics
- Consistent error handling and timing across all variational algorithms
- Parameter landscape analysis capabilities
- Future extensibility for new optimization methods
Supported problem types:
- :max-cut - Maximum cut problem on graphs
- :max-sat - Maximum satisfiability problem
- :tsp - Travelling salesman problem (simplified encoding)
- :custom - Custom problem with provided Hamiltonian
Supported optimization methods:
- :gradient-descent - Basic gradient descent with parameter shift gradients
- :adam - Adam optimizer with parameter shift gradients (recommended default)
- :quantum-natural-gradient - Quantum Natural Gradient using Fisher Information Matrix
- :nelder-mead - Derivative-free Nelder-Mead simplex method
- :powell - Derivative-free Powell's method
- :cmaes - Covariance Matrix Adaptation Evolution Strategy (robust)
- :bobyqa - Bound Optimization BY Quadratic Approximation (handles bounds well)
Parameters:
- backend: Quantum backend implementing QuantumBackend protocol
- options: QAOA configuration options
- :problem-type - Type of problem (:max-cut, :max-sat, :tsp, :custom)
- :problem-instance - Problem-specific data (graph, clauses, distance matrix, etc.)
- :num-qubits - Number of qubits in the system
- :num-layers - Number of QAOA layers (p parameter)
- :optimization-method - Optimization method to use (default: :adam)
- :max-iterations - Maximum iterations for optimization (default: 500)
- :tolerance - Convergence tolerance (default: 1e-6)
- :gradient-tolerance - Gradient norm tolerance (default: 1e-4)
- :min-iterations - Minimum iterations before convergence (default: 10)
- :patience - Convergence analysis window (default: 20)
- :shots - Number of shots for circuit execution (default: 1024)
- :initial-parameters - Custom initial parameters (optional)
- :parameter-strategy - Parameter initialization strategy (default: :theoretical)
* :theoretical - Literature-based optimal values for small p (recommended)
* :adiabatic - Linear interpolation schedule inspired by adiabatic evolution
* :random-smart - Random sampling in theoretically good parameter ranges
- :classical-optimum - Known classical optimum for approximation ratio calculation
- :mixer-hamiltonian - Custom mixer Hamiltonian (optional)
- :mixer-type - Type of mixer (:standard, :xy) (optional, default: :standard)
Returns:
Enhanced map containing QAOA results and comprehensive analysis
Example:
(quantum-approximate-optimization-algorithm backend
{:problem-type :max-cut
:problem-instance [[0 1 1.0] [1 2 1.0] [0 2 1.0]] ; Triangle graph
:num-qubits 3
:num-layers 2
:optimization-method :adam
:max-iterations 100
:tolerance 1e-6})(smart-parameter-initialization num-layers problem-type strategy)Generate smart initial parameters for QAOA based on theoretical insights and heuristics.
Different strategies:
Parameters:
Returns: Vector of [γ₁ β₁ γ₂ β₂ ...] parameters
Generate smart initial parameters for QAOA based on theoretical insights and heuristics. Different strategies: - :theoretical - Based on known optimal values for small p - :adiabatic - Linear interpolation from adiabatic evolution - :random-smart - Improved random initialization in good ranges Parameters: - num-layers: Number of QAOA layers (p) - problem-type: Type of optimization problem (:max-cut, :max-sat, etc.) - strategy: Initialization strategy keyword Returns: Vector of [γ₁ β₁ γ₂ β₂ ...] parameters
(standard-mixer-hamiltonian num-qubits)Create the standard QAOA mixer Hamiltonian.
The mixer Hamiltonian is typically H_M = Σᵢ Xᵢ, which creates transitions between computational basis states and allows exploration of the solution space.
Parameters:
Returns: Collection of Pauli terms representing the mixer Hamiltonian
Create the standard QAOA mixer Hamiltonian. The mixer Hamiltonian is typically H_M = Σᵢ Xᵢ, which creates transitions between computational basis states and allows exploration of the solution space. Parameters: - num-qubits: Number of qubits in the system Returns: Collection of Pauli terms representing the mixer Hamiltonian
(travelling-salesman-hamiltonian distance-matrix & {:keys [penalty-weight]})Create a Travelling Salesman Problem (TSP) Hamiltonian.
The TSP aims to find the shortest route visiting all cities exactly once. This uses the standard n² qubit encoding where qubit q_{i,j} represents whether city i is visited at time step j.
The Hamiltonian has three components:
The encoding maps qubit index q = i*n + j to city i at time j.
Parameters:
Returns: Collection of Pauli terms representing the TSP Hamiltonian
Create a Travelling Salesman Problem (TSP) Hamiltonian.
The TSP aims to find the shortest route visiting all cities exactly once.
This uses the standard n² qubit encoding where qubit q_{i,j} represents
whether city i is visited at time step j.
The Hamiltonian has three components:
1. Cost function: Σ_{i,j,k} d_{i,j} * x_{i,k} * x_{j,k+1}
2. City constraints: Σ_i (Σ_j x_{i,j} - 1)² (each city visited exactly once)
3. Time constraints: Σ_j (Σ_i x_{i,j} - 1)² (exactly one city per time step)
The encoding maps qubit index q = i*n + j to city i at time j.
Parameters:
- distance-matrix: n×n matrix of distances between cities
- penalty-weight: Weight for constraint penalty terms (default: auto-calculated)
Returns:
Collection of Pauli terms representing the TSP Hamiltonian(xy-mixer-hamiltonian num-qubits periodic)Create an XY mixer Hamiltonian for problems with particle number conservation.
The XY mixer preserves the number of |1⟩ states and is useful for problems where the constraint is to select exactly k items out of n.
H_M = Σᵢ (Xᵢ₊₁Xᵢ + Yᵢ₊₁Yᵢ) = Σᵢ (σᵢ₊ σᵢ₋ + σᵢ₋ σᵢ₊₁)
Parameters:
Returns: Collection of Pauli terms representing the XY mixer Hamiltonian
Create an XY mixer Hamiltonian for problems with particle number conservation. The XY mixer preserves the number of |1⟩ states and is useful for problems where the constraint is to select exactly k items out of n. H_M = Σᵢ (Xᵢ₊₁Xᵢ + Yᵢ₊₁Yᵢ) = Σᵢ (σᵢ₊ σᵢ₋ + σᵢ₋ σᵢ₊₁) Parameters: - num-qubits: Number of qubits in the system - periodic: Whether to include periodic boundary conditions Returns: Collection of Pauli terms representing the XY mixer Hamiltonian
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 |