First Acceptance!

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!

Published by chatsagnik

I am a student of Computer Science Engineering at the West Bengal University of Technology (In-house), Calcutta. I prefer to think of myself as someone who archives moments, and later if possible reproduces them to the best of my ability. I sing and dance, both badly, but with great enthusiasm. I also love to learn. Be it Geo-politics or Crypto-currencies, I do not prefer to be in the dark about any topic which I find interesting. Although this does not help my academics to the extent I would like, this habit does have a beautiful side effect of making me extremely easy to converse with. Feel free to connect with me on Twitter or read up my posts in "Tasting Life in Retrospect". Positive criticism is always welcome, and food for thought about new exciting ideas are even more so.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: