Maxcut QAOA - Quantum Algorithm
Project Description

I was super excited and honoured to have the opportunity to demo this project at the TKS booth during the TakeOver Innovation conference. The project is a python implementation of a relatively new quantum algorithm known as the Quantum Approximate Optimization Algorithm (QAOA). This project is exciting because it solves the MaxCut problem on a smaller relative timescale than classical computers, and thus demonstrates the potential for a quantum advantage.

01. The Problem

MaxCut is a problem in graph theory that involves a graph of N nodes and a set of connecting vertices that must be split into two subsets such that the number of edges that span the two sets is maximized. In plain English, imagine a telephone network with 5 interconnected landlines (shown above) - the goal is to separate the phones into two different houses so that the number of phone lines between the two houses is maximized. The real challange behind this problem comes with the addition of more nodes - add more phones, and the problem becomes exponentially more complicated, to the point where even supercomputers struggle to find the best answer.

02. The Algorithm

The QAOA works by encoding the graph into the Hamiltonian of a series of qubits on Rigetti's 19-qubit system. The algorithm then attempts to minimize the quantum program into a ground-state energy, which, by the nature of quantum mechanics, naturally encodes an approximation of the optimal solution. While it isn't perfect, the algorithm is able to work with a very high degree of accuracy for reasonable graph sizes. The current limitation to this algorithm is the number of qubits available - upon the development of higher-volume systems, more qubits will be open for use in both computation and error correction. At this point, quantum computers will be well on their way to demonstrating a quantum advantage over classical systems, which can only scale in a linear fashion compared to the exponential fashion that follows quantum computing.

03. The Experience

I had an incredible time demonstrating this project at the TakeOver conference! I was able to connect with experts from various industries ranging anywhere from pharma to machine learning and have great conversations about the future of quantum computing - especially at its intersection with machine learning! I also enjoyed hearing about the developments at the forefront of other industries because it showed me just how disruptive quantum computing will be in coming years. Be sure to check out my other quantum computing project which integrates machine learning to simulate potential pharmaceutical drugs!

Interested? Check out the project here! View Github Project