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.

NP-hard problems for Simulated Quantum Annealing

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. Qaptiva 800s provides:

• Quantum Approximate Optimization Algorithm (QAOA) relying on gate-based computation

• Adiabatic Quantum Optimization (AQO) relying on analog computation

• Adiabatic Quantum Optimization for Rydberg quantum devices (RYD), relying on the Crossing Lattice embedding technique to target Rydberg atom devices

Gate-Based simulation - QAOA

Analog simulation - AQO

Analog simulation for Rydberg QPU - RYD

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.

NP-hard problems for the 3 types of quantum computation