Combinatorial optimization

As we hinted in the Annealing programming section, many problems with actual practical applications are combinatorial and can be represented as minimization or maximization ones. Here we will use the quantum formulations of such problems to encode and solve some of the most famous NP-hard problems.

However, it is not only annealing that allows us to encode and tackle such minimization or maximization problems. In fact, one can also use the gate-based and analog computing approaches to create custom circuits or custom schedules, which, when executed, should also give us the desired lowest energy, hence best answer. Here we present techniques achieving exactly that - the Quantum Approximate Optimization Algorithm (QAOA) relying on gate-based computation and Quantum Annealing (QA) - on analog computation.

Since using all the three quantum computation paradigmes above leads to solving the same general task, the NP-hard problems representations were abstracted to allow a seamless shift in generating such gate-based, analog or annealing problems - the so-called NP-hard problems generators.