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

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).