Impact of graph structures for QAOA on MaxCut

Rebekah Herrman; Lorna Treffert; James Ostrowski; Phillip C. Lotshaw; Travis S. Humble; George Siopsis

doi:10.1007/s11128-021-03232-8

Impact of graph structures for QAOA on MaxCut

Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip C. Lotshaw, Travis S. Humble, George Siopsis

Research output: Contribution to journal › Article › peer-review

19 Scopus citations

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 graphs with specific structure; however, little is known about the general performance of the algorithm on arbitrary graphs. In this paper, we investigate how different graph characteristics correlate with QAOA performance at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices. Some good predictors of QAOA success relate to graph symmetries, odd cycles, and density. For example, on eight vertex graphs, the average probability for selecting an optimal solution for graphs that contain no odd cycles after three iterations of QAOA is 60.6 % compared to 48.2 % for those that do. 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 be used to identify classes of combinatorial problems that are likely to exhibit a quantum advantage.

Original language	English
Article number	289
Journal	Quantum Information Processing
Volume	20
Issue number	9
DOIs	https://doi.org/10.1007/s11128-021-03232-8
State	Published - Sep 2021

Funding

The authors would like to thank Ryan Bennink for his helpful comments on early drafts of this manuscript. This work was supported by DARPA ONISQ program under Award W911NF-20-2-0051. J. Ostrowski acknowledges the Air Force Office of Scientific Research Award, AF-FA9550-19-1-0147. G. Siopsis acknowledges the Army Research Office Award W911NF-19-1-0397. J. Ostrowski and G. Siopsis acknowledge the National Science Foundation Award OMA-1937008. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the US Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan. (http://energy.gov/downloads/doe-public-access-plan). The authors would like to thank Ryan Bennink for his helpful comments on early drafts of this manuscript. This work was supported by DARPA ONISQ program under Award W911NF-20-2-0051. J. Ostrowski acknowledges the Air Force Office of Scientific Research Award, AF-FA9550-19-1-0147. G. Siopsis acknowledges the Army Research Office Award W911NF-19-1-0397. J. Ostrowski and G. Siopsis acknowledge the National Science Foundation Award OMA-1937008. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the US Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan. ( http://energy.gov/downloads/doe-public-access-plan ).

Funders	Funder number
United States Government
National Science Foundation	DE-AC05-00OR22725, OMA-1937008
U.S. Department of Energy
Air Force Office of Scientific Research	AF-FA9550-19-1-0147
Army Research Office	W911NF-19-1-0397
Defense Advanced Research Projects Agency	W911NF-20-2-0051

Keywords

Correlation
Graph structures
MaxCut
QAOA

Access to Document

10.1007/s11128-021-03232-8

Cite this

@article{ae04c653a91b4bb79e6dfc99ab0b5b58,

title = "Impact of graph structures for QAOA on MaxCut",

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 graphs with specific structure; however, little is known about the general performance of the algorithm on arbitrary graphs. In this paper, we investigate how different graph characteristics correlate with QAOA performance at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices. Some good predictors of QAOA success relate to graph symmetries, odd cycles, and density. For example, on eight vertex graphs, the average probability for selecting an optimal solution for graphs that contain no odd cycles after three iterations of QAOA is 60.6 % compared to 48.2 % for those that do. 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 be used to identify classes of combinatorial problems that are likely to exhibit a quantum advantage.",

keywords = "Correlation, Graph structures, MaxCut, QAOA",

author = "Rebekah Herrman and Lorna Treffert and James Ostrowski and Lotshaw, {Phillip C.} and Humble, {Travis S.} and George Siopsis",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2021",

month = sep,

doi = "10.1007/s11128-021-03232-8",

language = "English",

volume = "20",

journal = "Quantum Information Processing",

issn = "1570-0755",

publisher = "Springer",

number = "9",

}

TY - JOUR

T1 - Impact of graph structures for QAOA on MaxCut

AU - Herrman, Rebekah

AU - Treffert, Lorna

AU - Ostrowski, James

AU - Lotshaw, Phillip C.

AU - Humble, Travis S.

AU - Siopsis, George

PY - 2021/9

Y1 - 2021/9

N2 - 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 graphs with specific structure; however, little is known about the general performance of the algorithm on arbitrary graphs. In this paper, we investigate how different graph characteristics correlate with QAOA performance at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices. Some good predictors of QAOA success relate to graph symmetries, odd cycles, and density. For example, on eight vertex graphs, the average probability for selecting an optimal solution for graphs that contain no odd cycles after three iterations of QAOA is 60.6 % compared to 48.2 % for those that do. 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 be used to identify classes of combinatorial problems that are likely to exhibit a quantum advantage.

AB - 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 graphs with specific structure; however, little is known about the general performance of the algorithm on arbitrary graphs. In this paper, we investigate how different graph characteristics correlate with QAOA performance at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices. Some good predictors of QAOA success relate to graph symmetries, odd cycles, and density. For example, on eight vertex graphs, the average probability for selecting an optimal solution for graphs that contain no odd cycles after three iterations of QAOA is 60.6 % compared to 48.2 % for those that do. 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 be used to identify classes of combinatorial problems that are likely to exhibit a quantum advantage.

KW - Correlation

KW - Graph structures

KW - MaxCut

KW - QAOA

UR - http://www.scopus.com/inward/record.url?scp=85114024104&partnerID=8YFLogxK

U2 - 10.1007/s11128-021-03232-8

DO - 10.1007/s11128-021-03232-8

M3 - Article

AN - SCOPUS:85114024104

SN - 1570-0755

VL - 20

JO - Quantum Information Processing

JF - Quantum Information Processing

IS - 9

M1 - 289

ER -

Impact of graph structures for QAOA on MaxCut

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this