  Quantum approximate optimization algorithms are hybrid quantum-classical
variational algorithms designed to approximately solve combinatorial
optimization problems such as the MAX-CUT problem. In spite of its potential
for near-term quantum applications, it has been known that quantum approximate
optimization algorithms have limitations for certain instances to solve the
MAX-CUT problem, at any constant level $p$. Recently, the recursive quantum
approximate optimization algorithm, which is a non-local version of quantum
approximate optimization algorithm, has been proposed to overcome these
limitations. However, it has been shown by mostly numerical evidences that the
recursive quantum approximate optimization algorithm outperforms the original
quantum approximate optimization algorithm for specific instances. In this
paper, we analytically prove that the recursive quantum approximate
optimization algorithm is more competitive than the original one to solve the
MAX-CUT problem for complete graphs with respect to the approximation ratio.

Quantum Physics