  The quantum approximate optimization algorithm (QAOA) is an appealing
proposal to solve NP problems on noisy intermediate-scale quantum (NISQ)
hardware. Making NISQ implementations of the QAOA resilient to noise requires
short ansatz circuits with as few CNOT gates as possible. Here, we present
Dynamic-ADAPT-QAOA. Our algorithm significantly reduces the circuit depth and
the CNOT count of standard ADAPT-QAOA, a leading proposal for near-term
implementations of the QAOA. Throughout our algorithm, the decision to apply
CNOT-intensive operations is made dynamically, based on algorithmic benefits.
Using density-matrix simulations, we benchmark the noise resilience of
ADAPT-QAOA and Dynamic-ADAPT-QAOA. We compute the gate-error probability
$p_\text{gate}^\star$ below which these algorithms provide, on average, more
accurate solutions than the classical, polynomial-time approximation algorithm
by Goemans and Williamson. For small systems with $6-10$ qubits, we show that
$p_{\text{gate}}^\star>10^{-3}$ for Dynamic-ADAPT-QAOA. Compared to standard
ADAPT-QAOA, this constitutes an order-of-magnitude improvement in noise
resilience. This improvement should make Dynamic-ADAPT-QAOA viable for
implementations on superconducting NISQ hardware, even in the absence of error
mitigation.
