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