  Google's recent quantum supremacy experiment heralded a transition point
where quantum computing performed a computational task, random circuit
sampling, that is beyond the practical reach of modern supercomputers. We
examine the constraints of the observed quantum runtime advantage in an
extrapolation to circuits with a larger number of qubits and gates. Due to the
exponential decrease of the experimental fidelity with the number of qubits and
gates, we demonstrate for current fidelities a theoretical classical runtime
advantage for circuits deeper than a few hundred gates, while quantum runtimes
for cross-entropy benchmarking limit the region of a quantum advantage to a few
hundred qubits. However, the quantum runtime advantage boundary in circuit
width and depth grows exponentially with respect to reduced error rates, and
our work highlights the importance of continued progress along this line.
Extrapolations of measured error rates suggest that the limiting circuit size
for which a computationally feasible quantum runtime advantage in cross-entropy
benchmarking can be achieved approximately coincides with expectations for
early implementations of the surface code and other quantum error correction
methods. Thus the boundaries of quantum supremacy via random circuit sampling
may fortuitously coincide with the advent of scalable, error corrected quantum
computing in the near term.
