Welcome!

QAOA.jl is a lightweight implementation of the Quantum Approximate Optimization Algorithm (QAOA) based on Yao.jl. Furthermore, it implements the mean-field Approximate Optimization Algorithm, which is a useful tool to simulate quantum annealing and the QAOA in the mean-field approximation.

Installation

To install, use Julia's built-in package manager

julia> ] add QAOA

Library

Index

Note

Below is a list of the functions exported by QAOA.jl. Please note that we are taking advantage of multiple dispatch as implemented in Julia, i.e. some functions are defined multiple times with different signatures.

Problem Structure

QAOA.ProblemType
Problem(num_layers::Int, local_fields::Vector{Real}, couplings::Matrix{Real}, driver)

A container holding the basic properties of the QAOA circuit.

  • num_qubits::Int64: The number of qubits of the QAOA circuit.

  • num_layers::Int64: The number of layers $p$ of the QAOA circuit.

  • local_fields::Vector{Real}: The local (magnetic) fields of the Ising problem Hamiltonian.

  • couplings::Matrix{Real}: The coupling matrix of the Ising problem Hamiltonian.

  • edges::Any: The edges of the graph specified by the coupling matrix.

  • driver::Any: The driver of the QAOA circuit. By default the Pauli matrix X. May also be set to, e.g., [[X, X], [Y, Y]] to obtain the drivers$\hat X_i \hat X_j + \hat Y_i \hat Y_j$ acting on every pair of connected qubits.

Cost Function and QAOA Parameter Optimization

QAOA.cost_functionMethod
cost_function(problem::Problem, beta_and_gamma::Vector{Float64})

Returns the QAOA cost function, i.e. the expectation value of the problem Hamiltonian.

Input

  • problem::Problem: A Problem instance defining the optimization problem.
  • beta_and_gamma::Vector{Float64}: A vector of QAOA parameters.

Output

  • The expectation value of the problem Hamiltonian.

Notes

This function computes

$\langle \hat H \rangle = \left\langle \sum_{i=1}^N\left( h_i \hat Z_i + \sum_{j>i} J_{ij}\hat Z_i \hat Z_j \right)\right\rangle,$

where $N$ is num_qubits, $h_i$ are the local_fields and $J_{ij}$ are the couplings from problem.

QAOA.optimize_parametersMethod
optimize_parameters(problem::Problem, beta_and_gamma::Vector{Float64}, algorithm; niter::Int=128)

Gradient-free optimization of the QAOA cost function using NLopt.

Input

  • problem::Problem: A Problem instance defining the optimization problem.
  • beta_and_gamma::Vector{Float64}: The vector of initial QAOA parameters.
  • algorithm: One of NLopt's algorithms.
  • niter::Int=128 (optional): Number of optimization steps to be performed.

Output

  • cost: Final value of the cost function.
  • params: The optimized parameters.
  • probabilities: The simulated probabilities of all possible outcomes.

Example

  • For given number of layers p, local fields h and couplings J, define the problem

problem = QAOA.Problem(p, h, J)

and then do

cost, params, probs = QAOA.optimize_parameters(problem, ones(2p), :LN_COBYLA).

QAOA.optimize_parametersMethod
optimize_parameters(problem::Problem, beta_and_gamma::Vector{Float64}; niter::Int=128, learning_rate::Float64 = 0.05)

Gradient optimization of the QAOA cost function using Zygote.

Input

  • problem::Problem: A Problem instance defining the optimization problem.
  • beta_and_gamma::Vector{Float64}: The vector of initial QAOA parameters.
  • niter::Int=128 (optional): Number of optimization steps to be performed.
  • learning_rate::Float64=0.05 (optional): The learning rate of the gradient-ascent method.

Output

  • cost: Final value of the cost function.
  • params: The optimized parameters.
  • probabilities: The simulated probabilities of all possible outcomes.

Notes

  • The gradient-ascent method is defined via the parameter update

params = params .+ learning_rate .* gradient(f, params)[1].

Example

  • For given number of layers p, local fields h and couplings J, define the problem

problem = QAOA.Problem(p, h, J)

and then do

cost, params, probs = QAOA.optimize_parameters(problem, ones(2p)).

Mean-Field Approximate Optimization Algorithm

QAOA.evolve!Method
evolve!(S::Vector{<:Vector{<:Real}}, h::Vector{<:Real}, J::Matrix{<:Real}, β::Vector{<:Real}, γ::Vector{<:Real})

Input

  • S::Vector{<:Vector{<:Real}}: The initial vector of all spin vectors.
  • h::Vector{<:Real}: The vector of local magnetic fields of the problem Hamiltonian.
  • J::Matrix{<:Real}: The coupling matrix of the problem Hamiltonian.
  • β::Vector{<:Real}: The vector of QAOA driver parameters.
  • γ::Vector{<:Real}: The vector of QAOA problem parameters.

