Variational Quantum Algorithms

from mpqp.execution.vqa import *

In order to support Variational Quantum Algorithms (VQA for short), the parametrized gates of our circuits accept sympy’s symbolic variable as arguments.

A symbolic variable is a variable aimed at being a numeric value but without the value attributed. It can be created as such:

from sympy import symbols

theta, k = symbols("Θ k")

This concept exists more or less in all quantum circuit libraries: braket has FreeExpression, qiskit has Parameter, qlm has Variable, cirq uses sympy’s Symbol, etc…

Once you define a circuit with variables, you have two options:

  1. either the measure of the circuit is an ExpectationMeasure and can directly feed it in the optimizer;

  2. or you can define a custom cost function for more complicated cases.

Detailed example for those two options can be found in our example notebooks.

minimize(optimizable, method, device=None, init_params=None, nb_params=None, optimizer_options=None, callback=None)[source]

This function runs an optimization on the parameters of the circuit, in order to minimize the measured expectation value of observables associated with the given circuit. Note that this means that the latter should contain an ExpectationMeasure.

Parameters

  • optimizable (Union[QCircuit, partial[float], Callable[[Union[list[float], ndarray[Any, dtype[float32]]]], float]]) – Either the circuit, containing symbols and an expectation measure, or the evaluation function.

  • method (Union[Optimizer, Callable[[Union[partial[float], Callable[[Union[list[float], ndarray[Any, dtype[float32]]]], float]], Optional[Union[list[float], ndarray[Any, dtype[float32]]]], Optional[dict[str, Any]]], tuple[float, Union[list[float], numpy.ndarray[Any, numpy.dtype[numpy.float32]]]]]]) – The method used to optimize most of those methods come from scipy. If the choices offered in this package are not covering your needs, you can define your own optimizer. This should be a function taking as input a function representing the circuit, with as many inputs as the circuit has parameters, and any optional initialization parameters, and returning the optimal value reached and the parameters used to reach this value.

  • device (Optional[AvailableDevice]) – The device on which the circuit should be run.

  • init_params (Optional[Union[list[float], ndarray[Any, dtype[float32]]]]) – The optional initialization parameters (the value attributed to the symbols in the first loop of the optimizer).

  • nb_params (Optional[int]) – Number of variables to input in optimizable. It is only useful if optimizable is a Callable and if init_params was not given. If not this argument is not taken into account.

  • optimizer_options (Optional[dict[str, Any]]) – Options used to configure the VQA optimizer (maximum iterations, convergence threshold, etc…). These options are passed as is to the minimizer.

  • callback (Optional[Union[Callable[[OptimizeResult], None], Callable[[Union[list[float], ndarray[Any, dtype[float32]], tuple[float, ...]]], None]]]) – A callable called after each iteration.

Returns

The optimal value reached and the parameters corresponding to this value.

Return type

tuple[float, Union[list[float], numpy.ndarray[Any, numpy.dtype[numpy.float32]]]]

Examples

>>> alpha, beta = symbols("α β")
>>> circuit = QCircuit([
...     H(0),
...     Rx(alpha, 1),
...     CNOT(1,0),
...     Rz(beta, 0),
...     ExpectationMeasure(
...         Observable(np.diag([1,2,-3,4])),
...         [0,1],
...         shots=0,
...     ),
... ])
>>> minimize(
...     circuit,
...     Optimizer.BFGS,
...     ATOSDevice.MYQLM_PYLINALG,
...     optimizer_options={"maxiter":50},
... )
(-0.9999999999999996, array([0., 0.]))

>>> def cost_func(params):
...     run_res = run(
...         circuit,
...         ATOSDevice.MYQLM_PYLINALG,
...         {alpha: params[0], beta: params[1]}
...     )
...     return 1 - run_res.expectation_values ** 2
>>> minimize(
...     cost_func,
...     Optimizer.BFGS,
...     nb_params=2,
...     optimizer_options={"maxiter":50},
... )
(8.881784197001252e-16, array([0., 0.]))

For now, our minimizer is a wrapper around scipy’s minimizer. The Optimizer enum lists all the methods validated with the rest of the library.

class Optimizer(value, names=<not given>, *values, module=None, qualname=None, type=None, start=1, boundary=None)[source]

