Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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.