Output

  • The vector of all spin vectors after a full mean-field AOA evolution.

Notes

  • This is the first dispatch of evolve, which only returns the final vector of spin vectors.

  • The vector of spin vectors is properly initialized as

    S = [[1., 0., 0.] for _ in 1:num_qubits].

QAOA.evolve!Method
evolve!(S::Vector{<:Vector{<:Vector{<:Real}}}, h::Vector{<:Real}, J::Matrix{<:Real}, β::Vector{<:Real}, γ::Vector{<:Real})

Input

  • S::Vector{<:Vector{<:Vector{<:Real}}}: An empty history of the vector of all spin vectors.
  • h::Vector{<:Real}: The vector of local magnetic fields of the problem Hamiltonian.
  • J::Matrix{<:Real}: The coupling matrix of the problem Hamiltonian.
  • β::Vector{<:Real}: The vector of QAOA driver parameters.
  • γ::Vector{<:Real}: The vector of QAOA problem parameters.

Output

  • The full history of the vector of all spin vectors after a full mean-field AOA evolution.

Notes

  • This is the second dispatch of evolve, which returns the full history of the vector of spin vectors.

  • For a schedule of size num_layers = size(β)[1], S can be initialized as

    S = [[[1., 0., 0.] for _ in 1:num_qubits] for _ in 1:num_layers+1].

QAOA.expectationMethod
expectation(S::Vector{<:Vector{<:Real}}, h::Vector{<:Real}, J::Matrix{<:Real})

Input

  • S::Vector{<:Vector{<:Real}}: A vector of all spin vectors.
  • h::Vector{<:Real}: A vector of local magnetic fields.
  • J::Matrix{<:Real}: A coupling matrx.

Output

  • The energy expectation value corresponding to the supplied spin configuration.

Notes

  • In the mean-field approximation, the energy expectation value is defined as

    $\langle E \rangle = - \sum_{i=1}^N \bigg[ h_i + \sum_{j>i} J_{ij} n_j^z(p) \bigg] n_i^z(p).$

QAOA.mean_field_solutionMethod
mean_field_solution(problem::Problem, β::Vector{<:Real}, γ::Vector{<:Real})

Input

  • problem::Problem: A Problem instance defining the optimization problem.
  • β::Vector{<:Real}: The vector of QAOA driver parameters.
  • γ::Vector{<:Real}: The vector of QAOA problem parameters.

Output

  • The solution bitstring computed for a given problem and schedule parameters.

Notes

  • This is the first dispatch of mean_field_solution, which computes the sought-for solution bitstring for a given problem and schedule parameters.

  • The solution bitstring $\boldsymbol{\sigma}_*$ is defined as follows in terms of the $z$ components of the final spin vectors:

    $\boldsymbol{\sigma}_* = \left(\mathrm{sign}(n_1^z), ..., \mathrm{sign}(n_N^z) \right).$

QAOA.mean_field_solutionMethod
mean_field_solution(S::Vector{<:Vector{<:Real}})

Input

  • problem::Problem: A Problem instance defining the optimization problem.
  • β::Vector{<:Real}: The vector of QAOA driver parameters.
  • γ::Vector{<:Real}: The vector of QAOA problem parameters.

Output

  • The solution bitstring computed from a given vector of spin vectors.

Notes

  • This is the second dispatch of mean_field_solution, which computes the solution bitstring from a given vector of spin vectors.

  • The solution bitstring $\boldsymbol{\sigma}_*$ is defined as follows in terms of the $z$ components of the spin vectors:

    $\boldsymbol{\sigma}_* = \left(\mathrm{sign}(n_1^z), ..., \mathrm{sign}(n_N^z) \right).$

Fluctuation Analysis

QAOA.evolve_fluctuationsMethod
evolve_fluctuations(problem::Problem, τ::Real, β::Vector{<:Real}, γ::Vector{<:Real})

Input

  • problem::Problem: A Problem instance defining the optimization problem.
  • τ::Real: The time-step of the considered annealing schedule.
  • β::Vector{<:Real}: The corresponding vector of QAOA driver parameters.
  • γ::Vector{<:Real}: The corresponding vector of QAOA problem parameters.

Output

  • The Lyapunov exponents characterizing the dynamics of the Gaussian fluctuations.

Predefined Optimization Problems

QAOA.sherrington_kirkpatrickMethod
sherrington_kirkpatrick(variance::Float64; seed::Float64=1.0, num_layers::Int=1, driver=X)

Wrapper function setting up an instance of the Sherrington-Kirkpatrick model.