Bases: Enum

Enum used to select the optimizer for the VQA.

BFGS = 1
CMAES = 3
COBYLA = 2
POWELL = 4

Quantum Approximate Optimization Algorithm

See full example of this module in this dedicated notebook.

QUBO

This module is designed to generate and manipulate Quadratic Unconstrained Binary Optimization (Qubo) problems, which are widely use to describe various optimization problems.

We model Qubo expressions as binary trees, in the form of an Abstract Syntax Tree, useful for taking into account the hierarchies and priorities between the operations appearing in the Qubo. A node of this Qubo tree corresponds to an operation while the leaves of the tree are boolean variables or constants on which the binary or unary operations are applied. One can find below an example of such tree structure for the Qubo \(-1 + 2x\):

         Addition
       /          \
UnaryMinus   Multiplication
   /           /       \
  1           2    QuboAtom("x")

Most of the classes implemented in this module are not meant to be directly used by the user, but are instantiated in the background when arithmetic or boolean operations are used. Every node in the tree is inheriting from the Qubo class, regrouping all the common implementations for operations and simplifications. The only class that is meant to be directly instantiated by the user is QuboAtom, allowing one to define boolean variables that will be manipulated withing the Qubo.

In the context of the MPQP library, these classes are used in the QAOA module to encode the optimization problem solved by the qaoa_solver().

class BinaryOperation(value, left, right)[source]

Bases: Qubo

Class defining binary operations in a Qubo expression. A binary operation is defined by an operator (\(+\), \(-\) or \(*\)) applied on two operands (left and right), each of them potentially being:

  • a Qubo expression,

  • a QuboAtom variable,

  • a QuboConstant,

  • a BinaryOperation

This class should be exclusively used by other classes and not by the user.

Available binary operations: +, -, *. (Technically boolean operations: |, &, ^ are available but they are decomposed into the previously mentioned operations.)

Parameters

  • value (BinaryOperator) – Operator corresponding to the modeled operation by this class.

  • left (Qubo) – Left part of the equation, in term of a binary tree it’s the left child.

  • right (Qubo) – Right part of the equation, in term of a binary tree it’s the right child.

Examples

>>> BinaryOperation(Multiplication(), QuboConstant(3), QuboAtom("x"))
(3 * QuboAtom("x"))
>>> BinaryOperation(Subtraction(), QuboAtom("y"), QuboAtom("x"))
(QuboAtom("y") - QuboAtom("x"))
class Qubo(value, left=None, right=None)[source]

Bases: ABC

Abstract class defining an optimization problem following the Qubo representation. This class is instantiated through the use of QuboAtom, not directly (see examples below).

A Qubo is defined as a quadratic expression of boolean variables, hence, the available operators are:

  • & : the logical AND operation between two QuboAtom

  • | : the logical OR operation between two QuboAtom

  • ^ : the logical XOR operation between two QuboAtom

  • + : the artihmetic addition operator between two Qubo expressions

  • - : the artihmetic subtraction operator between two Qubo expressions

  • * : the artihmetic multiplication operator between two Qubo expressions

The evaluation of a Qubo expression can be minimized using the qaoa_solver() solver.

Conceptually, a Qubo is the the root node of a binary tree representing the whole Qubo expression with QuboAtom or QuboConstant . as its leafs. The classes BinaryOperation and UnaryOperation are used as nodes representing the Qubo’s operators.

Parameters

  • value (Union[str, Operator, float]) – Information concerning the root node, can be an Operator, the name of the boolean variable or the value of the constant.

  • left (Optional['Qubo']) – Left child of this Qubo root node.

  • right (Optional['Qubo']) – Right child of this Qubo root node.

Examples

