Modeling and mitigation of realistic readout noise with applications to Quantum Approximate Optimization Algorithm*

We introduce a correlated measurement noise model that can be efficiently described and characterized, and which admits noise-mitigation on the level of marginal probability distributions. Noise mitigation can be performed up to some error for which we give upper bounds. Characterization of the model is done efficiently using a generalization of Quantum Overlapping Tomography. We perform experiments on up to 15 qubits on IBM’s and Rigetti's quantum devices to test error-mitigation and conclude significant improvements. Furthermore, we study the effects of readout noise on the performance of the Quantum Approximate OptimizationAlgorithm (QAOA). We observe numerically that for numerous objective Hamiltonians, our noise-mitigation improves the quality of optimization in QAOA. Finally, we provide arguments why in the estimation of energy of local Hamiltonians that typically appear in QAOA, estimated variables (energies of local terms) can be expected to effectively behave as uncorrelated for a broad class of states. Those include states appearing in QAOA, Haar-random quantum states, and states generated by random shallow circuits.