Input

  • N::Int: The number of spins of the problem.
  • variance::Float64: The variance of the distribution of the coupling matrix.
  • seed::Float64=1.0: The seed for the random-number generator used in the coupling matrix.
  • num_layers::Int=1 (optional): The number of QAOA layers usually denoted by $p$.
  • driver=X (optional): The driver or mixer used in the QAOA.

Output

  • An instance of the Problem struct holding all relevant quantities.

Notes

The cost function of the Sherrington-Kirkpatrick model is

$\hat H_P = \frac{1}{\sqrt{N}}\sum_{i<j\leq N} J_{ij} \hat{Z}_i \hat{Z}_j,$

where the couplings $J_{ij}$ are i.i.d. standard Gaussian variables, i.e. with zero mean $\langle J_{ij} \rangle = 0$ and variance $\langle J_{ij}^2 \rangle = J^2$.

QAOA.partition_problemMethod
partition_problem(a::Vector{Float64}; num_layers::Int=1, driver=X)

Wrapper function setting up an instance of the partition problem.

Input

  • a::Vector{Float64}: The input vector of numbers to be partitioned.
  • num_layers::Int=1 (optional): The number of QAOA layers usually denoted by $p$.
  • driver=X (optional): The driver or mixer used in the QAOA.

Output

  • An instance of the Problem struct holding all relevant quantities.

Notes

The partition problem for a set of uniformly distributed numbers $\mathcal{S} = \{a_1, ..., a_N\}$ consists of finding two subsets $\mathcal{S}_{1} \cup \mathcal{S}_2 = \mathcal{S}$ such that the difference of the sums over the two subsets $\mathcal{S}_{1, 2}$ is as small as possible. The cost function in Ising form can be defined as

$\hat C = -\left(\sum_{i=1}^{N} a_i \hat{Z}_i\right)^2 = \sum_{i<j\leq N} J_{ij} \hat{Z}_i \hat{Z}_j + \mathrm{const.}$

with $J_{ij}=-2a_i a_j$. The goal is then to maximize $\hat C$.

QAOA.max_cutMethod
max_cut(num_nodes::Int, edges::Vector{Tuple{Int, Int}}; num_layers::Int=1, driver=X)

Wrapper function setting up an instance of the MaxCut problem for the graph graph.

Input

  • graph::PyObject: The input graph, must be a Python NetworkX graph.
  • num_layers::Int=1 (optional): The number of QAOA layers usually denoted by $p$.
  • driver=X (optional): The driver or mixer used in the QAOA.

Output

  • An instance of the Problem struct holding all relevant quantities.

Notes

The cost function for the MaxCut problem as defined in the original QAOA paper is

$\hat C = -\frac{1}{2} \sum_{(i, j) \in E(G)} \hat Z_i \hat Z_j + \mathrm{const.},$

where $E(G)$ is the set of edges of the graph $G$.

QAOA.min_vertex_coverMethod
min_vertex_cover(num_nodes::Int, edges::Vector{Tuple{Int, Int}}; num_layers::Int=1, driver=X)

Wrapper function setting up a problem instance for the minimum vertex cover of the graph graph.

Input

  • graph::PyObject: The input graph, must be a Python NetworkX graph.
  • num_layers::Int=1 (optional): The number of QAOA layers usually denoted by $p$.
  • driver=X (optional): The driver or mixer used in the QAOA.

Output

  • An instance of the Problem struct holding all relevant quantities.

Notes

The cost function for the minimum-vertex-cover problem is

$\hat C = -\frac{3}{4} \sum_{(i, j) \in E(G)} (\hat Z_i \hat Z_j + \hat Z_i + \hat Z_j) + \sum_{i \in V(G)} \hat Z_i,$

where $E(G)$ is the set of edges and $V(G)$ is the set of vertices of graph (we have a global minus sign since we maximize the cost function).

Annealing

QAOA.annealMethod
anneal(problem::Problem, schedule::Function, T::Float64)

An extra function to do quantum annealing for a given problem instead of the QAOA.

Input

  • problem::Problem: A Problem instance defining the optimization problem.
  • schedule::Function: A function specifying the annealing schedule (s. below).
  • T::Float64: The duration of the annealing run.

Output

  • probabilities::Vector{Float64}: The vector of output probabilities over the bitstrings.

Notes

The function schedule should map from $[0, T]$ to $[0, 1]$ and have schedule(0) == 0, schedule(T) == 1. In the simplest case of a linear schedule, set schedule(t) = t/T. With driver $\hat H_D$ and problem Hamiltonian $\hat H_P$, the full annealing Hamiltonian then reads

$\hat H_A = (1 - t/T) \hat H_D + (t/T) \hat H_P$