Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

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


By posting your answer, you agree to the privacy policy and terms of service.

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