Optimisation class

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]
qubo_to_ising(constant=0.0)[source]

Convert a QUBO problem to an Ising problem.

Maps a quadratic unconstrained binary optimisation (QUBO) problem defined over binary variables (0 or 1 values), where the linear term is contained along x’ Qx the diagonal of Q, to an Ising model defined on spins (variables with {-1, +1} values). Returns h and J that define the Ising model as well as constant representing the offset in energy between the two problem formulations.

\[x' Q x = constant + s' J s + h' s\]
Parameters:

  • Q (dict[(variable, variable), coefficient]) – QUBO coefficients in a dict of form {(u, v): coefficient, …}, where keys are 2-tuples of variables of the model and values are biases associated with the pair of variables. Tuples (u, v) represent interactions and (v, v) linear biases.

  • constant (float) – Constant offset to be applied to the energy. Defaults to 0.

Returns:

A 3-tuple containing: h (dict): Linear coefficients of the Ising problem. J (dict): Quadratic coefficients of the Ising problem. constant (float): The new energy offset.

Return type:

(dict, dict, float)

Example

This example converts a QUBO problem of two variables that have positive biases of value 1 and are positively coupled with an interaction of value 1 to an Ising problem, and shows the new energy offset.

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. Then, it creates a symbolic Hamiltonian using the qibo library.

Returns:

A symbolic

Hamiltonian that corresponds to the QUBO problem.

Return type:

ham (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:

The evaluated function value.

Return type:

f_value (float)

Example

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 float representing the gradient vector.

Return type:

grad (List)

Example

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:

List of ints representing the best binary vector found. best_obj_value (float): The corresponding objective value.

Return type:

best_solution (list)

Example

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]
print(best_obj_value)
# >>> 0.5
brute_force()[source]
Solves the QUBO problem by evaluating all possible binary vectors.

Note that this approach is very slow.

Returns:

List of ints representing the optimal binary vector. min_value (float): The minimum value of the objective function.

Return type:

opt_vector (list)

Example

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 QUBO matrix to canonical form where only terms with i < j are retained.

Returns:

A dictionary and also update Qdict

Return type:

self.Qdict (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:

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

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:

A QAOA circuit for the QUBO problem.

Return type:

qaoa (qibo.models.QAOA)

Linear Problems

Linear problem write up goes here.

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

A class used to represent a linear problem of the form Ax + b.

Parameters:

  • A (np.ndarray) – Coefficient matrix.

  • b (np.ndarray) – Constant vector.

  • n (int) – Dimension of the problem, inferred from the size of b.

Example

A1 = np.array([[1, 2], [3, 4]])
b1 = np.array([5, 6])
lp1 = linear_problem(A1, b1)
A2 = np.array([[1, 1], [1, 1]])
b2 = np.array([1, 1])
lp2 = linear_problem(A2, b2)
lp3 = lp1 + lp2
print(lp3.A)
# >>> [[2 3]
#      [4 5]]
print(lp3.b)
# >>> [6 7]
print(lp1.A)  # Original lp1 unchanged
# >>> [[1 2]
#      [3 4]]
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.

Returns:

The value of the linear function Ax + b at the given x.

Return type:

numpy.ndarray

Example

A = np.array([[1, 2], [3, 4]])
b = np.array([5, 6])
lp = linear_problem(A, b)
x = np.array([1, 1])
result = lp.evaluate_f(x)
print(result)
# [ 8 13]
square()[source]

Squares the linear problem to obtain a quadratic problem.

Returns:

A quadratic problem corresponding to squaring the linear function.

Return type:

qiboopt.opt_class.opt_class.QUBO

Example

A = np.array([[1, 2], [3, 4]])
b = np.array([5, 6])
lp = linear_problem(A, b)
Quadratic = lp.square()
print(Quadratic.Qdict)
# >>> {(0, 0): 56, (0, 1): 14, (1, 0): 14, (1, 1): 88}
print(Quadratic.offset)
# >>> 61