Noise is arguably the primary obstacle we must overcome to achieve the next generation of functional quantum processors. Many quantum breakthroughs have come from advancing our understanding of these uniquely quantum sources of errors, and how to protect against them – starting from the celebrated threshold theorem in the 1990s – which suggested that we might be able to run quantum computation in a way that is error-corrected, or robust to errors – to the recent experimental realization of so-called “logical” qubits. Heartening as it is to see these first steps towards fault-tolerant quantum computing, it may take a while before we develop the fine quantum control and fast processing speeds required to realize it in full.

Yet, it is reasonable to ask if we have to wait for fully fault-tolerant quantum devices to be realized before we can profit from their computing prowess. One suite of techniques to deal with noise, intended to be accessible even on today’s processors, goes by the name of “quantum error mitigation”. The idea is to delegate the effort of recovering from noise to classical post-processing, a significantly cheaper resource today than the intermediate measurements and control or decoders required for quantum error correction. To be clear, error mitigation was not intended as a comprehensive solution for quantum noise; reflecting this, preliminary analyses of individual error mitigation techniques already exposed their steep resource requirements. But they did not rule out the possibility that scalability (in terms of the number of qubits) could be within reach, with a mere tweak to the technique. And, for a period of time, more error mitigation schemes were developed, with no clear understanding of how much further this could go.

Our work puts hard limits on the scalability of error mitigation. We unify a multitude of these schemes under one umbrella – and show that this pernicious sample complexity is inherent to the idea of error mitigation itself. The ansatz we then proceeded with takes a radical approach and sees error mitigation as a statistical inference problem: If some of the noise can be canceled, it must be possible to discriminate certain input states - and then relate the task to one of hypothesis testing. It then turns out that one can design reasonable circuits that are so mixing that this task becomes basically impossible, unless a number of samples is available that scales not only exponentially in the depth, but also the system size. This was an intricate step: We had to find circuits that are extremely mixing in a precise sense.

As a result, we show that to mitigate noise in a circuit, it must be run a number of times that scales exponentially with both the circuit’s depth and system size. This is prohibitively expensive, even for circuits whose depth scales as loglog of system size, a finger width more than constant depth.

As with all-no-go theorems, our findings should also be seen as an invitation: what features of our general framework, if lifted, would allow for error recovery schemes whose sample complexity scales as favorably as error correction? We also point out that our claim of exponential sample complexity for error mitigation only holds for worst-case circuits, with all-to-all connected architectures. In a way, long-ranged entanglement and quantum noise do not seem to go together well. Local gates, therefore, should offer better scalability. Quantum error correction also remains unaffected by our findings. Our work brings into focus the two paths ahead: tailor error mitigation schemes more closely to the circuits at hand, or switch to a different paradigm of error recovery altogether.