MainIn recent years, numerous theoretical results have shown evidence that quantum computers have the potential to tackle a wide range of problems out of reach of classical techniques. The main examples include factoring large integers6, implicitly solving exponentially sized systems of linear equations7, optimizing intractable problems8, learning certain functions9 and simulating large quantum many-body systems10. However, accounting for considerations such as quantum error correction overheads...