Let's look at quantum subroutine of Shor's algorithm: Hadamard gates create superposition of all (exponential number) values for input qubits. Then we perform a classical function on them, which is here: $f(a) = y^a \textrm{ mod } N$, where $N$ is the number we would like to factorize, $y<N$ ...