5
$\begingroup$

I found many circuits for the Shor algorithm for N=15, but i don't understand how to read the result 3 or 5. Where can i find the result e.g. for this circuit I found it here

$\endgroup$

1 Answer 1

7
$\begingroup$

The circuit you reference has a control register that is only three qubits long, which is fine as an example, but insufficient if you are to guarantee being able to solve via continued fractions as Shor originally proposed in [Shor94] [Shor97]. If you seek to factor $N = 15$, and select $g = 7$ as the generator for your cyclic subgroup (which has order $r = 4$ in this case), you will observe a frequency $j \in \{0, 16, 32, 48\}$ when reading out the control register after applying the quantum Fourier transform (QFT). This assuming that you have a control register of length $m + \ell = 6$ qubits.

To illustrate with a slide from one of my lectures (with $m = \ell = 3$):

enter image description here

If you post-process $j$ by expanding $\frac{j}{2^{m+\ell}} = \frac{j}{2^6}$ in a continued fraction, you will find

  • $0$ when $j = 0$ (no solution),
  • $2$ (as yielded by the fraction $\frac{1}{2}$) when $j = 32$ (you found a divisor of $r$), and
  • $4$ (the correct order, as yielded by the fraction $\frac{1}{4}$ or $\frac{3}{4}$) when $j \in \{16, 48\}$.

Provided you found $r$, you can factor by computing $\text{gcd}(g^{r/2} \pm 1, N)$ as proposed by Shor.

(Here, $m$ is an upper bound on the bit length of $r$, where we have used the fact that $r < N/2$ (see e.g. [Gerjuoy05] for an early mention), and $\ell = m$. In practice, $\ell$ can be decreased below $m$, but this requires more elaborate post-processing (see e.g. [E24] for further details).)

If you wish to use the circuit you reference, apply the "Chance" display to the top three qubits at the end of the circuit where the QFT is applied. You will then observe $j \in \{0,2,4,6\}$, and expanding $\frac{j}{2^3}$ in a continued fraction will yield results equivalent to the above three cases, but with a different scaling factor. (This being said, it is not clear to me how the circuit you refence performs the arithmetic; it may not work in a cyclic subgroup of $\mathbb Z_{15}^*$. But here is another circuit that illustrates the above example.)

$\endgroup$

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.