The Max-Cut problem has been of continued research interest and has developed an extensive literature. The Max-Cut problem is a well-known combinatorial optimization problem which aims to find a division of a vertex set
into two parts maximizing the sum of weights over all the edges across the two vertex subsets in a given edge-weighted graph.
When applied in various real-world fields, the weight of the cut in the Max-Cut problem has real and concrete
implications. For example, for network design, the weight may represent the cost of some infrastructure.
The Max-Cut problem has many applications in various fields such as network design, statistical physics and VLSI design, circuit layout design,
and data clustering. Hence, in a nutshell, Max-cut has wide applications in various industries such as : Electronics Industry (Circuit design, VLSI design etc.), Finance Industry (Data clustering) etc.
The Max-Cut problem is one of the first problems proved to be NP-hard, meaning that there are no strongly efficient exact
algorithms. So many researchers turn their attention to find approximate algorithms and heuristic algorithms.
Hence, the main motivation was to improve upon existing heursitic algorithms like QAOA to solve Max-cut by introducing quantum or classical modifications or both.
What it does :
It basically solves smaller instances of Max-Cut problems yielding significantly better results. The probability of optimal strings being pulled out is 100% or relatively greater in WS-QAOA than in Standard QAOA. It involves two modifications in QAOA, namely :-
1. Quantum Modifications :
There is a lot of research going on in improving the original QAOA proposal. Egger et al. (see here) recently proposed a new variant of QAOA called the Warm-start QAOA (WS-QAOA) which demonstrated comparable performance with the Goemans-Williamson algorithm (the best known classical Algorithm for Max-cut) and even outperformed it in some instances. They showed how WS-QAOA successfully pulls out the optimal bit-strings with significant probabilities by destructively interfering with the unwanted strings/solutions. This would enable us to implement bigger problem instances on small depth circuits.
2. Classical Modificatons :
Moreover, QAOA has a direct correlation with the “Quantum Adiabatic Algorithm”, and this results in observable trends in the optimal parameters and the determination of optimal parameters is indeed a crucial step. Zhou et al. (see here) suggested two approaches, INTERP and FOURIER, to manipulate this structure for the purpose of finding optimal parameters. This heursitic parameter technique is particularly helpful in case of higher depths (p).
In this project, we deal with WS-QAOA and INTERP, and the performances of WS-QAOA and WS-QAOA w/ INTERP (on two simulators, namely : statevector_simulator and qasm_simulator) are analysed in terms of depth (p) and running time complexity while comparing with standard QAOA and QAOA w/ INTERP and ultimately demonstrated the superiority of WS-QAOA and WS-QAOA w/ INTERP. We also show how noise affects the performances of these algorithms by incorporating a “noise model” from an actual quantum device and also perform noise mitigation.
How I built it :
All the implementations were done in Qiskit. For sake of brevity and without loss of generality I chose a unweighted bi-partite graph (weighted graph with weight of all edges = 1 )to run alI the experiments on all the variants. First, for WS-QAOA I implemented the initial state circuit and the corresponding Mixer Hamiltonian and then implemented INTERP (which uses linear interpolation strategy for choosing initial parameters. Beginning from level p = 1, we optimize and linearly interpolate the curve generated by optimised parameters at level p to obtain a collection of good initial parameters for level p + 1).
Challenges I ran into :
Most of the time was spent in tackling debugging issues. While initially trying out various instances, a challenge encountered was choosing an optimiser because the continous relaxed version of QUBOs of certain instances were non-convex, hence all optimisers couldn't be employed.
Accomplishments that I am proud of :
It's a state-of-the-art algo (in conjunction with INTERP), wherein we observed remarkably good performances as the optimal solutions get pulled out with 100 % or significantly better probabilities in comparison to QAOA.
What I learned :
While going through number of research papers, I learnt VQE and QAOA in depth in the process.
What's next for "Methods to improve the QAOA for Max-Cut" :
I will try it :
- On larger instances (where the number of vertices are more).
- Other graph classes such as cyclic graphs, undirected d-Regular (udR) and weighted d-Regular graphs (wdR). Moreover, the same experiments can be tried by replacing INTERP with FOURIER.
- Our next immediate goal would be to use WS-QAOA and WS-QAOA w/ INTERP to solve instances of weighted MAX k-CUT problem (where k>2) which consists of finding a k-partition of a given weighted undirected graph G(V, E) such that the sum of the weights of the crossing edges is maximized.