Combinatorial Optimization Problems¶
All the famous NP problems can be formulated as minimization or maximization problems. They can either be represented in the form of clauses of boolean variables (the class CombinatorialProblem), an Ising (the class Ising) form or a Quadratic Unconstrained Binary Optimization (the class QUBO) form $-$ take a look at the Introduction.
Quantum Approximate Optimization Algorithm (QAOA)¶
The Quantum Approximate Optimization Algorithm (QAOA) is a widely-studied method for solving combinatorial optimization problems on NISQ devices.
For each combinatorial optimization problem, we can construct a QAOA variational ansätz from it. A quantum circuit can then be executed to determine the paramaters that optimize the variational ansätz. Once the optimal variables are found, another sampling job is ran to find the most probable states of the distribution corresponding to the optimized QAOA parameters. The state distribution that can be observed in this sampling job corresponds to the result of the combinatorial optimization problem.
Simulated Annealing and QUBO¶
At the same time, Qaptiva HPC is equipped with a Simulated Annealing (SA) solver, which can heuristically find a solution of such Ising or QUBO problems.
Solving Combinatorial Optimization problems on myQLM¶
One is therefore welcome to explore solving some of these NP problems either using the QAOA variational ansätze method or using SA. A list of the problems currently supported is provided below.
In general, this folder contains notebooks that combine different tools provided inside the qat.opt, qat.mc and qat.simulated_annealing namespaces.