Abstract: Noise in quantum devices can be corrected with quantum error correction or it can be mitigated via classical post-processing. The latter can be done with negligible overhead in the space-time volume of the quantum circuit, but will generally incur exponential overhead in sampling complexity. We use statistical-mechanical arguments to discuss the limits of error mitigation in quantum circuits. We show that noisy random quantum circuit models with imperfectly characterized noise remain robust to imperfections at a finite rate of disorder, before exhibiting a disorder-driven error mitigation threshold. Based on Imry-Ma arguments, we conjecture that this transition is in the same universality class as the classical random field Ising model in D+1 dimension for D>1 spatial dimensions of the qubits. Our results are based on a replica analysis of statistical mechanics models for noisy random circuits, as well as numerical simulations of error mitigated noisy quantum circuits. We discuss the implications of our results for quantum algorithms and tests of quantum computational advantage in near-term devices.
Joint work with Pradeep Niroula and Sarang Gopalakrishnan.
Location: ATL 4402