# Shor's Algorithm: Why throw away the f(x)?

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$

-

## 1 Answer

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 20, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9458901286125183, "perplexity_flag": "head"}