Parameter concentrations in quantum approximate optimization
V. Akshay, Daniil Rabinovich, Ernesto Campos, Jacob Biamonte
Abstract
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. In QAOA, a quantum circuit is trained---by repeatedly adjusting circuit parameters---to solve a problem instance. Several recent findings have reported parameter concentration effects in QAOA and their presence has become one of folklore: while empirically observed, the concentrations have not been defined and analytical approaches remain scarce, focusing on limiting system sizes while neglecting parameter scaling as system size increases. We found that optimal QAOA circuit parameters concentrate as an inverse polynomial in the problem size, providing an optimistic result for improving circuit training. Our results are analytically demonstrated for QAOA at $p=1,2$ (corresponding to 2 and 4 tunable parameters, respectively). The technique is also applicable for higher depths wherein the concentration effect is cross verified numerically. Parameter concentrations allow for training on a fraction $w<n$ of qubits to assert that these parameters are nearly optimal on $n$ qubits, thereby reducing training time.