Skip to content

The classical pipeline

A QUBO problem on \(N\) variables consists in a symmetric matrix \(Q\) of size \(N\times N\).

Solving a QUBO problem means to find the bitstring \(z=(z_1,...,z_N)\in \{0, 1\}^N\) that minimizes the quantity

\[ f(z) = z^TQz= \sum_i Q_{ii} z_i + \sum_{i \neq j} Q_{ij} z_i z_j, \quad z_i \in \{0,1\}. \]

Qubo Solver's classical machinery runs entirely on CPU, without going through the quantum pipeline, and serves three purposes:

  1. Solvers as a baseline — exact or heuristic algorithms to solve a QUBO instance from scratch, to validate or compare against the quantum pipeline.
  2. Solvers as a refinement step — some solvers take an initial solution and improve it, which is useful to post-process the output of a quantum solver.
  3. Transforms to reduce or adapt an instance before solving — fixing variables to shrink the problem, or removing negative off-diagonal coefficients so it becomes embeddable on a quantum device.

Baseline: solving from scratch

Solvers that don't need a starting point are the simplest way to get a reference solution: an exact solve, or a fast heuristic to compare quality and runtime against the quantum pipeline. See Solvers for the full list.

Refinement: improving an existing solution

Solvers that take an initial solution can post-process the result of any other solver, including a quantum one — for example, running local bitflips on a quantum sampler's output to squeeze out a better bitstring. See Solvers for the refinement algorithms and an example.

Adapting the instance: transforms

Transforms change the Instance itself before it reaches a solver, and record enough history to map a Solution of the transformed problem back to the original one. Some transforms are exact — variable fixing only fixes a variable when it is guaranteed to be optimal, so the transformed problem is equivalent to the original — while others are approximations: zeroing negative off-diagonal coefficients (needed to make an instance embeddable on a quantum device) changes the objective, and should be used with that trade-off in mind. See Transforms for details on each.

Where to go next

  • Choose a baseline or refinement algorithm in Solvers.
  • Reduce or adapt an instance before solving in Transforms.