Take the 2-minute tour ×

I'm having a little trouble understanding Shor's algorithm - namely, why do we throw away the result f(x) that we get after applying the F gate? Isn't that the answer we need?

My notation: $\newcommand{\ket}[1]{\left|#1\right>}$

$F(\ket x \otimes \ket0) = \ket x \otimes \ket{f(x)}$ ,

$f(x) = a^x \mod r$

share|improve this question

1 Answer 1

up vote 1 down vote accepted

$f(x)$ is easy to compute for a given $x$, even classically, and we are not really interested in its value. What we are interested in in Shor's algorithm is the period of $f$, i.e. the smallest $p$ such that $f(x+p)=f(x)$ for all $x$.

The way Shor's algorithm work is to prepare the superposition $\sum_x\ket x\otimes\ket0$ and apply the function $F$. The result is $$\sum_x\ket x\otimes\ket{f(x)} = \sum_{l<r}\left(\sum_k\ket{x_l+k p}\right)\otimes\ket l,$$ where $x_l$ is the smallest $x$ such that $f(x_l)=l$. Measuring the second register ($f(x)$) would give $l$, which is random and does not give much information. The key trick of Shor's algorithm i that it projects the $x$ register onto the state $\sum_k\ket{x_l+k p}$, the period of which ($p$) can be found by Quantum Fourier Transform. This period allows then to deduce the factors of $r$.

share|improve this answer

Your Answer


