Paper Info
Title
Lower Bounds On Circuit Depth Of The Quantum Approximate Optimization Algorithm
Abstract
The quantum approximate optimization algorithm (QAOA) is a method of approximately solving combinatorial optimization problems. While QAOA is developed to solve a broad class of combinatorial optimization problems, it is not clear which classes of problems are best suited for it. One factor in demonstrating quantum advantage is the relationship between a problem instance and the circuit depth required to implement the QAOA method. As errors in noisy intermediate-scale quantum (NISQ) devices increase exponentially with circuit depth, identifying lower bounds on circuit depth can provide insights into when quantum advantage could be feasible. Here, we identify how the structure of problem instances can be used to identify lower bounds for circuit depth for each iteration of QAOA and examine the relationship between problem structure and the circuit depth for a variety of combinatorial optimization problems including MaxCut and MaxIndSet. Specifically, we show how to derive a graph, G, that describes a general combinatorial optimization problem and show that the depth of circuit is at least the chromatic index of G. By looking at the scaling of circuit depth, we argue that MaxCut, MaxIndSet, and some instances of vertex covering and Boolean satisfiability problems are suitable for QAOA approaches while knapsack and traveling salesperson problems are not.
Year
DOI
Venue
2021
10.1007/s11128-021-03001-7
QUANTUM INFORMATION PROCESSING
Keywords
DocType
Volume
Quantum approximate optimization algorithm, Circuit depth, Combinatorial optimization, Chromatic index
Journal
20
Issue
ISSN
Citations 
2
1570-0755
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Herrman Rebekah101.35
James Ostrowski202.37
Travis S. Humble301.01
George Siopsis401.69