Noise robustness of quantum approximate optimization against correlated errors.

The Quantum Approximate Optimization Algorithm (QAOA) has the potential of providing a quantum advantage in large-scale optimization problems, as well as in finding the ground state of spin glasses. This algorithm is especially suited for Noisy Intermediate Scale Quantum (NISQ) devices because of its expected noise resilience. In fully error-corrected quantum computers, error correlations are known to lead to increased overhead. The effect of noise correlations on NISQ algorithms such as QAOA, however, remained largely unknown. In this work, we study by numerical simulation the causes and effects of the noise correlations on the performance of QAOA. We find evidence that the approximation ratio obtained by QAOA improves polynomially as the strength of the correlations is increased. This shows that, as opposed to fully error-corrected quantum computers, noise correlations can improve the performance of NISQ algorithms such as QAOA. This opens the way towards tailoring NISQ algorithms to leverage noise correlations, thereby boosting their noise resilience.