A tour of QUBO¶

The library you're looking at, qubo-solver, is a tool designed to let you take advantage of quantum computers to solve many problems without having to dig deep into the underlying quantum theory.

At the core of this library sits QUBO, the Quantum Unconstrained Binary Optimization. QUBO is an optimization problem that has three very important properties:

• entire classes of optimization problems frequently encountered in industry and research can be expressed as QUBO, which means that qubo-solver can be applied to numerous real-world problems;
• QUBO was designed to be executed efficiently on quantum computers, in particular the analog quantum computers produced by Pasqal;
• QUBO is actually simple to understand.

In this tutorial, we'll walk you through using QUBO and qubo-solver to solve a simple optimization problem, while other tutorials will dig deeper into the specifics of qubo-solver.

QUBO, intuitively¶

QUBO can be described as a puzzle.

Considered a switchboard with $N$ switches $1$, $2$, ..., $N$. Each switch can be set to on of off.

The switches are connected to an electrical grid. If both switches $i$ and $j$ are set to on, then the player add $Q_{i, j}$ points to their cost. In particular, if $i$ is set to on, the player immediately adds $Q_{i, i}$ to their cost. Note that $Q_{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 $Q_{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 $Q_{i, j}$. If they're all positive, we should set all the switches to off and our total cost will be $0$. 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¶

Given a set of coefficients $Q_{i, j}$ for $1 \leq i, j \leq N$, solving the QUBO problem for $Q$ consists in finding the booleans $x_1, x_2, ... x_n$ that minimize $\sum_{i, j} Q_{i,j}\cdot x_i\cdot x_j$.

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

Your first QUBO¶

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

$$Q = \begin{bmatrix}-10 & 0 \\ 0 & 5\end{bmatrix}$$

In [ ]:

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

%pip install qubo-solver --quiet

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

/Users/c.moussa/Library/Application Support/hatch/env/virtual/qubo-solver/PnNblJQR/qubo-solver/bin/python3: No module named pip
Note: you may need to restart the kernel to use updated packages.

Now, let's define the problem as a QUBO instance

In [ ]:

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 QUBOInstance import torch Q = torch.tensor([ [-10.0, 0], [ 0, 5.0], ], dtype=torch.float32) instance = QUBOInstance(Q)

To solve an instance of the problem, we'll create a QuboSolver.

For this example, let's take the simplest possible QuboSolver.

In [ ]:

from qubosolver.solver import QuboSolver
solver = QuboSolver(instance)
solution = solver.solve()
print(solution)

from qubosolver.solver import QuboSolver solver = QuboSolver(instance) solution = solver.solve() print(solution)

QUBOSolution(bitstrings=tensor([[1, 0]]), costs=tensor([-10.]), counts=None, probabilities=None, solution_status=<SolutionStatusType.TRIVIALONE: 'trivial-one'>)

This is a bit terse, but let's look at the details:

• solution.bitstrings is a sequence of 1s and 0s containing the best solution we found to this QUBO problem. Here, it means that $x_1$ should be set to 1 (the on position) and $x_2$ should be set to 0 (the off position).
• solution.costs is $-10.0$, which means that the best solution we found brought the total score to -10.

This specific solution found only one possible instance, but there will be cases in which the solver will find more than one solution.

Now, if you look at solution.probabilities, you'll see None. If you're a bit familiar with quantum computing, you may find this surprising as all quantum computing is probabilistic. In fact, that's because we didn't instruct the solver to use a quantum device, so it picked a non-quantum one.

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.

In [ ]:

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

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

from qubosolver.config import SolverConfig config = SolverConfig(use_quantum=True) solver = QuboSolver(instance, config) solution = solver.solve() print(solution)

QUBOSolution(bitstrings=tensor([[1, 0]]), costs=tensor([-10.]), counts=None, probabilities=None, solution_status=<SolutionStatusType.TRIVIALONE: 'trivial-one'>)

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 $2$ 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.

In [ ]:

%pip install qubovert --quiet

%pip install qubovert --quiet

/Users/c.moussa/Library/Application Support/hatch/env/virtual/qubo-solver/PnNblJQR/qubo-solver/bin/python3: No module named pip
Note: you may need to restart the kernel to use updated packages.

In [ ]:

# 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)

# 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)

{(0, 1): 8.0, (0,): -26.0, (1,): -27.0, (): 64.0, (0, 2): 8.0, (2,): -26.0, (0, 3): 8.0, (3,): -27.0, (0, 4): 8.0, (4,): -26.0, (0, 5): 6.0, (5,): -26.0, (0, 6): 6.0, (6,): -24.0, (0, 7): 8.0, (7,): -24.0, (1, 2): 8.0, (1, 3): 8.0, (1, 4): 8.0, (1, 5): 8.0, (1, 6): 8.0, (1, 7): 6.0, (2, 3): 8.0, (2, 4): 6.0, (2, 5): 8.0, (2, 6): 6.0, (2, 7): 8.0, (3, 4): 8.0, (3, 5): 8.0, (3, 6): 8.0, (3, 7): 6.0, (4, 5): 8.0, (4, 6): 6.0, (4, 7): 8.0, (5, 6): 8.0, (5, 7): 6.0, (6, 7): 6.0}

In [ ]:

# 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)

# 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)

In [ ]:

# Now, let's solve the problem using quantum

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

# Now, let's solve the problem using quantum solver = QuboSolver(instance, config) solutions = solver.solve() print(solutions)

QUBOSolution(bitstrings=tensor([[1., 0., 0., 0., 0., 1., 0., 0.],
        [1., 0., 0., 1., 0., 0., 0., 0.],
        [0., 0., 0., 1., 1., 0., 0., 0.],
        [1., 0., 1., 0., 0., 0., 0., 0.],
        [1., 0., 0., 0., 1., 0., 0., 0.],
        [0., 0., 0., 0., 0., 1., 1., 0.],
        [0., 0., 1., 0., 0., 0., 0., 1.],
        [0., 0., 0., 1., 0., 0., 0., 0.],
        [0., 1., 0., 0., 0., 0., 0., 0.],
        [0., 0., 1., 0., 0., 0., 0., 0.],
        [0., 0., 0., 0., 0., 1., 0., 0.],
        [0., 0., 0., 0., 1., 0., 0., 0.],
        [1., 0., 0., 0., 0., 0., 0., 0.],
        [0., 0., 0., 0., 0., 0., 0., 1.],
        [0., 0., 0., 0., 0., 0., 1., 0.]]), costs=tensor([-46., -45., -45., -44., -44., -42., -42., -27., -27., -26., -26., -26.,
        -26., -24., -24.]), counts=tensor([145,  13,  25, 157,  20,  10,  16,  22,  11,  18,   9,  18,   6,  15,
         15], dtype=torch.int32), probabilities=tensor([0.2900, 0.0260, 0.0500, 0.3140, 0.0400, 0.0200, 0.0320, 0.0440, 0.0220,
        0.0360, 0.0180, 0.0360, 0.0120, 0.0300, 0.0300]), solution_status=<SolutionStatusType.UNPROCESSED: 'unprocessed'>)

Our solver has evaluated all the most probable solutions to the problem and returns them as a QUBOSolution.

Let's unpack this by looking at each solution individually.

In [ ]:

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)): print(f"Solution {i} (probability {probability}): {solution} with costs {cost + constant}")

