Optimisation classes

This module contains classes for formulating and solving QUBO and linear problems.

QUBO

QUBO, short for Quadratic Unconstrained Binary Optimisation, are a class of problems which are NP-complete.

When formulated carefully, QUBO problems can be mapped to solve a host of optimisation problems such as Travelling Salesman Problem, Maximum Independent Set, Quadratic Assignment Problem, Maximum Clique problem, Maximum Cut problem, etc.

class qiboopt.opt_class.opt_class.QUBO(offset, *args)[source]

Initializes a QUBO class. The QUBO class can be multiplied by a scalar factor, and multiple QUBO instances can be added together.

Args: offset (float): The constant offset of the QUBO problem. args (dict): Input for parameters for QUBO or Ising formulation. If len(args) == 1,

args has to be a dictionary representing the quadratic coefficient assigned to the QUBO.QDict attribute, which represents the \(Q\) matrix. If len(args) == 2, both objects have to be dictionaries representing the inputs \(h\) and \(J\) for an Ising formulation.

We have the following relation:

\[s' J s + h' s = \text{offset} + x' Q x\]
where
h (dict): Linear biases as a dictionary of the form {v: bias, ...}, where keys are variables of the

model and values are biases.

J (dict): Quadratic biases as a dictionary of the form {(u, v): bias, ...}, where keys are

two-tuples of variables of the model and values are biases associated with the interaction between the pair of variables.

Example

from qiboopt.opt_class.opt_class import QUBO


Qdict1 = {(0, 0): 1.0, (0, 1): 0.5, (1, 1): -1.0}
qp1 = QUBO(0, Qdict1)
print(qp1.Qdict)

{(0, 0): 1.0, (0, 1): 0.5, (1, 1): -1.0}

qp1 *= 2
print(qp1.Qdict)

{(0, 0): 2.0, (0, 1): 1.0, (1, 1): -2.0}

Qdict2 = {(0, 0): 2.0, (1, 1): 1.0}
qp2 = QUBO(1, Qdict2)
qp3 = qp1 + qp2
print(qp3.Qdict)

{(0, 0): 4.0, (0, 1): 1.0, (1, 1): -1.0}

print(qp3.offset)

1

h = {3: 1.0, 4: 0.82, 5: 0.23}
J = {(0, 0): 1.0, (0, 1): 0.5, (1, 1): -1.0}
qp = QUBO(0, h, J)
print(qp.Qdict)

{(3, 3): -2.0, (4, 4): -1.64, (5, 5): -0.46, (0, 1): 2.0, (0, 0): -1.0, (1, 1): -1.0}
qubo_to_ising()[source]

Convert a QUBO problem to an Ising problem.

Maps a quadratic unconstrained binary optimisation (QUBO) problem defined over binary variables (\(\{0, 1\}\)), where the linear term is contained along the diagonal of \(Q\) (\(x' Qx\)), to an Ising model defined on spin variables (\(\{-1, +1\}\)). More specifically, returns the the \(h\) and \(J\) variables defining the Ising model as well as the constant value representing the offset in energy between the two problem formulations.

\[x' Q x = \text{constant} + s' J s + h' s\]
Returns:

A 3-tuple containing: h: the linear coefficients of the Ising problem, J: the quadratic coefficients of the Ising problem, and constant: the new energy offset.

Return type:

(dict, dict, float)

construct_symbolic_Hamiltonian_from_QUBO()[source]

Constructs a symbolic Hamiltonian from the QUBO problem by converting it to an Ising model.

The method calls the qubo_to_ising function to convert the QUBO formulation into an Ising Hamiltonian with linear and quadratic terms, before creating a symbolic Hamiltonian using the main qibo library.

Returns:

Hamiltonian corresponding to the QUBO problem

Return type:

qibo.hamiltonians.hamiltonians.SymbolicHamiltonian

evaluate_f(x)[source]

Evaluates the quadratic function for a given binary vector.

Parameters:

x (list) – A list representing the binary vector for which to evaluate the function.

Returns:

Value of the given binary vector.

Return type:

float

Example

from qiboopt.opt_class.opt_class import QUBO


Qdict = {(0, 0): 1.0, (0, 1): 0.5, (1, 1): -1.0}
qp = QUBO(0, Qdict)
x = [1, 1]
print(qp.evaluate_f(x))

0.5
evaluate_grad_f(x)[source]

Evaluates the gradient of the quadratic function at a given binary vector.

Parameters:

x (List[int]) – A list representing the binary vector for which to evaluate the gradient.

Returns:

List of floats representing the gradient vector.

Return type:

list

Example

from qiboopt.opt_class.opt_class import QUBO


Qdict = {(0, 0): 1.0, (0, 1): 0.5, (1, 1): -1.0}
qp = QUBO(0, Qdict)
x = [1, 1]
print(qp.evaluate_grad_f(x))

[ 1.5 -0.5]

Solves the QUBO problem using the Tabu search algorithm.

Parameters:

  • max_iterations (int) – Maximum number of iterations to run the Tabu search. Defaults to 100.

  • tabu_size (int) – Size of the Tabu list.

Returns:

A list of integers representing the best binary vector found and its corresponding value

Return type:

(list, float)

Example

from qiboopt.opt_class.opt_class import QUBO


Qdict = {(0, 0): 1.0, (0, 1): 0.5, (1, 1): -1.0}
qp = QUBO(0, Qdict)
best_solution, best_obj_value = qp.tabu_search(50, 5)
print(best_solution)

[0 1]

..testcode:

print(best_obj_value)

..testoutput

0.5

brute_force()[source]

Solves the QUBO problem by evaluating all possible binary vectors. Note that this approach is very slow.

Returns:

A list of integers representing the optimal binary vector and its corresponding value

Return type:

(list, float)

Example

from qiboopt.opt_class.opt_class import QUBO


Qdict = {(0, 0): 1.0, (0, 1): 0.5, (1, 1): -1.0}
qp = QUBO(0, Qdict)
opt_vector, min_value = qp.brute_force()
print(opt_vector)

(0, 1)

print(min_value)

-1.0
canonical_q()[source]

Converts the Qdict attribute (QUBO matrix) to canonical form whereby only terms with i < j are retained.

Returns:

Updated QUBO matrix

Return type:

dict

qubo_to_qaoa_circuit(gammas, betas, alphas=None, custom_mixer=None)[source]

Constructs a QAOA or XQAOA circuit for the given QUBO problem.

Parameters:

  • gammas (List[float]) – parameters for phasers

  • betas (List[float]) – parameters for X mixers

  • alphas (List[float], optional) – parameters for Y mixers for XQAOA

  • custom_mixer (List[qibo.models.Circuit]) – optional argument that takes as input custom mixers. If len(custom_mixer) == 1, then use this one circuit as mixer for all layers. If len(custom_mixer) == len(gammas), then use each circuit as mixer for each layer. If len(custom_mixer) != 1 and != len(gammas), raise an error.

Returns:

The QAOA or XQAOA circuit corresponding to the QUBO problem.

Return type:

qibo.models.Circuit

train_QAOA(gammas=None, betas=None, alphas=None, p=None, nshots=1000, regular_loss=True, maxiter=10, method='cobyla', cvar_delta=0.25, custom_mixer=None, backend=None, noise_model=None)[source]

Constructs the QAOA or XQAOA circuit with optional parameters for the mixers or phases before using a classical optimiser to search for the optimal parameters which minimise the cost function (either expected value or Conditional Variance at Risk (CVaR).

Parameters:

  • gammas (List[float], optional) – parameters for phasers.

  • betas (List[float], optional) – parameters for X mixers.

  • alphas (List[float], optional) – parameters for Y mixers for XQAOA. Defaults to None.

  • p (int, optional) – number of layers.

  • nshots (int, optional) – number of shots

  • regular_loss (Bool, optional) – If False, Conditional Variance at Risk (CVaR) is used as cost function. Defaults to True, where expected value is used as cost function.

  • maxiter (int, optional) – Maximum number of iterations used in the minimiser. Defaults to 10.

  • cvar_delta (float, optional) – Represents the quantile threshold used for calculating the CVaR. Defaults to 0.25.

  • custom_mixer (List[qibo.models.Circuit]) – optional argument that takes as input custom mixers. If len(custom_mixer) == 1, then use this one circuit as mixer for all layers. If len(custom_mixer) == len(gammas), then use each circuit as mixer for each layer. If len(custom_mixer) != 1 and != len(gammas), raise an error.

  • backend (qibo.backends.abstract.Backend, optional) – backend to be used in the execution. If None, it uses the current backend. Defaults to None.

  • noise_model (qibo.noise.NoiseModel, optional) – noise model applied to simulate noisy computations. Defaults to None.

Returns:

A tuple containing:

  • best (float): The lowest cost value achieved.

  • params (List[float]): Optimised QAOA parameters.

  • extra (dict): Additional metadata (e.g., convergence info).

  • circuit (qibo.models.Circuit): Final circuit used for evaluation.

  • frequencies (dict): Bitstring outcome frequencies from measurement.

Return type:

Tuple[float, List[float], dict, qibo.models.Circuit, dict]

Example

from qiboopt.opt_class.opt_class import QUBO

Qdict = {(0, 0): 1.0, (0, 1): 0.5, (1, 1): -1.0}
qp = QUBO(0, Qdict)
opt_vector, min_value = qp.brute_force()

# Train regular QAOA
output = QUBO(0, Qdict).train_QAOA(p=10)
qubo_to_qaoa_object(params: list = None)[source]

Generates a QAOA object for the QUBO problem.

Parameters:

params (List[float]) – Parameters of the QAOA given in block format: e.g. [all_gammas, all_betas, all_alphas] (if alphas is not None)

Returns:

QAOA circuit for the QUBO problem.

Return type:

qibo.models.QAOA

Linear Problems

Linear problem write up goes here.

class qiboopt.opt_class.opt_class.LinearProblem(A, b)[source]

Initializes a LinearProblem class, which represents a linear problem of the form \(Ax + b\). The LinearProblem class can be multiplied by a scalar factor, and multiple LinearProblem instances can be added together.

Parameters:

  • A (np.ndarray) – Coefficient matrix.

  • b (np.ndarray) – Constant vector.

Example

import numpy as np
from qiboopt.opt_class.opt_class import LinearProblem


A1 = np.array([[1, 2], [3, 4]])
b1 = np.array([5, 6])
lp1 = LinearProblem(A1, b1)
lp1 *= 2
A2 = np.array([[1, 1], [1, 1]])
b2 = np.array([1, 1])
lp2 = LinearProblem(A2, b2)
lp3 = lp1 + lp2
print(lp3.A)

[[3 5]
 [7 9]]

print(lp3.b)

[11 13]
evaluate_f(x)[source]

Evaluates the linear function \(Ax + b\) at a given point \(x\).

Parameters:

x (np.ndarray) – Input vector at which to evaluate the linear function.

Example

import numpy as np
from qiboopt.opt_class.opt_class import LinearProblem


A = np.array([[1, 2], [3, 4]])
b = np.array([5, 6])
lp = LinearProblem(A, b)
x = np.array([1, 1])
result = lp.evaluate_f(x)
print(result)

[ 8 13]
Returns:

The value of the linear function \(Ax + b\) at \(x\).

Return type:

numpy.ndarray

square()[source]

Squares the linear problem to obtain a quadratic problem. :returns: Quadratic problem corresponding to squaring the linear function. :rtype: qiboopt.opt_class.opt_class.QUBO

Example

import numpy as np
from qiboopt.opt_class.opt_class import LinearProblem

A = np.array([[1, 2], [3, 4]])
b = np.array([5, 6])
lp = LinearProblem(A, b)
Quadratic = lp.square()
print(Quadratic.Qdict)

{(0, 0): 56, (0, 1): 14, (1, 0): 14, (1, 1): 88}

print(Quadratic.offset)

61