Exponential State Distributions in Quantum Approximate Optimization*

The quantum approximate optimization algorithm (QAOA) is a quantum algorithm for solving combinatorial optimization problems with near-term quantum computers.  However, little is known about structure in the states that are produced by QAOA.  Here, we analyze systematic structure in QAOA for optimized MaxCut instances on graph ensembles with 14-23 qubits and depth parameters p≤12. We decompose the total probability to measure any solution with a given cost into an average probability per basis state × the density of solutions.  The average probability per basis state scales exponentially with costs in the Maxcut objective, and we devise an empirical relation that accounts for the scaling.  Approximate QAOA states are then generated using the predicted scaling and the density of solutions.  These approximate states predict approximation ratios with median errors of <1% and worst-case error of <3%, relative to exact results, across the 7,200 instances we consider.  They also predict the probability for the optimal solution and cumulative distribution functions, but with larger errors. The simple patterns identified here are expected to lead to new investigations into QAOA behavior and performance.