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
(create-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
(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-tsp-solution measurement n distance-matrix)Decode a quantum state measurement into a TSP tour.
Parameters:
Returns: Map with decoded tour information
Decode a quantum state measurement into a TSP tour. Parameters: - measurement: String of 0s and 1s representing qubit measurements - n: Number of cities - distance-matrix: Distance matrix for cost calculation Returns: Map with decoded tour information
(estimate-classical-optimum problem-type problem-instance num-qubits)Estimate the classical optimum for comparison with QAOA results.
For small problem instances, this performs brute-force enumeration. For larger instances, this provides heuristic estimates.
Parameters:
Returns: Estimated classical optimum value
Estimate the classical optimum for comparison with QAOA results. For small problem instances, this performs brute-force enumeration. For larger instances, this provides heuristic estimates. Parameters: - problem-type: Type of optimization problem - problem-instance: Problem-specific data - num-qubits: Number of qubits (determines search space size) Returns: Estimated classical optimum value
(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-optimization objective-fn initial-parameters options)Run QAOA optimization using the specified method.
Similar to VQE optimization but specialized for QAOA's alternating structure. Supports the same optimization methods as VQE.
Parameters:
Returns: Map with optimization results
Run QAOA optimization using the specified method. Similar to VQE optimization but specialized for QAOA's alternating structure. Supports the same optimization methods as VQE. Parameters: - objective-fn: QAOA objective function to minimize - initial-parameters: Starting parameter values [γ₁ β₁ γ₂ β₂ ...] - options: Optimization options Returns: Map with optimization results
(quantum-approximate-optimization-algorithm backend options)Main QAOA algorithm implementation.
This function orchestrates the QAOA process, including circuit construction, optimization, and execution on a quantum backend.
Supported problem types:
Supported optimization methods:
Parameters:
Returns: Map containing QAOA results and 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})
Main QAOA algorithm implementation.
This function orchestrates the QAOA process, including circuit construction,
optimization, and execution on a quantum backend.
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)
- :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
Returns:
Map containing QAOA results and 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})(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 |