Welcome!

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

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

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

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 input S is now 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].

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 input S is now 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].

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

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

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

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.

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

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

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

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

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$