Solving MIS by solving a QUBO¶

qubo-solver is a package aimed at solving quadratic unconstrained binary optimization (QUBO) problems. MIS can be expressed as a QUBO, and thus can be solved with the solvers available in the library. Let us retake the example of the first tutorial and show the workflow.

In [1]:

import networkx as nx
from mis import MISInstance, MISSolution

# Create a new networkx graph instance to be populated with DIMACS data.
graph = nx.Graph()


with open("./datasets/dimacs/a265032_1tc.8.txt", "r") as f:
    for line in f:
        if line.startswith("c"):  # Comment line in DIMACS file.
            continue
        elif line.startswith("p"):  # Problem definition, i.e. # nodes and edges.
            _, _, num_nodes, num_edges = line.strip().split()
            # Preset graph node labels as there might be isolated ones.
            graph.add_nodes_from(range(1, int(num_nodes) + 1))

        elif line.startswith("e"):
            _, node1, node2 = line.strip().split()
            graph.add_edge(int(node1), int(node2))

instance = MISInstance(graph)

import networkx as nx from mis import MISInstance, MISSolution # Create a new networkx graph instance to be populated with DIMACS data. graph = nx.Graph() with open("./datasets/dimacs/a265032_1tc.8.txt", "r") as f: for line in f: if line.startswith("c"): # Comment line in DIMACS file. continue elif line.startswith("p"): # Problem definition, i.e. # nodes and edges. _, _, num_nodes, num_edges = line.strip().split() # Preset graph node labels as there might be isolated ones. graph.add_nodes_from(range(1, int(num_nodes) + 1)) elif line.startswith("e"): _, node1, node2 = line.strip().split() graph.add_edge(int(node1), int(node2)) instance = MISInstance(graph)

In [2]:

import sys
if sys.version_info[1] < 13: # qubo-solver is only available up to python 3.12 versions
    ! pip install qubo-solver --quiet

    from qubosolver import QUBOInstance
    qubo_mis = QUBOInstance(instance.to_qubo(penalty=None))
    print(qubo_mis)
    print(qubo_mis.coefficients)

import sys if sys.version_info[1] < 13: # qubo-solver is only available up to python 3.12 versions ! pip install qubo-solver --quiet from qubosolver import QUBOInstance qubo_mis = QUBOInstance(instance.to_qubo(penalty=None)) print(qubo_mis) print(qubo_mis.coefficients)

ERROR: Could not install packages due to an OSError: [Errno 28] No space left on device

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[2], line 5
      2 if sys.version_info[1] < 13: # qubo-solver is only available up to python 3.12 versions
      3     get_ipython().system(' pip install qubo-solver --quiet')
----> 5     from qubosolver import QUBOInstance
      6     qubo_mis = QUBOInstance(instance.to_qubo(penalty=None))
      7     print(qubo_mis)

ModuleNotFoundError: No module named 'qubosolver'

Using a classical solver¶

In [3]:

if sys.version_info[1] < 13: 
    from qubosolver.config import SolverConfig
    from qubosolver.solver import QuboSolver

    config = SolverConfig(use_quantum=False) # will use a local emulator
    solver = QuboSolver(qubo_mis, config)
    solution = solver.solve()

    # to turn QUBO solutions to MIS
    bitstrings_to_nodes = [row.nonzero(as_tuple=True)[0].tolist() for row in solution.bitstrings if row.sum().item() > 0]

    # take only the first solution
    mis_sol = MISSolution(instance, frequency=1.0, nodes=bitstrings_to_nodes[0])
    mis_sol.draw()
    print("Solution nodes: ", mis_sol.nodes)
    print("Solution frequency:", mis_sol.frequency)
    print("Solution size:", mis_sol.size)

if sys.version_info[1] < 13: from qubosolver.config import SolverConfig from qubosolver.solver import QuboSolver config = SolverConfig(use_quantum=False) # will use a local emulator solver = QuboSolver(qubo_mis, config) solution = solver.solve() # to turn QUBO solutions to MIS bitstrings_to_nodes = [row.nonzero(as_tuple=True)[0].tolist() for row in solution.bitstrings if row.sum().item() > 0] # take only the first solution mis_sol = MISSolution(instance, frequency=1.0, nodes=bitstrings_to_nodes[0]) mis_sol.draw() print("Solution nodes: ", mis_sol.nodes) print("Solution frequency:", mis_sol.frequency) print("Solution size:", mis_sol.size)

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[3], line 2
      1 if sys.version_info[1] < 13: 
----> 2     from qubosolver.config import SolverConfig
      3     from qubosolver.solver import QuboSolver
      5     config = SolverConfig(use_quantum=False) # will use a local emulator

ModuleNotFoundError: No module named 'qubosolver'

Using a quantum solver¶

In [4]:

if sys.version_info[1] < 13: 
    config = SolverConfig(use_quantum=True) # will use a local emulator
    solver = QuboSolver(qubo_mis, config)
    solution = solver.solve()

    # to turn QUBO solutions to MIS
    bitstrings_to_nodes = [row.nonzero(as_tuple=True)[0].tolist() for row in solution.bitstrings if row.sum().item() > 0]

    # take only the first solution
    mis_sol = MISSolution(instance, frequency=solution.probabilities[0], nodes=bitstrings_to_nodes[0])
    mis_sol.draw()
    print("Solution nodes: ", mis_sol.nodes)
    print("Solution frequency:", mis_sol.frequency)
    print("Solution size:", mis_sol.size)

if sys.version_info[1] < 13: config = SolverConfig(use_quantum=True) # will use a local emulator solver = QuboSolver(qubo_mis, config) solution = solver.solve() # to turn QUBO solutions to MIS bitstrings_to_nodes = [row.nonzero(as_tuple=True)[0].tolist() for row in solution.bitstrings if row.sum().item() > 0] # take only the first solution mis_sol = MISSolution(instance, frequency=solution.probabilities[0], nodes=bitstrings_to_nodes[0]) mis_sol.draw() print("Solution nodes: ", mis_sol.nodes) print("Solution frequency:", mis_sol.frequency) print("Solution size:", mis_sol.size)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[4], line 2
      1 if sys.version_info[1] < 13: 
----> 2     config = SolverConfig(use_quantum=True) # will use a local emulator
      3     solver = QuboSolver(qubo_mis, config)
      4     solution = solver.solve()

NameError: name 'SolverConfig' is not defined