Solving with a decomposition¶

To solve large QUBO instances using a quantum approach, we can set in SolverConfig the decompose argument to True and set several decomposition hyperparameters. This will use an iterative algorithm that solves a subproblem (found by placing a subset variables heuristically on a device).

In [ ]:

from qubosolver import QUBOInstance
from qubosolver.solver import QuboSolver
from qubosolver.config import SolverConfig, DecompositionConfig

from qubosolver import QUBOInstance from qubosolver.solver import QuboSolver from qubosolver.config import SolverConfig, DecompositionConfig

In [ ]:

import torch

def generate_qubo_matrix(
    size: int, density: float, value_range: tuple[int, int], seed: int | None = None
) -> torch.Tensor:
    """Generate a random symmetric qubo matrix with negative diagonal coefficients
       and positive off-diagonal elements.

    Args:
        size (int): Size of qubo.
        density (float): Density.
        value_range (tuple[int, int]): Value range of elements.
        seed (int | None, optional): Random seed for reproducibility. Defaults to None.

    Returns:
        torch.Tensor: Qubo matrix.
    """

    import numpy as np

    if seed is not None:
        np.random.seed(seed)
    matrix = np.zeros((size, size))
    for i in range(size):
        matrix[i, i] = -np.abs(np.random.uniform(0, 100))  # Negative diagonal
        for j in range(i + 1, size):
            if np.random.rand() < density:
                value = np.abs(
                    np.random.uniform(value_range[0], value_range[1])
                )  # Positive off-diagonal
                matrix[i, j] = value
                matrix[j, i] = value
    return torch.tensor(matrix)

import torch def generate_qubo_matrix( size: int, density: float, value_range: tuple[int, int], seed: int | None = None ) -> torch.Tensor: """Generate a random symmetric qubo matrix with negative diagonal coefficients and positive off-diagonal elements. Args: size (int): Size of qubo. density (float): Density. value_range (tuple[int, int]): Value range of elements. seed (int | None, optional): Random seed for reproducibility. Defaults to None. Returns: torch.Tensor: Qubo matrix. """ import numpy as np if seed is not None: np.random.seed(seed) matrix = np.zeros((size, size)) for i in range(size): matrix[i, i] = -np.abs(np.random.uniform(0, 100)) # Negative diagonal for j in range(i + 1, size): if np.random.rand() < density: value = np.abs( np.random.uniform(value_range[0], value_range[1]) ) # Positive off-diagonal matrix[i, j] = value matrix[j, i] = value return torch.tensor(matrix)

In [ ]:

decomposable_qubo = QUBOInstance(generate_qubo_matrix(80, 0.30, (0, 20), 1))

config = SolverConfig(use_quantum=True, decompose=DecompositionConfig())
solver = QuboSolver(decomposable_qubo, config)

decomposable_qubo = QUBOInstance(generate_qubo_matrix(80, 0.30, (0, 20), 1)) config = SolverConfig(use_quantum=True, decompose=DecompositionConfig()) solver = QuboSolver(decomposable_qubo, config)

In [ ]:

solver.solve()

solver.solve()

Out[ ]:

QUBOSolution(bitstrings=tensor([[1., 1., 1., 1., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 1., 1., 0.,
         1., 1., 0., 0., 0., 0., 1., 0., 0., 1., 0., 0., 0., 0., 1., 0., 1., 1.,
         1., 0., 0., 0., 1., 1., 1., 1., 0., 0., 0., 0., 0., 1., 1., 1., 0., 1.,
         1., 0., 1., 0., 1., 0., 0., 1., 0., 0., 1., 0., 0., 1., 0., 0., 0., 1.,
         1., 1., 0., 0., 1., 0., 0., 0.]]), costs=tensor([146.9694]), counts=tensor([1], dtype=torch.int32), probabilities=None, solution_status=<SolutionStatusType.UNPROCESSED: 'unprocessed'>)

In [ ]:

solver._solver.number_iterations

solver._solver.number_iterations

Out[ ]:

4