  Demonstrating quantum supremacy, a complexity-guaranteed quantum advantage
against over the best classical algorithms by using less universal quantum
devices, is an important near-term milestone for quantum information
processing. Here we develop a threshold theorem for quantum supremacy with
noisy quantum circuits in the pre-threshold region, where quantum error
correction does not work directly. We show that, even in such a region, we can
virtually simulate quantum error correction by postselection. This allows us to
show that the output sampled from the noisy quantum circuits (without
postselection) cannot be simulated efficiently by classical computers based on
a stable complexity theoretical conjecture, i.e., non-collapse of the
polynomial hierarchy. By applying this to fault-tolerant quantum computation
with the surface codes, we obtain the threshold value $2.84\%$ for quantum
supremacy, which is much higher than the standard threshold $0.75\%$ for
universal fault-tolerant quantum computation with the same circuit-level noise
model. Moreover, contrast to the standard noise threshold, the origin of
quantum supremacy in noisy quantum circuits is quite clear; the threshold is
determined purely by the threshold of magic state distillation, which is
essential to gain a quantum advantage.