>>> x0 = QuboAtom('x0')
>>> x1 = QuboAtom('x1')
>>> qubo1 = 3*x0*x1 + x0 - 2*x1
>>> qubo2 = 0.7*x0 + 0.3*x1 - 0.02
>>> print(qubo1)
3*x0*x1+x0-2*x1
>>> qubo2.__repr__()
'(((QuboAtom("x0") * 0.7) + (QuboAtom("x1") * 0.3)) - 0.02)'
>>> print(qubo1 + qubo2)
3*x0*x1+x0-2*x1+0.7*x0+0.3*x1-0.02
>>> print(qubo2 * qubo2)
(0.7*x0+0.3*x1-0.02)*(0.7*x0+0.3*x1-0.02)
>>> print(qubo1 - x0)
3*x0*x1+x0-2*x1-x0
>>> print((qubo1 + qubo2).simplify())
1.7*x0-1.7*x1+3*x0*x1-0.02
>>> print((qubo2 * x0).simplify())
0.68*x0+0.3*x1*x0
>>> print((qubo1 - x0).simplify())
-(2*x1)+3*x0*x1
>>> print(qubo1.to_cost_hamiltonian().pauli_string)
0.25*I@I + 0.25*I@Z - 1.25*Z@I + 0.75*Z@Z
>>> pprint(qubo1.to_cost_hamiltonian().matrix)
[[0, 0 , 0, 0],
 [0, -2, 0, 0],
 [0, 0 , 1, 0],
 [0, 0 , 0, 2]]
>>> qubo1.depth()
4
>>> (qubo1 -5).get_terms_and_coefs()
[(3, ['x0', 'x1']), (1, ['x0']), (-2, ['x1']), (-5, [])]
>>> qubo2.size()
2
>>> qubo2.weight_matrix()
(array([[0.7, 0. ],
       [0. , 0.3]]), -0.02)
>>> -(x0 - x1)
-(QuboAtom("x0") - QuboAtom("x1"))
depth()[source]

Return the maximum depth of the tree representing the Qubo expression.

Return type

int

evaluate(variables)[source]

Function used to evaluate the result of a Qubo expression.

Parameters

variables (dict[str, bool]) – Mapping of the variables to their binary value.

Returns

The value of the expression for the given values.

Return type

float

Examples

>>> x0 = QuboAtom("x0")
>>> x1 = QuboAtom("x1")
>>> expr = 3*x0
>>> expr.evaluate({"x0": True})
3
>>> expr.evaluate({"x0": False})
0
>>> expr = 3*(~x0)
>>> expr.evaluate({"x0": False})
3
>>> expr = 3*x0*x1 - 2*x1
>>> expr.evaluate({"x1": True, "x0": False})
-2
get_terms_and_coefs()[source]

Creates a list of lists containing the coefficients of the monomials of the Qubo.

Returns

The coefficients and variables in the Qubo expression.

Return type

list[tuple[float, list[str]]]

Examples

>>> x0 = QuboAtom('x0')
>>> x1 = QuboAtom('x1')

>>> expr = 3*x0 - x1 + 1
>>> expr.get_terms_and_coefs()
[(3, ['x0']), (-1, ['x1']), (1, [])]

>>> expr = 3*(x0 | x1)
>>> expr.get_terms_and_coefs()
[(3, ['x0']), (3, ['x1']), (-3, ['x0', 'x1'])]
get_variables()[source]

This function generates a list containing every unique variables used in the expression. They are ordered from the left of the expression to the right.

Returns

A list of all of the unique boolean variables of the Qubo.

Return type

list[str]

Examples

>>> x0 = QuboAtom('x0')
>>> x1 = QuboAtom('x1')

>>> expr = 3*x0 - x1
>>> expr.get_variables()
['x0', 'x1']

>>> expr = 3*x1 - 10*x0
>>> expr.get_variables()
['x1', 'x0']

>>> expr = 3*x0*x1 - x1 + x0
>>> expr.get_variables()
['x0', 'x1']
simplify()[source]

Returns the simplified form of the given Qubo.

Notes

In the case of all the coefficients of an atom cancel each other then the simplified form will not declare the atom.

The resulting cost hamiltonian hence would be changed.

Examples

>>> x0 = QuboAtom("x0")
>>> x1 = QuboAtom("x1")
>>> expr = 3*x0 - x1 - 2*(x0^x1)
>>> simplified = expr.simplify()
>>> print(simplified)
x0-3*x1+4*x0*x1
>>> print(
...     matrix_eq(
...         expr.to_cost_hamiltonian().matrix,
...         simplified.to_cost_hamiltonian().matrix
...     )
... )
True
Return type

Qubo

size()[source]

Returns the number of unique boolean variables in the Qubo expression.

Return type

int

to_cost_hamiltonian()[source]

Converts this Qubo into a cost Hamiltonian, represented by an Observable, that can typically be used in the QAOA algorithm.

Returns

The cost Hamiltonian representing this Qubo.

Return type

Observable

Examples

>>> x_0 = QuboAtom("x_0")
>>> x_1 = QuboAtom("x_1")
>>> expr = 3 * x_0 * x_1 - 4 * x_0 - 2 * x_1 + 1
>>> pprint(expr.to_cost_hamiltonian().matrix)
[[1, 0 , 0 , 0 ],
 [0, -1, 0 , 0 ],
 [0, 0 , -3, 0 ],
 [0, 0 , 0 , -2]]
weight_matrix()[source]

Generates the weight matrix corresponding to this Qubo expression. The weight matrix regroups the coefficients that appears in front of all possible combinations of quadratic binary monomials.

The coefficient in front of QuboAtom \(x_i\) (which correspond to \(x_i \cdot x_i\)) gives us \(i\)-th the diagonal element of the weigh matrix. For instance, the Qubo written as \(3x_0 + 2x_1\), is a two-by-two diagonal matrix with elements \([3,2]\).

The off-diagonal element on the \(i\)-th line and the \(j\)-th column corresponds to the half of the coefficient in front of the binary monomial \(x_i \cdot x_j\). One can notice that the weight matrix is indeed a symmetric matrix.

If a constant is appearing in the Qubo, it will be stored aside of the weight matrix and returned by this function. This is useful in the context of the generation of the corresponding cost Hamiltonian.

Returns

A tuple containing the weight matrix of this Qubo and the potential additive constant.

Return type

tuple[npt.NDArray[np.float64], float]

Examples

>>> x0 = QuboAtom('x0')
>>> x1 = QuboAtom('x1')
>>> x2 = QuboAtom('x2')
>>> x3 = QuboAtom('x3')
>>> expr = 2 * x0 + 3 * x1 + 4 * x0 * x2 + x3 + 18
>>> w_matrix, add_constant = expr.weight_matrix()
>>> pprint(w_matrix)
[[2, 0, 2, 0],
 [0, 3, 0, 0],
 [2, 0, 0, 0],
 [0, 0, 0, 1]]
>>> print(add_constant)
18.0
class QuboAtom(value)[source]

Bases: Qubo

Class defining a boolean variable for a Qubo problem.

See class Qubo for full usage of this class.

Arg:

value: String holding the name of the variable.

Examples

>>> x = QuboAtom("x")
>>> expr = 2 * x + 2
>>> print(expr.get_variables())
['x']
>>> y = QuboAtom("y")
>>> expr = 2 * x + 2 - 5 * y + 4 * (x ^ y)
>>> print(expr.get_variables())
['x', 'y']
>>> print(~y)
~y
>>> ~(~y)
QuboAtom("y")
>>> print(x | y)
x+y-x*y
>>> print(x & y)
x*y
>>> print(x ^ y)
x+y-2*x*y
Parameters

value (str) –

class QuboConstant(value)[source]

Bases: Qubo

Class defining constant terms (real numbers) in a Qubo expression. In the context of the tree this node is always a leaf.

This class should be exclusively used by other classes and not by the user.

Parameters

value (float) – The value of the constant in the expression.

Examples

>>> QuboConstant(0)
0
>>> QuboConstant(3.2)
3.2
>>> (QuboConstant(3) - QuboConstant(4.0)).simplify()
-1.0
class UnaryOperation(value, right)[source]

Bases: Qubo

Class defining a unary operation for a Qubo expression. The value is the operator and the rest of the equation is store in the right child.

This class should be exclusively used by other classes and not by the user.

Unary operations supported: -, ~.

Parameters

  • value (UnaryOperator) – The unary operator.

  • right (Qubo) – The Qubo representing the operand.

Examples

>>> UnaryOperation(Minus(), QuboAtom("x"))
-QuboAtom("x")
>>> UnaryOperation(Not(), QuboAtom("x"))
~QuboAtom("x")

QAOA

This module is an implementation of one particular type of Variational Quantum Algorithms: the Qaoa (Quantum Approximate Optimization Algorithm). Mainly used for combinatorial optimization problems, and following the trotterization principle, this algorithm works by generating a circuit of alternated parametrized operators: the cost operator and the mixer operator.

