Quadratic Unconstrainted Binary Optimization Problem Tutorial via Basiq SDK

WOMANIUM Global Quantum Media Project Initiative — Winner of Global Quantum Media Project

Table of Contents:

01) The QMware Cloud Service
02) Introducing Basiq SDK
03) Understanding QUBO Problems
04) Variational Quantum Algorithms (VQAs)
05) The General QUBO Problem

Introduction

Quantum computing has ushered in a new era of computational possibilities, and one of its key applications is solving complex optimization problems more efficiently than classical computers. One such optimization problem is the Quadratic Unconstrained Binary Optimization (QUBO) problem. In this comprehensive tutorial, we will explore how to tackle QUBO using the Basiq SDK on the QMware Terra Quantum Cloud Service platform.

The QMware Cloud Service

QMware Terra Quantum Cloud Service is a hybrid quantum-classical cloud platform that offers access to both simulated and native quantum hardware.

QMware Cloud | quantum computing | hybrid quantum computing

Developed as a joint venture between Terra Quantum and NOVARION, it provides a user-friendly environment for developers and researchers to harness the power of quantum computing.

Some of its notable features include:

1. Quantum Hardware Access: QMware Cloud offers access to various quantum hardware, including simulators and real quantum computers, allowing users to experiment with quantum algorithms.
2. User-Friendly Interface: The platform boasts an intuitive interface, making it easy for users to develop and execute quantum applications seamlessly.
3. Quantum Programming Tools: QMware Cloud provides a range of tools and libraries to support quantum programming, making it accessible to both beginners and experts.
4. Security and Reliability: With a focus on security and reliability, QMware Cloud meets the stringent requirements of businesses and researchers in the quantum computing field.

Quantum cloud computing services | quantum cloud services

Introducing Basiq SDK

Basiq is a software development kit (SDK) developed by Terra Quantum. It is a powerful toolkit that empowers developers to write quantum algorithms and execute them on classical computers. At its core, Basiq relies on the Tensor Network formalism, a robust mathematical framework for representing quantum states and operations.

Some of the key features of Basiq include:

1. High-Level Programming Language: Basiq employs a high-level programming language based on Python, making it accessible to a wide range of developers.
2. Compiler: The SDK includes a compiler that translates quantum algorithms into a format compatible with classical computers.
3. Quantum Algorithm Library: Basiq comes with a library of quantum algorithms that serve as building blocks for creating more complex quantum solutions.

Quantum SDK | Software Development Kit | quantum algorithms

Understanding QUBO Problems

Before diving into the specifics of using Basiq SDK, let’s grasp the essence of QUBO problems. A QUBO problem involves finding a binary solution (0 or 1) that minimizes a quadratic function. These problems find applications in various fields, including machine learning, chemistry, and physics. For example:

• In machine learning, QUBO can help determine optimal weights for neural networks and clustering data points efficiently.
• In chemistry, it can assist in finding the lowest energy configuration of molecules and designing drug molecules.
• In physics, QUBO can be instrumental in solving complex quantum system problems and optimizing quantum circuits.

It’s worth noting that QUBO problems are considered NP-hard, making them challenging for classical computers to solve efficiently. However, quantum computers can leverage quantum effects to navigate the solution space more rapidly, making them a promising avenue for addressing such problems.

Variational Quantum Algorithms (VQAs)

Variational Quantum Algorithms (VQAs) are a class of quantum machine learning algorithms often employed to solve optimization problems like QUBO. The core components of a VQA include:

1. Cost Function: A function that measures the quality of a solution, with the goal of minimizing it.
2. Ansatz: A quantum circuit designed to represent the problem’s solution, with its parameters optimized during the algorithm’s execution.
3. Training Data: Pairs of inputs and outputs used for training the VQA, where inputs represent problem instances, and outputs are the corresponding solutions.

Image Credits: QMWare Cloud Service

The VQA workflow involves iteratively refining the ansatz to minimize the cost function. It follows these steps:

• Evaluate the cost function using the current ansatz.
• Use a classical optimizer to update the ansatz parameters.
• Repeat the above steps until the cost function converges to its minimum.
• The final ansatz serves as the solution to the problem.

