Error Mitigation Thresholds in Random Circuits

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 without overhead in the spacetime volume of the circuit, but eventually incurs exponential overhead in sampling complexity. Such error mitigation techniques require accurate noise tomography and one might wonder if they are robust to imperfections in the learned noise model. We show that noisy random quantum circuit models with imperfectly characterized noise can exhibit a disorder-driven error mitigation threshold at a finite rate of disorder. 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 random circuits, as well as numerical simulations of error mitigated random quantum circuits. We discuss the implications for quantum algorithms in near-term devices.