submited by

Style Pass

Quantum error mitigation has been proposed as a means to combat unwanted and unavoidable errors in near-term quantum computing without the heavy resource overheads required by fault-tolerant schemes. Recently, error mitigation has been successfully applied to reduce noise in near-term applications. In this work, however, we identify strong limitations to the degree to which quantum noise can be effectively ‘undone’ for larger system sizes. Our framework rigorously captures large classes of error-mitigation schemes in use today. By relating error mitigation to a statistical inference problem, we show that even at shallow circuit depths comparable to those of current experiments, a superpolynomial number of samples is needed in the worst case to estimate the expectation values of noiseless observables, the principal task of error mitigation. Notably, our construction implies that scrambling due to noise can kick in at exponentially smaller depths than previously thought. Noise also impacts other near-term applications by constraining kernel estimation in quantum machine learning, causing an earlier emergence of noise-induced barren plateaus in variational quantum algorithms and ruling out exponential quantum speed-ups in estimating expectation values in the presence of noise or preparing the ground state of a Hamiltonian.

Quantum computers promise to efficiently solve some computational tasks that are out of reach of classical supercomputers. As early as the 1980s1, it was suspected that quantum devices may have computational capabilities that go substantially beyond those of classical computers. Shor’s algorithm, presented in the mid-1990s, confirmed this suspicion by presenting an efficient quantum algorithm for factoring, for which no efficient classical algorithm is known2. Since then, quantum computing has been a hugely inspiring theoretical idea. However, it soon became clear that unwanted interactions with the environment and, hence, the concomitant decoherence are the major threats to realizing quantum computers as actual physical devices. Fortunately, early fears that decoherence could not be overcome in principle were proven wrong. The field of quantum error correction has presented ideas that show that one can still correct for arbitrary unknown errors3. This key insight triggered a development that led to the blueprint of what is called the fault-tolerant quantum computer4,5, a (so far still fictitious) device that allows for arbitrary local errors and can still maintain an arbitrarily long and complex quantum computation. That said, known schemes for fault tolerance have demanding and possibly prohibitive overheads5. For the quantum devices that have been realized in recent years, such prescriptions still seem out of scope.

Read more nature.com/a...