Solvers

DecomposeQuboSolver(instance, config, solver_factory)

Bases: BaseSolver

Solver that leverages qubo decomposition techniques to solve subproblems and merge subsolutions to propose solutions of the original instance. Note, the QUBO instance is seen as a graph where variables are vertices, and coefficients represents weighted edges.

Scope: the decomposition only accepts qubo with positive coefficients off-diagonal coefficients.

Algorithm

Note, only one bitstring solution is returned.

Initialize the DecomposeQuboSolver with the given problem and configuration.

PARAMETER	DESCRIPTION
instance	The QUBO problem to solve. TYPE: QUBOInstance
config	Solver settings including backend and device. TYPE: SolverConfig
solver_factory	solver class for subproblems. TYPE: Callable[[QUBOInstance, SolverConfig], BaseSolver]

Source code in qubosolver/solver.py

def __init__(
    self,
    instance: QUBOInstance,
    config: SolverConfig | None,
    solver_factory: Callable[[QUBOInstance, SolverConfig], BaseSolver],
):
    """
    Initialize the DecomposeQuboSolver with the given problem and configuration.

    Args:
        instance (QUBOInstance): The QUBO problem to solve.
        config (SolverConfig): Solver settings including backend and device.
        solver_factory (Callable[[QUBOInstance, SolverConfig], BaseSolver]): solver class
            for subproblems.
    """
    if (
        instance.coefficients[~torch.eye(*instance.coefficients.shape, dtype=torch.bool)] < 0
    ).any():
        raise ValueError("Decomposition does not handle off-diagonal negative coefficients")

    # default is a quantum solver as we apply device-dependent decomposition
    super().__init__(
        QUBOInstance(instance.coefficients),
        config or SolverConfig(use_quantum=True),
    )
    self._solver_factory = solver_factory

    self.backend = self.config.backend
    self.device = self.config.device._device

    self.decomposition_config: DecompositionConfig = (
        self.config.decompose or DecompositionConfig()
    )

    # A cached version of `config` that we're going
    # to use for problems we do not wish to decompose.
    self._config_subproblems = SolverConfig.from_kwargs(
        **self.config.model_dump(exclude={"decompose"})
    )

solve()

Execute a solver by decomposing the instance. Note, the QUBO instance is seen as a graph where variables are vertices, and coefficients represents weighted edges.

Algorithm

RETURNS	DESCRIPTION
QUBOSolution	Final result after execution and postprocessing. Note, only one bitstring solution is returned. TYPE: QUBOSolution

Source code in qubosolver/solver.py

