Executive Summary : | The research group aims to solve NP-Hard combinatorial optimization problems, which are of great interest in theoretical computer science and practical applications like delivery scheduling, airline crew paring, VLSI design, protein folding, and developing mRNA vaccines for COVID-19. They have developed solutions for the famous NP-Hard graph problem (Max-Cut) using both QAOA and oscillator-based techniques.
The project will continue their work on QAOA and oscillator-based algorithms by solving various NP-Hard combinatorial optimization problems other than Max-Cut. Two mathematical approaches will be used: Method 1: Creating the equivalent Hamiltonian for each NP-Hard optimization problem, and then generating the quantum circuit for QAOA or the Kuramoto model for oscillators based on the Hamiltonian. These models will be solved numerically using the same method as for Max-Cut, with some modifications as required. Method 2: Converting the given combinatorial problem to a Max-Cut problem by converting it to 3SAT (Boolean satisfiability problem) and then to Max-Cut. The solution of the MaxCut problem using the codes developed already will be converted to the solution for the given optimization problem.
As QAOA and the oscillator-based methods are heuristic solvers, it is not known whether method 1 or method 2 will lead to more accurate solutions. Exploring this is a major aim of the proposal. |