In the article article there is an optimized circuit for Shor's algorithm:

enter image description here

and I'm not sure if $x=11$ is the random number $1<x<N$ I can choose to calculate $f(r)= x^r\bmod N$ for $r=1,2,3,4\ldots$ which will lead to the period $r$.

Namely, as far as I understand this circuit and the further description which can be found on page 31, $x$ is the random number that I can choose. The resulting outcome of the given circuit after running it on the IBM Quantum Composer is $00100$ or $4$ denoted with $p$. Further, in the article, it is said that $M/p= 8/4 =2$ where $M$ is $2^n$, $n$ being the number of qubits in the control register giving $r=2$.

Inserting $r=0,1,2,3,4,...$ in $x^{r} \bmod 15$ I obtain $1,11,1,11,1,\ldots$ resulting in a period of $2$.

Now, what confuses me is that I'm not sure if the result of the given circuit is the period (4) and I got the meaning of $x$ wrong, if $r=2$ is the period and the result obtained $(4)$ isn't, or if both $p=4$ and $r=2$ are periods of the function, but we have to make sure if there is a smaller one than the obtained one and that's the reason why we divide by $2$.

The last paragraph can be summarized as the question: What is the meaning of the obtained result of the given circuit?


1 Answer 1


The circuit does not return the period itself but a value $y = M/r$. It holds that $M=2^n$, where $n$ is number of qubits used for representation of $y$. In your particular case $n=3$, hence $M=8$. The returned value of $y$ is 4 (note that also 0 has high probability but this results is deemed "trivial" and it is neglected). Easily $r = M/y = 8/4 = 2$ which is the period.

After that you can calculate factors $p,q = \gcd\{a^{r/2}\pm1;N\} = \gcd\{11\pm1;15\}$, i.e. $p =\gcd\{12;15\}=3$ and $q =\gcd\{10;15\}=5$.

  • 1
    $\begingroup$ Thank you very much. $\endgroup$ Feb 17, 2022 at 10:29

Your Answer

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

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