# What is the quantum query complexity of the period finding routine of Shor's algorithm?

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?

• "Query complexity" probably means number of oracle calls to calculate modular powers. Would you confirm it? Welcome to SE! May 7, 2021 at 10:30

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)$$.

### Derivation

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.

• I understand the oracle is used once, and there are O(𝑝𝑜𝑙𝑦(log𝑁)) operations required for the QFT in the circuit, as you've mentioned. But isn't there an there is another complexity involved - the measurement needs to be repeated some function of N times, to improve the probability of finding the correct period - what complexity is this called ?
– Arun
May 8, 2021 at 12:21
• Ah, I see. Yes, the measurement does need to be repeated some number of times, however, this number depends on $r$, not $N$, and so when considering query and time complexity, is considered constant. I revised my answer to include this, along with brisk a derivation. May 8, 2021 at 21:35
• @Arun, let me know if that answers your question! May 10, 2021 at 23:03
• yes it does, thanks!
– Arun
May 13, 2021 at 12:22
• It is not the case that $O(\log \log r)$ is constant time, since $r$ is expected to be of size roughly similar to $N$. If you want $O(1)$ query complexity, you need to use some other technique: See for instance "On Shor's Quantum Factor Finding Algorithm: Increasing the Probability of Success and Tradeoffs Involving the Fourier Transform Modulus" by E. Knill for an early proposal. Apr 3, 2023 at 20:16