Skip to content
Pasqal Documentation

A tour of QUBO

QUBO, intuitively

Section titled “QUBO, intuitively”

QUBO can be described as a puzzle.

Considered a switchboard with NN switches 11, 22, ..., NN. Each switch can be set to on of off.

The switches are connected to an electrical grid. If both switches ii and jj are set to on, then the player add Qi,jQ_{i, j} points to their cost. In particular, if ii is set to on, the player immediately adds Qi,iQ_{i, i} to their cost. Note that Qi,jQ_{i, j} can be negative, in which case this decreases the total cost.

What is are best ways to set the switches to ensure the lowest possible cost?

This will, of course, depend on the values of Qi,jQ_{i, j}. If all the values are negative, for instance, we should set all the switches to on and our total cost will be the sum of all Qi,jQ_{i, j}. If they're all positive, we should set all the switches to off and our total cost will be 00. In most cases, we'll need to ponder which switches to set on, as they can have both positive and negative contributions depending on the setting of other switches.

QUBO may have several solutions.

QUBO, formally

Section titled “QUBO, formally”

Given a set of coefficients Qi,jQ_{i, j} for 1≤i,j≤N1 \leq i, j \leq N, solving the QUBO problem for QQ consists in finding the booleans x1,x2,...xnx_1, x_2, ... x_n that minimize ∑i,jQi,j⋅xi⋅xj\sum_{i, j} Q_{i,j}\cdot x_i\cdot x_j.

Equivalently, given a matrix QQ, solving the QUBO problem for QQ consists in finding the vectors xx of booleans that minimize ⊺x⋅Q⋅x^\intercal x\cdot Q \cdot x.

Your first QUBO

Section titled “Your first QUBO”

Let's start with a simple (and very artificial) QUBO.

Q=[−10amp;00amp;5]Q = \begin{bmatrix}-10 & 0 \\ 0 & 5\end{bmatrix}

# Before we proceed, we need to install qubo-solver.


%pip install qubo-solver --quiet
from qubosolver.solver import QUBOInstance
import torch


Q = torch.tensor([
    [-10.0, 0],
    [ 0, 5.0],
], dtype=torch.float32)
instance = QUBOInstance(Q)
from qubosolver.solver import QuboSolver
solver = QuboSolver(instance)
solution = solver.solve()
print(solution)

Once more, with quantum

Section titled “Once more, with quantum”

Let's change the options to use a quantum device. For the sake of this tutorial, we'll assume that you do not have access to a physical QPU and we'll use a quantum emulator.

from qubosolver.config import SolverConfig
config = SolverConfig(use_quantum=True)


solver = QuboSolver(instance, config)
solution = solver.solve()
print(solution)

Graph partitioning

Section titled “Graph partitioning”

Let's now apply the solver to a real problem: graph partitioning.

In this problem, we are given a graph, for instance a map, consisting in nodes (places) and edges (roads). Each edge may have a cost. The objective of 22 graph partioning problem is to split the graph into two sets of nodes with the smallest numbers of edges between these sets.

Path-finding applications on complex maps such as Google Maps uses such algorithms to preprocess and simplify maps to make finding directions much faster, especially on lengthy journeys crossing multiple states or countries.

Graph partitioning has a fairly simple translation to QUBO, but for the sake of simpicity, we'll use an existing library. If you wish to read the detail of the conversion, you may find the relevant mathematics in Ising formulations of many NP problems, by Andrew Lucas (external).

%pip install qubovert --quiet
# Use qubovert to convert the original problem to a qubo.


from qubovert.problems import GraphPartitioning


edges = {
    # French side
    ("Paris", "Lyon"), ("Lyon", "Marseille"), ("Paris", "Marseille"), ("Paris", "Calais"),
    # British side
    ("London", "Bristol"), ("London", "Edinburgh"), ("London", "Dover"),
    # Connections
    ("Calais", "Dover"), ("Paris", "London"),
}


problem = GraphPartitioning(edges)
as_qubo = problem.to_qubo()
print(as_qubo)
# Convert from qubovert's format to qubo-solver's
from qubovert.utils import qubo_to_matrix


# The QUBO problem created by qubovert is actually a slight extension of QUBO,
# with an additional constant. We need to remove this constant to make it a
# regular QUBO for qubosolver.
#
# This will not affect the results of qubo-solver.
constant = as_qubo.pop(())
Q = qubo_to_matrix(as_qubo, symmetric=True)


# Now turn this into a QUBO instance for qubo-solver.
instance = QUBOInstance(Q)
# Now, let's solve the problem using quantum


solver = QuboSolver(instance, config)
solutions = solver.solve()
print(solutions)
for (i, (solution, cost, probability)) in enumerate(iterable=zip(solutions.bitstrings, solutions.costs, solutions.probabilities)):
    print(f"Solution {i} (probability {probability}): {solution} with costs {cost + constant}")
for (i, (solution, cost, probability)) in enumerate(iterable=zip(solutions.bitstrings, solutions.costs, solutions.probabilities)):
    readable_solution = problem.convert_solution(solution)
    print(f"Solution {i} (probability {probability}): {readable_solution} costs {cost + constant}")

Running it on a Quantum Computer

Section titled “Running it on a Quantum Computer”

So far, we have used an emulator to solve our instances of QUBO. With qubo-solver, you can just as well run the code on a physical Quantum Computer. The example below shows how to access a QPU with Pasqal Cloud:

from qubosolver.config import BackendConfig, BackendType


# Replace with your username, project id and password on the Pasqal Cloud.
USERNAME="username"
PROJECT_ID="123"
PASSWORD=None


if PASSWORD is not None:
    config = SolverConfig(
        backend_config = BackendConfig(
            backend=BackendType.REMOTE_QPU,
            username=USERNAME,
            project_id=PROJECT_ID,
            password=PASSWORD
        ),
    )


    # Run the solver
    solver = QuboSolver(instance, config)
    solutions = solver.solve()


    # Display results
    print(solutions)

Limitations

Section titled “Limitations”

As of this writing, qubo-solver cannot solve all QUBO problems.

Its main limitation is that, in the current version, it can only solve problems for which Q_{i, j} => 0 if i≠ji \neq j. In other words, individual switches can have a negative cost, but the combination of two distinct switches always has a positive cost.

That is because the first reason for which this solver was developed was to demonstrate how to efficiently use analog quantum devices, and this subclass of QUBO can be executed extremely efficiently on such devices.

We are currently hard at work on a more powerful version of qubo-solver that lifts this limitation.

Going further

Section titled “Going further”

Given how convenient QUBO is for execution on quantum computers, research on expressing problems as instances of QUBO is an active field. This page (external) lists dozens of optimization problems and their expression as QUBO. In particular, Qubovert (external), the third-party library we've used in this tutorial, offers mechanisms to encode a number of well-known problems to QUBO.

Getting in touch

Section titled “Getting in touch”