def solve(self) -> QUBOSolution:
    """
    Execute a solver by decomposing the instance.
    Note, the QUBO instance is seen as a graph where variables
    are vertices, and coefficients represents weighted edges.

    Algorithm:
        1. Initialize global solution and vertices to place.
        2. While we can apply decomposition:
            - Select a random vertex to place using device layout.
            - Apply a geometric search to obtain a set of vertices
              that can be placed on a device to form a subproblem.
            - Solve the subproblem with a solver.
            - Update the global solution and the vertices left to place.
        3. For remaining variables, we solve classically.

    Returns:
        QUBOSolution: Final result after execution and postprocessing.
            Note, only one bitstring solution is returned.
    """

    self.number_iterations = 0
    assert self.instance.size
    if self.instance.size <= self.decomposition_config.decompose_stop_number:
        solver = QuboSolverClassical(
            self.instance,
            SolverConfig(use_quantum=False, decompose=None),
        )
        return solver.solve()

    else:
        from qubosolver.algorithms.decompose import (
            compute_distance_interaction_matrix,
            geometric_search,
            interaction_matrix_from_placed,
            last_target_matrix,
            transfer_edge_values,
            update_global_solution,
            vertices_to_place,
        )

        global_solution = torch.full((self.instance.size,), -1)
        qubo_mat = self.instance.coefficients.clone()
        dist_matrix = compute_distance_interaction_matrix(
            self.device,
            qubo_mat,
            neglecting_inter_distance=self.decomposition_config.neglecting_inter_distance,
            neglecting_max_coefficient=self.decomposition_config.neglecting_max_coefficient,
        )

        # The following dictionary contain vertices to apply the decomposition search
        # where each vertex key maps to other blocking, separated and neighbors vertices
        # and gets updated as we iterate in the decomposition
        dict_vertices_to_place = vertices_to_place(
            dist_matrix,
            qubo_mat,
            separation_threshold=self.decomposition_config.neglecting_inter_distance,
        )

        transfer_edge_values(dict_vertices_to_place, dict(), global_solution, qubo_mat)
        while len(dict_vertices_to_place) > self.decomposition_config.decompose_stop_number:
            # find a first vertex to start the geometric search
            # random works better according to some performed numerics
            first_vertex_search = random.choice(list(dict_vertices_to_place.keys()))
            placed_vertices = geometric_search(
                qubo_mat,
                dict_vertices_to_place,
                first_vertex_search,
                self.decomposition_config.decompose_threshold,
                self.device,
            )
            if len(placed_vertices) <= self.decomposition_config.decompose_break_placement:
                break
            self.number_iterations += 1

            matrix_to_solve, map_index_vertices = interaction_matrix_from_placed(
                placed_vertices, self.device
            )
            qubo = QUBOInstance(matrix_to_solve)
            subsolver = self._solver_factory(qubo, self._config_subproblems)

            # only one bitstring is kept as per design choice of the
            # decomposition algorithm
            sub_solution = subsolver.solve().bitstrings[0]
            update_global_solution(
                global_solution=global_solution,
                sub_solution=sub_solution,
                mapping=map_index_vertices,
            )

            transfer_edge_values(
                dict_vertices_to_place,
                placed_vertices,
                global_solution,
                qubo_mat,
            )

        # classical resolution of last matrix
        matrix_to_solve, mapping_target_vertices = last_target_matrix(
            list(dict_vertices_to_place.keys()), qubo_mat
        )
        qubo = QUBOInstance(matrix_to_solve)
        lastsolver = QuboSolverClassical(
            qubo,
            SolverConfig(use_quantum=False, decompose=None),
        )
        sub_solution = lastsolver.solve().bitstrings[0]
        update_global_solution(
            global_solution=global_solution,
            sub_solution=sub_solution,
            mapping=mapping_target_vertices,
        )
        # Probabilities and counts are ignored as we return one solution
        qubosol = QUBOSolution(
            bitstrings=global_solution.unsqueeze(0).to(dtype=torch.float32),
            counts=torch.tensor([1], dtype=torch.int),
            costs=torch.Tensor(),
            probabilities=None,
        )
        qubosol.costs = qubosol.compute_costs(self.instance)
        qubosol.bitstrings = qubosol.bitstrings.int()
        return qubosol

QuboSolver(instance, config=None)

Bases: BaseSolver

Dispatcher that selects the appropriate solver (quantum or classical) based on the SolverConfig and delegates execution to it.

Source code in qubosolver/solver.py

def __init__(self, instance: QUBOInstance, config: SolverConfig | None = None):
    super().__init__(instance, config)
    self._solver: BaseSolver

    if config is None:
        self._solver = QuboSolverClassical(instance, self.config)
    else:
        if config.decompose:
            if self.config.use_quantum:
                solver_factory: type[BaseSolver] = QuboSolverQuantum
            else:
                solver_factory = QuboSolverClassical
            self._solver = DecomposeQuboSolver(instance, self.config, solver_factory)

        elif config.use_quantum:
            self._solver = QuboSolverQuantum(instance, config)
        else:
            self._solver = QuboSolverClassical(instance, config)

QuboSolverClassical(instance, config=None)

Bases: BaseSolver

Classical solver for QUBO problems. This implementation delegates the classical solving task to the external classical solver module (e.g., CPLEX, D-Wave SA, or D-Wave Tabu), as selected via the SolverConfig.

After obtaining the raw solution, postprocessing (e.g., bit-flip local search) is applied.

Source code in qubosolver/solver.py

def __init__(self, instance: QUBOInstance, config: SolverConfig | None = None):
    super().__init__(instance, config)
    # Optionally, you could instantiate Fixtures here for postprocessing:
    self.fixtures = Fixtures(self.instance, self.config)

QuboSolverQuantum(instance, config=None)

Bases: BaseSolver

Quantum solver that orchestrates the solving of a QUBO problem using embedding, drive shaping, and quantum execution pipelines.

Note: Negative off-diagonal coefficients are not supported.

Initialize the QuboSolver with the given problem and configuration.

PARAMETER	DESCRIPTION
instance	The QUBO problem to solve. TYPE: QUBOInstance
config	Solver settings including backend and device. TYPE: SolverConfig DEFAULT: None

Source code in qubosolver/solver.py

