5
$\begingroup$

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?

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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 ? $\endgroup$
    – Arun
    May 8, 2021 at 12:21
  • $\begingroup$ 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. $\endgroup$
    – ryanhill1
    May 8, 2021 at 21:35
  • $\begingroup$ @Arun, let me know if that answers your question! $\endgroup$
    – ryanhill1
    May 10, 2021 at 23:03
  • $\begingroup$ yes it does, thanks! $\endgroup$
    – Arun
    May 13, 2021 at 12:22
  • $\begingroup$ 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. $\endgroup$ Apr 3 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.