Impact of Graph Structures for QAOA on MaxCut
- URL: http://arxiv.org/abs/2102.05997v1
- Date: Thu, 11 Feb 2021 13:32:00 GMT
- Title: Impact of Graph Structures for QAOA on MaxCut
- Authors: Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw,
Travis S. Humble and George Siopsis
- Abstract summary: The quantum approximate optimization algorithm (QAOA) is a promising method of solving optimization problems using quantum computing.
We evaluate the performance of QAOA at depths at most three on the MaxCut problem for all connected non-isomorphic graphs.
Knowing the relationship between structure and performance can allow us to identify classes of problems that are likely to exhibit a quantum advantage.
- Score: 0.2609784101826761
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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. Some of the strongest predictors of
QAOA success are the existence of odd-cycles and the amount of symmetry in the
graph. The data generated from these studies are shared in a
publicly-accessible database to serve as a benchmark for QAOA calculations and
experiments. Knowing the relationship between structure and performance can
allow us to identify classes of combinatorial problems that are likely to
exhibit a quantum advantage.
Related papers
Err
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.