Skip to content

Results are limited to QUBO Solver v0.9.1

Product news
You are reading QUBO Solver v0.9.1, an older version of this documentation. Go to the latest version (v0.10.0)

The classical pipeline

A QUBO problem on NN variables consists in a symmetric matrix QQ of size NΓ—NN\times N.

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

f(z)=zTQz=βˆ‘iQiizi+βˆ‘iβ‰ jQijzizj,zi∈{0,1}. 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.

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.

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.

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.

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