Quantum Approximate Optimization Algorithm
Master
Semester programme:Master of Applied IT
Client company:Fontys
Project description
The main question of the study is to understand how well a quantum computer can "solve" an optimization problem. The optimization problem was Maxcut and the algorithm is called Quantum Approximate Optimization Algorithm (QAOA). We studied QAOA using several experiments run on a quantum computer simulator developed by Fontys teachers and students. The Max-Cut problem involves dividing a graph's vertices into two groups in order to maximize the number of edges between them. It is practically impossible to solve optimally on a classic computer because it is an NP-hard problem, but quantum computers could theoretically do so.
Context
The major theme in this study are quantum computing and simulation, quantum algorithms graphs, software optimization.
Results
The study had two main results. The first result is that it showed that current quantum technology, which is inherently flawed (noisy), cannot approximate the maximum cut of a graph using QAOA reliably. The second main insight is that ideal quantum computing, which can only be achieved through simulation, is good enough at approximating the maxcut for slightly larger graphs (~15 nodes). It is widely acknowledged and demonstrated that current quantum hardware and technology is not good enough for any real uses. This study has once again shown this current limitation, but in a new context.
About the project group
I worked on this project during the first semester of my master. I had never worked on anything related to quantum computing. Especially at the beginning I was very exploritory which helped getting an understand of what was out there and choose a good subject to write a paper about.