About the author:
Daniel is co-founder and CTO at Aqarios GmbH. He holds a M.Sc. in Computer Science from LMU Munich, and has published papers in reinforcement learning. He writes about technical topics in quantum computing.
jrnl · home about list my companies

# 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 1.

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.

Algorithm Type
Simulated Annealing classical
Tabu Search classical
Bruteforce classical
Dialectic Search classical
Parallel Tempering with Simulated Annealing classical
Population Annealing classical
Numpy Minimum Eigensolver classical
QAOA quantum-classical hybrid
Recursive QAOA quantum-classical hybrid
VQE quantum-classical hybrid
Recursive VQE quantum-classical hybrid
QBsolv with QPU quantum-classical hybrid
Population Annealing with QPU quantum-classical hybrid
Parallel Tempering with QPU quantum-classical hybrid
Grover Search quantum

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

Published on