This iterative process is adaptable to various quantum computing platforms, including Noisy Intermediate-Scale Quantum (NISQ) devices and fault-tolerant quantum computers.

Image Credits: QMWare Cloud Service

The General QUBO Problem

The QUBO model is expressed as an optimization problem, aiming to either minimize or maximize a target function, denoted as y, which is dependent on a vector of binary variables x and a square matrix of constants Q. Mathematically, it is represented as:

Where:

• x is a vector of binary variables.
• Q is a square matrix of constants q_ij​.

It is common to assume that Q is symmetric or in upper triangular form, which can be achieved as follows:

Symmetric Form:

For all i and j except i=j, replace q_ij​ by 1/2(​q_ij​+q_ji​)).

Upper Triangular Form:

For all i and j with j>i, replace q_ij​ by q_ij​+q_ji​. Then, replace all q_ij​ for j<i by 0.

In the following examples, we will work with the full, symmetric Q matrix rather than using the “upper triangular form.”

QUBO Example:

Consider the optimization problem:

Here, x1​, x2​, and x3​ are binary variables representing our decision choices.

The function to be minimized is a quadratic function in binary variables with both linear and quadratic components. The linear part can be expressed as −5x^2​−3x^2​−8x^2​.

We can transform this problem into a matrix form, as shown below:

This matrix notation allows us to succinctly represent the QUBO problem as:

In this model, the matrix Q encapsulates all the problem data, making the QUBO framework particularly appealing for combinatorial optimization problems. It provides an alternative to traditional constrained problem representations.

The optimal solution to this specific example is x=(0,1,1), which results in y=−9.

Implementing the Quadratic Unconstrained Binary Optimization (QUBO) problem using the Basiq SDK involves several steps, as shown in the provided code snippet. Let’s break down these steps in detail:

You

Step 1: Import Necessary Libraries and Initialize Basiq

In this step, you import the required modules from the Basiq SDK, including components for QUBO, VQE, circuit building, circuit visualization, and optimization. You also initialize Basiq and specify the number of OpenMP threads to be used.

from basiq import *
from basiq.algorithms.qubo import *
from basiq.algorithms.vqe import VQE
from basiq.algorithms.circuit_builder import TwoLocalCircuit, TwoLocalCircuitParameterized
from basiq.visualization.circuit_visualization import draw_circuit
from scipy.optimize import minimize as scipy_minimize
from noisyopt import minimizeCompass
from noisyopt import minimizeSPSA

# Initialize Basiq
print(bq_init())
set_omp_thread_number(1)

Step 2: Define the QUBO Problem

In this step, you create a QuadraticFunction object quad_prog to define the QUBO problem. You specify the binary variables 'x', 'y', and 'z', along with their respective bounds (0 and 1). Then, you define the objective function to be minimized, including the linear and quadratic coefficients.

quad_prog = QuadraticFunction("qubo")
quad_prog.add_variable(0, 1, VarType.BINARY, 'x')
quad_prog.add_variable(0, 1, VarType.BINARY, 'y')
quad_prog.add_variable(0, 1, VarType.BINARY, 'z')
quad_prog.minimize(linear=[-5,-3,-8], quadratic={('x', 'y'): 4, ('x', 'z'): 8, ('y', 'z'): 2})

Output:

Quadratic function qubo:
variable 1: x BINARY bound:[0,1]
variable 2: y BINARY bound:[0,1]
variable 3: z BINARY bound:[0,1]
objective: +4(x*y)+8(x*z)+2(y*z)-5x-3y-8z
sense:     ObjectiveSense.MINIMIZE

Step 3: Transform QUBO into a Hamiltonian

Here, you transform the QUBO problem into a quantum Hamiltonian. The to_ising() method converts the QUBO into an Ising Hamiltonian and returns the Hamiltonian operator along with an offset. This step is crucial for quantum computing applications.

hamiltonian, offset = quad_prog.to_ising()
print(quad_prog.to_string())
print()
print("offset: {}\noperator: {}".format(offset, hamiltonian.print_details()))
print(quad_prog.export_as_lp_string())

