Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
It seems like it should be a function of N - O(log N), to minimise probability of getting a multiple of the period. However, Prof Preskill's lec notes mention:
Thus we solve Period Finding if the sampled values of k have no common factor, which is true with high probability after a constant number of trials. Hence the quantum query complexity of Period Finding is constant (even better than for Simon's problem).
What am I missing?
Given a periodic function $f(x+r) = f(x)$, the period-finding procedure of Shor's algorithm can find the period $r$ using ${O}(1)$ oracle calls and ${O}(poly(\log N))$ operations where a high probability of success is assured after repeating the procedure ${O}(\log \log r)$ times [1]. The number of times the procedure must be repeated is thus a small, constant number (of order ten or so). So, the quantum query complexity across all repetitions is ${O}(\log \log r)$ * ${O}(1)$, where ${O}(\log \log r)$ is constant time, so the result is still ${O}(1)$.
Given $N$, we find a smooth $Q$ with $N^2 \leq Q < 2N^2$, wich implies that $Q/r > N$. Next, we put our machine in the uniform superposition of states representing numbers $x \text{ (mod } Q)$, and compute $a^x \text{ (mod } N)$ with a single application of $U:(x,y)\mapsto (x,y\oplus f(x))$, leaving the machine in state
$$\frac{1}{Q^{1/2}} \sum_{x=0}^{Q-1}|x, a^x \text{ (mod } N)\rangle.$$
We then apply the inverse quantum Fourier transform to the first register, producing the state
$$\frac{1}{Q}\sum_{x=0}^{Q-1}\exp{(2\pi i xc/Q)}|c, a^x \text{ (mod } N)\rangle.$$
Finally, we compute the probability that our machine ends in a particular state $|c, a^k \text{ (mod } N)\rangle$, where we may assume $0 \leq k < r$. Summing over all possible ways to reach this state, we find that the probability is
$$\bigg| \frac{1}{Q} \sum_{b=0}^{\lfloor (Q-k-1)/r \rfloor} \exp{(2\pi i brc/Q)} \bigg|^2.$$
The above probability is a simple explicit function of the integer $c$, whose magnitude has maxima when $c$ is close to integral multiples of $Q/r$. If $rc \text{ (mod } Q) \leq r/2$, this quantity can be shown to be asymptotically bounded below by $4/(\pi^2r^2)$, and thus at least $1/3r^2$. The probability of seeing a given state $|c, a^k \text{ (mod } N)\rangle$ will thus be at least $1/3r^2$ if there is a $d$ such that
$$\bigg|\frac{c}{Q} - \frac{d}{r} \bigg| \leq \frac{1}{2Q}.$$
Since $r < N$, and since any two distinct fractions with denominators less than $N$ must differ by at least $1/N^2$, a unique value of $d/r$ can be efficiently extracted from the known value of $c/Q$ by an application of the theory of continued fractions [2, Chapter X]. If we have the fraction $d/r$ in lowest terms, and if $d$ happens to be relatively prime to $r$, this will give us $r$.
There are $\phi(r)$ possible values for $d$ relatively prime to $r$, where $\phi$ is Euler's $\phi$ function. There are also $r$ possible values for $a^k$, since $r$ is the order of $a$. Thus, there are $r\phi(r)$ states $|c, a^k \text{ (mod } N)\rangle$ which would enable us to obtain $r$. Since each of these states occurs with probability at least $1/3r^2$, we obtain $r$ with probability at least $\phi(r)/3r$. Using the theorom that $\phi(r)/r > k/\log \log r$ for some fixed $k$ [2, Theorom 328], this shows that we find $r$ at least $k/\log \log r$ fraction of the time. So, by repeating this procedure only ${O}(\log \log r)$ times, we are assured of a high probability of success [1].
When $N$ is the product of two primes, the period $r$ is not only less than $N$ but also less than $\frac{1}{2}N$. As a result, a more extended analysis shows that the probability of learning a divisor $r$ from the measured value of $c$ is bounded from below not just by $4/\pi^2 \simeq 0.4$, but by more than 0.9. Furthermore, by adding a small number of additional qubits to the input register, the probability of learning a divisor $r$ in a single run can be made quite close to 1 [3].
[1] P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, 1994.
[2] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford University Press, 1979.
[3] N. David Mermin, Quantum Computer Science: an Introduction. Cambridge University Press, 2016.
