2020/08/04 by James Ostrowski, Ostrowski, James, Rebekah Herrman +5
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Machine Learning and Algorithms #Optimization and Control (math.OC) #Optimization and Search Problems #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2008.01820
openalex publication_date 2020/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The quantum approximate optimization algorithm (QAOA) is a method of\napproximately solving combinatorial optimization problems. While QAOA is\ndeveloped to solve a broad class of combinatorial optimization problems, it is\nnot clear which classes of problems are best suited for it. One factor in\ndemonstrating quantum advantage is the relationship between a problem instance\nand the circuit depth required to implement the QAOA method. As errors in NISQ\ndevices increases exponentially with circuit depth, identifying lower bounds on\ncircuit depth can provide insights into when quantum advantage could be\nfeasible. Here, we identify how the structure of problem instances can be used\nto identify lower bounds for circuit depth for each iteration of QAOA and\nexamine the relationship between problem structure and the circuit depth for a\nvariety of combinatorial optimization problems including MaxCut and MaxIndSet.\nSpecifically, we show how to derive a graph, G, that describes a general\ncombinatorial optimization problem and show that the depth of circuit is at\nleast the chromatic index of G. By looking at the scaling of circuit depth,\nwe argue that MaxCut, MaxIndSet, and some instances of Vertex Covering and\nBoolean satisifiability problems are suitable for QAOA approaches while\nKnapsack and Traveling Sales Person problems are not.\n