Solution 0 (probability 0.28999999165534973): tensor([1., 0., 0., 0., 0., 1., 0., 0.]) with costs 18.0
Solution 1 (probability 0.026000000536441803): tensor([1., 0., 0., 1., 0., 0., 0., 0.]) with costs 19.0
Solution 2 (probability 0.05000000074505806): tensor([0., 0., 0., 1., 1., 0., 0., 0.]) with costs 19.0
Solution 3 (probability 0.3140000104904175): tensor([1., 0., 1., 0., 0., 0., 0., 0.]) with costs 20.0
Solution 4 (probability 0.03999999910593033): tensor([1., 0., 0., 0., 1., 0., 0., 0.]) with costs 20.0
Solution 5 (probability 0.019999999552965164): tensor([0., 0., 0., 0., 0., 1., 1., 0.]) with costs 22.0
Solution 6 (probability 0.03200000151991844): tensor([0., 0., 1., 0., 0., 0., 0., 1.]) with costs 22.0
Solution 7 (probability 0.04399999976158142): tensor([0., 0., 0., 1., 0., 0., 0., 0.]) with costs 37.0
Solution 8 (probability 0.02199999988079071): tensor([0., 1., 0., 0., 0., 0., 0., 0.]) with costs 37.0
Solution 9 (probability 0.035999998450279236): tensor([0., 0., 1., 0., 0., 0., 0., 0.]) with costs 38.0
Solution 10 (probability 0.017999999225139618): tensor([0., 0., 0., 0., 0., 1., 0., 0.]) with costs 38.0
Solution 11 (probability 0.035999998450279236): tensor([0., 0., 0., 0., 1., 0., 0., 0.]) with costs 38.0
Solution 12 (probability 0.012000000104308128): tensor([1., 0., 0., 0., 0., 0., 0., 0.]) with costs 38.0
Solution 13 (probability 0.029999999329447746): tensor([0., 0., 0., 0., 0., 0., 0., 1.]) with costs 40.0
Solution 14 (probability 0.029999999329447746): tensor([0., 0., 0., 0., 0., 0., 1., 0.]) with costs 40.0

