Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths

Understand

We generalize the Quantum Approximate Optimization Algorithm (QAOA) of Farhi et al.

• (2014) to allow for arbitrary separable initial states with corresponding mixers such that the starting state is the most excited state of the mixing Hamiltonian.
• We demonstrate this version of QAOA, which we call QAOA-warmest, by simulating Max-Cut on weighted graphs.
• We initialize the starting state as a warm-start using $2$ and $3$-dimensional approximations obtained using randomized projections of solutions to Max-Cut's semi-definite program, and define a warm-start dependent custom mixer.