Cost operators are generated based on the cost Hamiltonian, which encodes the problem we want to optimize (usually expressed initially in Qubo formulation).

Mixer operators are here to escape from the natural convergence to the “closest” eigenstate of the cost Hamiltonian, allowing the algorithm to explore more widely the space of solutions. They can be customized for a specific problem, but we provide a generic set of Mixer operators.

class QaoaMixer(type, graph=None, bitflip=0)[source]

Bases: object

Class defining the Mixer hamiltonian used in the qaoa_solver() function.

This class is used to help generate commonly used mixer Hamiltonians. The available Hamiltonians are regrouped in QaoaMixerType.

Parameters

  • type (QaoaMixerType) – Type of the mixer hamiltonian to be generated.

  • graph (Optional['Graph']) – Graph needed to generate certain types of hamiltonian.

  • bitflip (int) – Value needed to build the bitflip hamiltonian.

generate_mixer_hamiltonian(qubits)[source]

Generates the mixer hamiltonian according to the mixer type.

Parameters

qubits (int) – Number of variables in the Qubo expression (also the number of qubits in the Qaoa ansatz).

Returns

The matrix of the mixer hamiltonian.

Return type

npt.NDArray[np.complex128]

class QaoaMixerType(value, names=<not given>, *values, module=None, qualname=None, type=None, start=1, boundary=None)[source]

Bases: Enum

Enum class that provides a set of commonly used mixer Hamiltonians.

This mixer was introduced in A Quantum Approximate Optimization Algorithm by Edward Farhi, Jeffrey Goldstone, Sam Gutmann in https://arxiv.org/abs/1411.4028.

MIXER_X = \(\large \sum\limits_{i} X_i\)

Both mixers below were introduced in From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz by Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas in https://doi.org/10.3390/a12020034.

MIXER_XY = \(\large\frac{1}{2} \sum\limits_{(i,j)\in E(G)} X_i X_j + Y_i Y_j\)

MIXER_BITFLIP = \(\large\sum \limits_{v\in V(G)} \frac{1}{2^{d(v)}}X_v \prod \limits_{w \in N(v)} (I + (-1)^b Z_w)\)

MIXER_BITFLIP = 3
MIXER_X = 1
MIXER_XY = 2
class QaoaResult(cost, final_state, values, final_params)[source]

Bases: object

This class is used to pack the different interpretations of the result of a Qaoa process.

We put at disposition: the minimal cost found, the state associated with this cost and the interpretation in terms of boolean variables of the Qubo problem.

Parameters

  • cost (float) – The minimum cost that was found.

  • final_state (str) – The quantum state associated with this cost.

  • values (dict[str, int]) – The associated variables with the state.

  • final_parameters – Values of the parameters of the ansatz for the best found cost.

  • final_params (OptimizerInput) –

Notes: This class is not meant to be instantiated directly by the user.

qaoa_solver(problem, depth, mixer, device, optimizer=Optimizer.POWELL, init_params=None)[source]

This function solves decision problems using Qaoa, the problem needs to be inputted as a Qubo expression.

Parameters

  • problem (Qubo) – Qubo expression representing the problem.

  • depth (int) – Number of layers in the ansatz, one layer being the application of one cost operator and one mixer operator.

  • mixer (Union[QaoaMixer, Observable]) – Type of the Mixer hamiltonian to be used or directly the mixer hamiltonian.

  • device (AvailableDevice) – The device that will be used to run the ansatz.

  • optimizer (Optimizer) – The optimizer used. Note: from our experience, not all of the available optimizers work well to solve Qaoa problems.

  • init_params (Optional[list[float]]) – List of parameters (float) used as the starting point for the optimization process, if empty initialize all parameters at 0.

Returns

A QaoaResult containing the minimal cost found and the associated state.

Return type

QaoaResult

Examples

>>> x0 = QuboAtom('x0')
>>> x1 = QuboAtom('x1')
>>> expr = -3*x0 - 5*x1 + 4*(x0 & x1)
>>> mixer = QaoaMixer(QaoaMixerType.MIXER_X)
>>> qaoa_solver(expr, 4, mixer, IBMDevice.AER_SIMULATOR, Optimizer.POWELL).final_state 
'01'