Normally, we should see a few solutions emerge with highest probability. Since quantum computing is non-deterministic, the list will change across runs.

Here, we show the solutions as bitstrings (the raw output of the quantum device), but fortunately, the library we're using can convert these bitstrings back to city names.

In [ ]:

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}")

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}")

Solution 0 (probability 0.28999999165534973): ({'Calais', 'Dover'}, {'Bristol', 'Lyon', 'Edinburgh', 'Marseille', 'Paris', 'London'}) costs 18.0
Solution 1 (probability 0.026000000536441803): ({'Edinburgh', 'Calais'}, {'Bristol', 'Lyon', 'Marseille', 'Dover', 'Paris', 'London'}) costs 19.0
Solution 2 (probability 0.05000000074505806): ({'Edinburgh', 'Marseille'}, {'Calais', 'Bristol', 'Lyon', 'Dover', 'Paris', 'London'}) costs 19.0
Solution 3 (probability 0.3140000104904175): ({'Lyon', 'Calais'}, {'Bristol', 'Edinburgh', 'Marseille', 'Dover', 'Paris', 'London'}) costs 20.0
Solution 4 (probability 0.03999999910593033): ({'Calais', 'Marseille'}, {'Bristol', 'Lyon', 'Edinburgh', 'Dover', 'Paris', 'London'}) costs 20.0
Solution 5 (probability 0.019999999552965164): ({'Paris', 'Dover'}, {'Calais', 'Bristol', 'Lyon', 'Edinburgh', 'Marseille', 'London'}) costs 22.0
Solution 6 (probability 0.03200000151991844): ({'Lyon', 'London'}, {'Calais', 'Bristol', 'Edinburgh', 'Marseille', 'Dover', 'Paris'}) costs 22.0
Solution 7 (probability 0.04399999976158142): ({'Edinburgh'}, {'Calais', 'Bristol', 'Lyon', 'Marseille', 'Dover', 'Paris', 'London'}) costs 37.0
Solution 8 (probability 0.02199999988079071): ({'Bristol'}, {'Calais', 'Lyon', 'Edinburgh', 'Marseille', 'Dover', 'Paris', 'London'}) costs 37.0
Solution 9 (probability 0.035999998450279236): ({'Lyon'}, {'Calais', 'Bristol', 'Edinburgh', 'Marseille', 'Dover', 'Paris', 'London'}) costs 38.0
Solution 10 (probability 0.017999999225139618): ({'Dover'}, {'Calais', 'Bristol', 'Lyon', 'Edinburgh', 'Marseille', 'Paris', 'London'}) costs 38.0
Solution 11 (probability 0.035999998450279236): ({'Marseille'}, {'Calais', 'Bristol', 'Lyon', 'Edinburgh', 'Dover', 'Paris', 'London'}) costs 38.0
Solution 12 (probability 0.012000000104308128): ({'Calais'}, {'Bristol', 'Lyon', 'Edinburgh', 'Marseille', 'Dover', 'Paris', 'London'}) costs 38.0
Solution 13 (probability 0.029999999329447746): ({'London'}, {'Calais', 'Bristol', 'Lyon', 'Edinburgh', 'Marseille', 'Dover', 'Paris'}) costs 40.0
Solution 14 (probability 0.029999999329447746): ({'Paris'}, {'Calais', 'Bristol', 'Lyon', 'Edinburgh', 'Marseille', 'Dover', 'London'}) costs 40.0

In our tests, the solver most commonly suggests grouping Lyon and Marseille on one side, and lump all other cities together. A surprisingly close second is grouping Lyon and Edinburgh, which indeed makes sense for our definition of graph partitioning.

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:

In [ ]:

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)

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¶

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 \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¶

Given how convenient QUBO is for execution on quantum computers, research on expressing problems as instances of QUBO is an active field. This page lists dozens of optimization problems and their expression as QUBO. In particular, Qubovert, 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¶

• Pasqal Community Portal (forums, chat, tutorials, examples, code library).
• GitHub Repository (source code, issue tracker).
• Professional Support (if you need tech support, custom licenses, a variant of this library optimized for your workload, your own QPU, remote access to a QPU, ...)