The extended abstract for our research work “Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem” was accepted at the AQIS’20 conference yesterday. To researchers who have decades of publishing experience under their belt, this is akin to a baby taking his first steps. In this analogy, I am the proud parent and the baby is my research career. Hopefully, there will be a lot more milestones to come.
The preprint version of the paper is available on arXiv here. The one line synopsis of the work is given in the title itself. QAOA or the Quantum Approximate Optimization Algorithm framework of algorithms was developed by Edward Farhi, Sam Guttman and Jeffrey Goldstone in 2014. These algorithms try to find approximate solutions to (hard) combinatorial problems. The initial aim of QAOA was to find a better approximation ratio for the Max-Cut problem compared to the Goemans-Williamson approximation ratio which is deemed to be optimal by the Unique Games Conjecture.
To make a long story short, they did not succeed in their initial aim. The story does not end there. The original authors applied QAOA to another problem (Max E3Lin2) and seemingly did achieve a better approximation ratio than the best classical algorithm at that time. There is an excellent blog post by Scott Aaronson on this topic which you should check out if you are interested in this topic. I’ll paraphrase anyway. This was a huge deal at the time, and in Scott Aaronson’s words, “….this is the first time that a quantum algorithm has been proved to achieve a better approximation ratio for a natural NP-hard optimization problem than the best known classical algorithm achieves..”
The honeymoon did not last long. In a paper titled “Beating the random assignment on constraint satisfaction problems of bounded degree“, the who’s who of the theoretical computer science field came together in an “Avenger’s Assemble” moment to dismantle the throne and claim not only a better approximation ratio, but the optimal one (under reasonable complexity-theoretic assumptions). A lesser known work by C. Lin and Y. Zhu, later drew even but by then the community had moved on.
Just when everyone thought that QAOA would die a premature death, Farhi and Harrow managed to show that it is hard to classically simulate the output distribution even for very shallow depth QAOA circuits p=1). If this were possible then the Polynomial Hierarchy would collapse to the third level. While not on the same level as the P=NP problem, this in itself is a very significant result and conjectured to be false. Next, came along a new batch of researchers who modified QAOA to work on constrained optimization problems. This new version of QAOA was titled Quantum Alternating Operator Ansatz, and this breathed a new life into the field.
We applied the Quantum Alternating Operator Ansatz (abbreviated as QAOA+ from now on) to the matching problem. The matching problem is deceptively hard. While we have an efficient algorithm to find a maximum matching, most counting problems for matching problems are hard even for the bipartite case. We managed to give theoretical proof that the choice of initial state matters – W1 states are inherently better than the all zero state. We also obtain results that show the expected matching size of our QAOA+ circuit (for general graphs) is better than the expected matching size of a uniform distribution over all edges. The proof is limited to 2-regular graphs, and moving forward we want to extend this to general graphs. This might have complexity theoretic consequences with regards to sampling the output state and something that we will be working on. Lastly, we showed a new way to analyze QAOA and QAOA+ circuits for bounded depths, and we look forward to exploring whether our techniques extend to harder combinatorial problems.
I hope there was something in this for everyone. Until next time!