# List of (quantum computing) algorithms for optimization and QUBOs

Combinatorial optimization problems are often one of the hardest problems (often being in the NP-hard complexity class) that can be solved. Often, without heuristics and approximating, problems scale extremely bad, with our current classical compute reaching their limits even for just small problem sizes of just a few hundred variables. For instance, with just 10 cities in a traveling salesman problem, there are over 3 million possible paths through these 10 cities to consider. With 50 cities, there are already over 1e+64 possible paths. Quantum computing (and especially Quantum Annealing) is expected to be able to solve such problem sizes, and even much larger ones, in a reasonable timeframe.

Below, a list of 15 algorithms that can be used for solving combinatorial optimization problems is shown. Some of these algorithms are purely classical, some are purely quantum, and some are hybrid. It should be noted that for the forseeable future, since we are in the noisy intermediate-scale quantum computing era (NISQ), hybrid methods will very likely be the algorithm of choice when using quantum computers. Evidently, these hybrid methods are already showing a measurable and substantial speedup over classical methods for a certain subset of for example Maximum Clique problems ¹.

The solvers below all work with quadratic unconstrained binary optimization (QUBO) problems.

This is by no means the definite list of all (quantum) algorithms for optimization problems out there. This list will grow over time.

Note that implementations for these algorithms can be found in the packages dwave-hybrid and qiskit.