Solving QUBOs with qiskit QAOA example

# Solving QUBOs with qiskit QAOA example

Qiskit is quite an amazing library allowing users to build circuits for the Quantum Gate Model, and use algorithms such as QAOA to solve optimization problems in the form of quadratic programs.

In the following, an end-to-end example of a QUBO matrix in the form of a numpy array being solved with QAOA is shown. Analogously, VQE can also be used (simply replace QAOA with VQE in the example code below).

Note that this uses the aqua package, which is deprecated since 2021. Through some preliminiary tinkering I was not able to get the new version to work and thus the example below uses aqua. There are comments for the new imports included. One error I saw:

AttributeError: 'EvolvedOp' object has no attribute 'broadcast_arguments'

With some further investigation I noticed that MinimumEigenOptimizer is still using aqua imports in the background. However, I stopped here.

Below, the QUBO is solved using QAOA. First, a QuadraticProgram needs to be created. We add as many binary variables as we have in the QUBO (basically the size of one dimension), and a minimization term with the QUBO matrix itself. We then create a QASM Simulator instance, a QAOA instance, and solve it. We finally return the solution vector x and the f-value, which is computed as x^T Q x.

from qiskit import BasicAer
from qiskit.optimization import QuadraticProgram
from qiskit.optimization.algorithms import MinimumEigenOptimizer

from qiskit.aqua import aqua_globals, QuantumInstance
from qiskit.aqua.algorithms import QAOA

# # Note: These are the replacements of the aqua package.
# from qiskit.utils import algorithm_globals, QuantumInstance
# from qiskit.algorithms import QAOA


def solve(Q):
    qp = QuadraticProgram()
    [qp.binary_var() for _ in range(Q.shape[0])]
    qp.minimize(quadratic=Q)

    quantum_instance = QuantumInstance(BasicAer.get_backend('qasm_simulator'))
    qaoa_mes = QAOA(quantum_instance=quantum_instance)
    qaoa = MinimumEigenOptimizer(qaoa_mes)
    qaoa_result = qaoa.solve(qp)
    return [qaoa_result.x], [qaoa_result.fval]

With this code, one could now build a QUBO (e.g. using qubo-nn one can readily transform 20 optimization problems in an instant) and solve it using QAOA. For example, given the following QUBO, which is a Minimum Vertex Cover QUBO:

Q = [
    [-23.   0.   4.   4.   0.   4.]
    [  0. -31.   4.   4.   4.   4.]
    [  4.   4. -15.   0.   0.   0.]
    [  4.   4.   0. -23.   4.   0.]
    [  0.   4.   0.   4. -15.   0.]
    [  4.   4.   0.   0.   0. -15.]
]

The solution vector and the corresponding f-value (or energy from Quantum Annealing) is:

[1., 1., 0., 1., 0., 0.], -61.0

This is in fact a valid solution, as I've tested with Tabu Search. It should be noted that both the state vector backend and the QASM backend only allow up to 32 QuBits, i.e. 32 variables, to be solved. That is a major limitation right now.

Note that Aqarios is building a quantum computing platform that allows matching the best combination of algorithm and hardware to a business use case, such as load balancing in energy grids. This post documents part of my work at Aqarios.

Published on 2021-09-15