The multi-angle quantum approximate optimization algorithm

The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems. In this presentation, we investigate a multi-angle ansatz for QAOA (ma-QAOA) that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by QAOA, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. It also yields a higher approximation ratio than QAOA at the same depth on a collection of larger MaxCut instances. Many of the optimized parameters are zero, so their associated gates can be removed from the circuit implementation, further decreasing the circuit depth. These results indicate that ma-QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.