Improving the Performance of Quantum Approximate Optimization Algorithm Through an Adaptive, Problem-Tailored Ansatz*

The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves combinatorial optimization problems. While there is evidence suggesting that the fixed form of the original QAOA ansatz is not optimal, there is no systematic approach for finding better ansatze. We address this problem by introducing a new method for creating wavefunction ansätze iteratively in a way that is tailored to the problem being solved and, if desired, to the quantum hardware it is being solved on. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the original QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters.