  In this perspective, we discuss conditions under which it would be possible
for a modest fault-tolerant quantum computer to realize a runtime advantage by
executing a quantum algorithm with only a small polynomial speedup over the
best classical alternative. The challenge is that the computation must finish
within a reasonable amount of time while being difficult enough that the small
quantum scaling advantage would compensate for the large constant factor
overheads associated with error-correction. We compute several examples of such
runtimes using state-of-the-art surface code constructions under a variety of
assumptions. We conclude that quadratic speedups will not enable quantum
advantage on early generations of such fault-tolerant devices unless there is a
significant improvement in how we would realize quantum error-correction. While
this conclusion persists even if we were to increase the rate of logical gates
in the surface code by more than an order of magnitude, we also repeat this
analysis for speedups by other polynomial degrees and find that quartic
speedups look significantly more practical.
