  The Quantum Approximate Optimization Algorithm (QAOA) was originally
developed to solve combinatorial optimization problems, but has become a
standard for assessing the performance of quantum computers. Fully descriptive
benchmarking techniques are often prohibitively expensive for large numbers of
qubits ($n \gtrsim 10$), so the QAOA often serves in practice as a
computational benchmark. The QAOA involves a classical optimization subroutine
that attempts to find optimal parameters for a quantum subroutine.
Unfortunately, many optimizers used for the QAOA require many shots ($N \gtrsim
1000$) per point in parameter space to get a reliable estimate of the energy
being minimized. However, some experimental quantum computing platforms such as
neutral atom quantum computers have slow repetition rates, placing unique
requirements on the classical optimization subroutine used in the QAOA in these
systems. In this paper we investigate the performance of two choices of
gradient-free classical optimizer for the QAOA - dual annealing and natural
evolution strategies - and demonstrate that optimization is possible even with
$N=1$ and $n=16$.