Output:

offset: -4.5
operator: WeightedPauliOperators:
-0.500000+0.000000j * 'ZII'
+1.500000+0.000000j * 'IIZ'
+1.000000+0.000000j * 'ZZI'
+2.000000+0.000000j * 'ZIZ'
+0.500000+0.000000j * 'IZZ'

Step 4: Set Up Quantum Engine and VQE Parameters

Here, you set up the quantum engine, determine the number of qubits n, and configure parameters for the Variational Quantum Eigensolver (VQE) algorithm. You specify the SU(2) gates (rotations), the number of repetitions (reps), and initialize parameter values.

qe = QEngine("qss")
n = hamiltonian.number_qbits
sample_rate = None
su2_gates = [QCircuit.ry, QCircuit.rz]
reps = 2

params = ["$par_"+str(i) for i in range(len(su2_gates)*n*(reps+1))]
initial_params = [(random.random() * 2 * np.pi - np.pi) for i in range(len(su2_gates)*n*(reps+1))]

Output:

<basiq> version: 23.4.23, thread mode: 1
WeightedPauliOperators:
-0.500000+0.000000j * 'ZII'
+1.500000+0.000000j * 'IIZ'
+1.000000+0.000000j * 'ZZI'
+2.000000+0.000000j * 'ZIZ'
+0.500000+0.000000j * 'IZZ'

[2.916641925382301, -1.9570752625110042, 2.2196374436230206, -0.5679536740918749, 1.454694533531807, 3.0020010291496595, 0.36429523265548847, -0.20993038590853663, -1.1959158809024537, 0.7740457577417028, 2.1147876135901384, -1.4579645384939957, -0.3546254162968614, -1.7622625208751492, -0.2226864331047187, 2.6425254150672384, 2.7001785505881895, -0.6823620934870784]
circuit with inital parameters:
Log level  : info
Trace level: 100000

Step 5: Create and Run VQE

In this step, you create the variational quantum circuit using the TwoLocalCircuitParameterized class, specifying the initial parameters. You then set up and run the VQE algorithm, optimizing the parameters to find the minimum eigenvalue, which corresponds to the solution of the QUBO problem.

var_form = TwoLocalCircuitParameterized(n, params, su2_gates, None, entanglement="linear", reps=reps, 
                                        insert_barriers=True, circuit_name="qubo")
print("circuit with initial parameters:")
print(draw_circuit(var_form.constructCircuit(initial_params)[0]))

vqe = VQE(qe, hamiltonian, var_form, initial_params, None, None)

result = vqe.run(scipy_minimize, sample_rate, optimizer_args=(), optimizer_kwargs={'method': 'nelder-mead'}, 
            jacobian=None, trace=0)

print("VQE solution parameters:\n", result['x'])
print("VQE eigenvalue:", result['fun'])

Output:

VQE starting with optimizer scipy.optimize._minimize.minimize method:nelder-mead and sample_rate:None ...

[|s0>:  0] world_rank:    0 , state_rank:    0 (state   0 of   1) my_node_id:    0 , num_nodes:    1 , ranks/node:  1 , threads/rank:  1 --useful
Classical optimization exited with an error index: 1
fev:3600  E => -4.497929627923661
Finnished.
VQE Total time: 1.18 s   fev/s: 3061.91

VQE solution parameters:
 [ 0.7653014  -2.94041136  2.92427259  0.43970798  1.5699237   3.1475731
  0.15631384 -0.35970092 -0.24366551 -0.13398711  3.20496603 -0.00809703
 -0.74706243  1.19023794 -0.05271085  5.30311732  1.64144474 -2.32137309]
VQE eigenvalue: -4.4979715334723895

Step 6: Classical Exact Calculation of the Eigenvalues

In this step, we perform a classical and exact calculation of the eigenvalues for the given Hamiltonian matrix (Q). This computation is carried out using numerical techniques. The eigenvalues represent the possible energy states of the quantum system associated with the QUBO problem. The code snippet calculates these eigenvalues and prints them along with their corresponding eigenvectors.

