A Caltech Library Service

For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances

Brandão, Fernando G. S. L. and Broughton, Michael and Farhi, Edward and Gutmann, Sam and Neven, Hartmut (2018) For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The Quantum Approximate Optimization Algorithm, QAOA, uses a shallow depth quantum circuit to produce a parameter dependent state. For a given combinatorial optimization problem instance, the quantum expectation of the associated cost function is the parameter dependent objective function of the QAOA. We demonstrate that if the parameters are fixed and the instance comes from a reasonable distribution then the objective function value is concentrated in the sense that typical instances have (nearly) the same value of the objective function. This applies not just for optimal parameters as the whole landscape is instance independent. We can prove this is true for low depth quantum circuits for instances of MaxCut on large 3-regular graphs. Our results generalize beyond this example. We support the arguments with numerical examples that show remarkable concentration. For higher depth circuits the numerics also show concentration and we argue for this using the Law of Large Numbers. We also observe by simulation that if we find parameters which result in good performance at say 10 bits these same parameters result in good performance at say 24 bits. These findings suggest ways to run the QAOA that reduce or eliminate the use of the outer loop optimization and may allow us to find good solutions with fewer calls to the quantum computer.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Additional Information:We thank the Google AI Quantum team for useful discussion. EF also thanks Soonwon Choi, Misha Lukin, Hannes Pichler, Sheng-Tao Wang and Leo Zhou for many good chats. We acknowledge Jeffrey Goldstone for help with the acknowledgements. The work of EF was partially supported from NSF grant CCF-1729369 and ARO contract W911NF-17-1-0433.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-17-1-0433
Record Number:CaltechAUTHORS:20190801-134537838
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97600
Deposited By: George Porter
Deposited On:01 Aug 2019 21:49
Last Modified:04 Jun 2020 10:14

Repository Staff Only: item control page