Analog vs digital quantum computing for certain optimization problems

Background

Quantum computing is an emerging technology that has significant disruptive power, because it opens up the possibility to tackle certain types of problems that are beyond the reach of classical computers.
Hardware development has gained significant momentum in recent years. It is expected by leading companies that the first noisy intermediate-scale quantum (NISQ) devices will be commercialized in the next 3 to 5 years. There are two types of quantum computers, analog and digital. The analog ones are based on quantum annealing, whereas the digital ones use a gate model and are more universal.
However, it is of yet unclear if there exist applications (algorithms) where NISQ computers can outperform their classical counterparts. The point in time where this is reached is typically called quantum advantage.

Problem to be studied

Combinatorial optimization problems are candidate applications for reaching quantum advantage on NISQ computers. Problems in this class include the MAXCUT and the Travelling Salesman problem, which are both NP-hard. It is not expected that quantum computers can solve NP-hard problems in polynomial time. They might, however, lead to better meta-heuristics as compared to their classical counterparts.
The Quantum Approximate Optimization Algorithm (QAOA) (Farhi, Edward,  Goldstone, Jeffrey and Gutmann, Sam, A quantum approximate optimization algorithm, arXiv preprint arXiv:1411.4028 ), which is a hybrid classical-quantum algorithm, is a metaheuristic that is a candidate for reaching quantum advantage on NISQ computers.
In this project we will focus on the MAXCUT problem, where one has to find the splitting of a graph in two parts which maximizes the number of edges that connect the two parts. This is equivalent to the problem of finding the ground state of typical spin-glass models, where the edges correspond to interactions between the spins.

Goals of the project

There are three primary goals of the project:

1. Developing a  sound theoretical understanding of both the quantum annealing and QAOA algorithms, including clarifying the recent developments and current state of the art.
2. Implementing both algorithms on actual quantum computers.  For execution on real devices, it is suggested to use D-wave's quantum annealing computer and IBM's gate based quantum computer. Both are available free online for trials with certain limitations to size (number of qubits) and/or run time. Simulators are also a viable alternative for testing. It is not expected that these resources are sufficient for solving problems which are large, but they will provide demonstrations of the possibilities.
3. Comparing the two types of algortihms. We can directly compare the performance on the present architectures. However, because of the limitations of current systems, a fair comparison of quantum annealing, and QAOA should also theoretically study the scaling of both approaches with the size of the system.

Time allowing, one should in addition aspire to find and test improvements on existing approaches.

The project will be in collaboration with researchers from SINTEF.