Limitations of noisy quantum algorithms

Daniel Stilck França, ENS Lyon

The impressive progress in quantum hardware of the last years has raised the interest of the quantum computing community in harvesting the computational power of such devices. However, in the absence of error correction, these devices can only reliably implement very shallow circuits or comparatively deeper circuits at the expense of a nontrivial density of errors. In this talk I will discuss how to use entropic inequalities to obtain limitation bounds for standard noisy intermediate scale proposals with or without error-mitigation tools. For instance, I will prove that with local depolarizing noise with probability p, at depths O(1/p) it is exponentially unlikely that the outcome of a noisy quantum circuit outperforms efficient classical algorithms for combinatorial optimization problems like Max-Cut. In addition, I am going to discuss how current error-mitigation protocols face significant barriers to overcome these conclusions.