# classical (exact) calculation of the eigenvalues

#print("ham_matrix", hamiltonian.to_matrix())

w, v = np.linalg.eig(hamiltonian.to_matrix())
print("eigenvalues/eigenvectors:\n")
print(w)
print(v)
exact_eigenvalue = np.min(w)
print("Exact minimal eigenvalue (classical):", exact_eigenvalue)

Output:

# classical (exact) calculation of the eigenvalues

#print("ham_matrix", hamiltonian.to_matrix())

w, v = np.linalg.eig(hamiltonian.to_matrix())
print("eigenvalues/eigenvectors:\n")
print(w)
print(v)
exact_eigenvalue = np.min(w)
print("Exact minimal eigenvalue (classical):", exact_eigenvalue)

Step 6: Compare with Exact Classical Solution

Here, you calculate the exact classical solution by diagonalizing the Hamiltonian matrix. You compare the VQE result to the exact minimal eigenvalue of the QUBO problem.

w, v = np.linalg.eig(hamiltonian.to_matrix())
print("eigenvalues/eigenvectors:\n")
print(w)
print(v)
exact_eigenvalue = np.min(w)
print("Exact minimal eigenvalue (classical):", exact_eigenvalue)

exact_result = np.min(w) + offset
print("Exact Result:", np.real(exact_result))
print("VQE result:", result['fun'] + offset)

Output:

VQE starting with optimizer scipy.optimize._minimize.minimize method:nelder-mead and sample_rate:None ...

[|s0>:  0] world_rank:    0 , state_rank:    0 (state   0 of   1) my_node_id:    0 , num_nodes:    1 , ranks/node:  1 , threads/rank:  1 --useful
Classical optimization exited with an error index: 1
fev:3600  E => -4.497929627923661
Finnished.
VQE Total time: 1.18 s   fev/s: 3061.91

VQE solution parameters:
 [ 0.7653014  -2.94041136  2.92427259  0.43970798  1.5699237   3.1475731
  0.15631384 -0.35970092 -0.24366551 -0.13398711  3.20496603 -0.00809703
 -0.74706243  1.19023794 -0.05271085  5.30311732  1.64144474 -2.32137309]
VQE eigenvalue: -4.4979715334723895

Step 7: Extract and Display the Solution

Finally, you construct a quantum circuit using the optimized parameters and perform measurements to extract the solution. The results are displayed, showing the values of binary variables corresponding to the optimal solution of the QUBO problem.

This detailed implementation showcases how to use the Basiq SDK to solve QUBO problems efficiently using a Variational Quantum Eigensolver (VQE) approach and compare the results with exact classical solutions. It demonstrates the power of quantum computing in solving complex optimization problems.

circuit, qreg = var_form.constructCircuit(result['x'])
creg = circuit.declare_cbit_register("creg", n)

circuit.multi_measure(qreg, creg)
qe = QEngine("qss")
qe.execute(circuit)

print("Solution: ")

for i, c in enumerate(creg):
    print("{} = {}".format(quad_prog.variables[i].name, c.value), end=', ')

Output:

Exact Result: -9.0
VQE result: -8.99797153347239
Solution: 
x = 0, y = 1, z = 1, 

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: qubo

Minimize
 obj: - 5 x - 3 y - 8 z + [ 8 x*y + 16 x*z + 4 y*z ]/2
Subject To

Bounds
 0 <= x <= 1
 0 <= y <= 1
 0 <= z <= 1

Binaries
 x y z
End

Conclusion

In conclusion, the synergy between quantum computing and user-friendly SDKs like Basiq is transforming the landscape of optimization problems. With QMware Terra Quantum Cloud Service and Basiq SDK at your disposal, you can delve into the world of quantum computing and tackle intricate QUBO problems with ease. Quantum computing’s potential for optimization is boundless, and mastering tools like Basiq is a significant step toward harnessing this potential for real-world applications.

P.S. I extend my heartfelt gratitude to WOMANIUM and TerraQuantum for providing me the invaluable opportunity to access the QMWare Cloud Hybrid quantum-classical cloud platform service.