Skip to content Skip to main navigation Report an accessibility issue

Impact of Graph Structure on the Quantum Approximate Optimization Algorithm Performance

Dr. Rebekah Herrman

Postdoctoral Researcher

Industrial & Systems Engineering

The University of Tennessee, Knoxville

Friday, February 26, 2021   3:30pm


The quantum approximate optimization algorithm (QAOA) is a promising method of solving combinatorial optimization problems using quantum computing. QAOA on the MaxCut problem has been studied extensively on specific families of graphs, however, little is known about the algorithm on arbitrary graphs.  We evaluate the performance of QAOA at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices and analyze  how graph structure affects QAOA performance. In this seminar, we introduce quantum computing and graph theory concepts, and discuss the relationship between graph structure and QAOA for MaxCut.



Dr. Rebekah Herrman is a postdoctoral researcher in the Industrial and Systems Engineering department at the University of Tennessee Knoxville. She received her Ph.D. in mathematics in 2020 from the University of Memphis with a focus in combinatorics. While there, she studied graph theory games and optimization problems on graphs. Aside from graph theory, her current research interest is quantum optimization, specifically the quantum approximate optimization algorithm.