QAOA QUBO#

The QUBO problem and its QAOA implementation is discussed in plenty of detail in the QUBO tutorial. All the necessary ingredients and required steps to run QAOA are elaborated on in an easy to grasp manner.

Here, we provide a condensed implementation of QAOA for QUBO using all of the predefined functions.

Problem description#

Given an \(n\times n\) QUBO matrix \(Q\) and a vector \(x=(x_1,\dotsc,x_n)^T\) of binary variables \(x_i\in\{0,1\}\), find an assignment of the variables \(x_i\) that minimizes the cost function \(C(x)=x^TQx\).

Solve QUBO#

solve_QUBO(Q, depth, shots=5000, max_iter=50, backend=None, print_res=False)[source]#

Solves a Quadratic Unconstrained Binary Optimization (QUBO) problem using the Quantum Approximate Optimization Algorithm (QAOA).

This function creates the QAOA problem for a given QUBO. It defines a quantum argument as a QuantumArray of len(Q) QuantumVariables with size 1. It then runs the QAOA with the given quantum argument, depth (number of layers), maximum iterations of the classical optimizer, and shots and backend as measurement keyword arguments. The method performs classical post-processing on the solutions of the QAOA optimization: it calculates the cost for each such solution, sorts the solutions by their cost in ascending order, and returns the optimal solution.

Warning

For small QUBO instance the number of shots typically exceeds the number of possible solutions. In this case, even QAOA with depth=0, i.e., sampling from a uniform superposition, may yield the optimal solution as the classical post-processing amounts to brute force search! Performance of solve_QUBO for small instance may not be indicative of performance for large instances.

Parameters:

Qnp.array: QUBO matrix to solve.
depthint: The depth (amount of layers) of the QAOA circuit.
shotsint: The number of shots. The default is 5000.
max_iterint, optional: The maximal amount of iterations of the COBYLA optimizer in the QAOA algorithm. The default is 50.
backendBackendClient, optional: The backend to be used for the quantum simulation. By default, the Qrisp simulator is used.
print_resBoolean, optional: If set to True, the 5 best solutions are printed. The default is False.

Returns:

optimal_solutiontuple: A tuple where the first element is the cost value and the second element is the optimal bitstring. If print_res is set to True, the function prints the 5 best solutions with their respective costs.

Examples

from qrisp.qaoa import solve_QUBO
import numpy as np

Q = np.array(
    [
        [-17,  10,  10,  10,   0,  20],
        [ 10, -18,  10,  10,  10,  20],
        [ 10,  10, -29,  10,  20,  20],
        [ 10,  10,  10, -19,  10,  10],
        [ 0,   10,  20,  10, -17,  10],
        [ 20,  20,  20,  10,  10, -28],
    ]
)

solve_QUBO(Q, depth = 1, print_res=True)

Cost operator#

create_QUBO_cost_operator(Q)[source]#

Creates the cost operator for a QUBO instance with matrix Q. In the QAOA overview section this is also called the phase separator \(U_P\).

Parameters:

Qnp.array: QUBO matrix to solve.

Returns:

cost_operatorfunction: A function receiving a QuantumVariable and a real parameter \(\gamma\). This function performs the application of the cost operator.

Classical cost function#

create_QUBO_cl_cost_function(Q)[source]#

Creates the classical cost function for a QUBO instance with matrix Q that we are attempting to solve.

Parameters:

Qnp.array: QUBO matrix to solve.

Returns:

cl_cost_functionfunction: The classical cost function for the problem instance, which takes a dictionary of measurement results as input.

QUBO problem#

QUBO_problem(Q)[source]#

Creates a QAOA problem instance with appropriate phase separator, mixer, and classical cost function.

Parameters:

Qnp.array: QUBO matrix to solve.

Returns:

QAOAProblem: A QAOA problem instance for a given QUBO matrix Q.

Example implementation#

from qrisp import QuantumVariable, QuantumArray
from qrisp.qaoa import QUBO_problem, QUBO_obj
from operator import itemgetter
import numpy as np

Q = np.array(
    [
        [-17,  20,  20,  20,   0,  40],
        [  0, -18,  20,  20,  20,  40],
        [  0,   0, -29,  20,  40,  40],
        [  0,   0,   0, -19,  20,  20],
        [  0,   0,   0,   0, -17,  20],
        [  0,   0,   0,   0,   0, -28],
    ]
)

qarg = QuantumArray(qtype=QuantumVariable(1), shape=len(Q))

QUBO_instance = QUBO_problem(Q)
res = QUBO_instance.run(qarg=qarg, depth=1, max_iter=50)

That’s it! In the following, we print the 5 best solutions together with their cost values.

costs_and_solutions = [(QUBO_obj(bitstring, Q), bitstring) for bitstring in res.keys()]
sorted_costs_and_solutions = sorted(costs_and_solutions, key=itemgetter(0))

for i in range(5):
    print(f"Solution {i+1}: {sorted_costs_and_solutions[i][1]} with cost: {sorted_costs_and_solutions[i][0]} and probability: {res[sorted_costs_and_solutions[i][1]]}")