def __init__(self, instance: QUBOInstance, config: SolverConfig | None = None):
    """
    Initialize the QuboSolver with the given problem and configuration.

    Args:
        instance (QUBOInstance): The QUBO problem to solve.
        config (SolverConfig): Solver settings including backend and device.
    """
    super().__init__(instance, config or SolverConfig(use_quantum=True))

    if (
        instance.coefficients[~torch.eye(*instance.coefficients.shape, dtype=torch.bool)] < 0
    ).any():
        raise ValueError("Quantum solver does not handle off-diagonal negative coefficients")

    self._check_size_limit()

    self.backend = self.config.backend
    self.embedder = get_embedder(self.instance, self.config, self.backend)
    self.drive_shaper = get_drive_shaper(self.instance, self.config, self.backend)

    self._register: Register | None = None
    self._drive: Drive | None = None

drive(embedding)

Generate the drive sequence based on the given embedding.

PARAMETER	DESCRIPTION
embedding	The embedded register layout. TYPE: Register

RETURNS	DESCRIPTION
tuple	A tuple of - Drive: Drive schedule for quantum execution. - QUBOSolution: Initial solution of generated from drive shaper TYPE: tuple

Source code in qubosolver/solver.py

def drive(self, embedding: Register) -> tuple:
    """
    Generate the drive sequence based on the given embedding.

    Args:
        embedding (Register): The embedded register layout.

    Returns:
        tuple:
            A tuple of
                - Drive: Drive schedule for quantum execution.
                - QUBOSolution: Initial solution of generated from drive shaper

    """
    drive, qubo_solution = self.drive_shaper.generate(embedding)

    self._drive = drive
    return drive, qubo_solution

embedding()

Generate a physical embedding (register) for the QUBO variables.

RETURNS	DESCRIPTION
Register	Atom layout suitable for quantum hardware. TYPE: Register

Source code in qubosolver/solver.py

def embedding(self) -> Register:
    """
    Generate a physical embedding (register) for the QUBO variables.

    Returns:
        Register: Atom layout suitable for quantum hardware.
    """
    self.embedder.instance = self.instance
    self._register = self.embedder.embed()
    return self._register

solve()

Execute the full quantum pipeline: preprocess, embed, drive, execute, postprocess.

RETURNS	DESCRIPTION
QUBOSolution	Final result after execution and postprocessing. TYPE: QUBOSolution

Source code in qubosolver/solver.py

def solve(self) -> QUBOSolution:
    """
    Execute the full quantum pipeline: preprocess, embed, drive, execute, postprocess.

    Returns:
        QUBOSolution: Final result after execution and postprocessing.
    """
    # 1) try trivial else delegate to quantum solver
    if self.config.activate_trivial_solutions:
        trivial = self._trivial_solution()
        if trivial is not None:
            return trivial
    self._check_size_limit()

    # 2) Apply preprocessing if requested
    self.preprocess()

    embedding = self.embedding()

    drive, qubo_solution = self.drive(embedding)

    bitstrings, counts, _, _ = (
        qubo_solution.bitstrings,
        qubo_solution.counts,
        qubo_solution.probabilities,
        qubo_solution.costs,
    )
    if (
        len(bitstrings) == 0 and qubo_solution.counts is None
    ) or self.config.drive_shaping.optimized_re_execute_opt_drive:
        bitstrings, counts = self.execute(drive, embedding)

    bitstring_strs = bitstrings
    bitstrings_tensor = torch.tensor(
        [list(map(int, bs)) for bs in bitstring_strs], dtype=torch.float32
    )
    if counts is None:
        counts_tensor = torch.empty((0,), dtype=torch.int32)
    elif isinstance(counts, dict) or isinstance(counts, Counter):
        count_values = [counts.get(bs, 0) for bs in bitstring_strs]
        counts_tensor = torch.tensor(count_values, dtype=torch.int32)
    else:
        counts_tensor = counts

    solution = QUBOSolution(
        bitstrings=bitstrings_tensor,
        counts=counts_tensor,
        costs=torch.Tensor(),
        probabilities=None,
    )

    # Post-process fixations of the preprocessing and restore the original QUBO
    solution = self.post_process_fixation(solution)
    solution = self.post_process(solution)

    solution.costs = solution.compute_costs(self.instance)
    solution.probabilities = solution.compute_probabilities()
    solution.sort_by_cost()

    solution.bitstrings = solution.bitstrings.int()
    return solution