The Shor Circuit

Modular exponentiation

The first step to implementing Shor’s Algorithm would be to create a quantum circuit to calculate Modular Exponentiation. Let’s recall our function $f(a)=X^{a}\space (mod\space N)$.

As, quantum operations are reversible, we will implement $f(a)$ as a quantum oracle with $|a\rangle$ and an ancilla register $|b\rangle$ as input, defined as follows:

$$U_f|a\rangle|b\rangle = |a\rangle|b \oplus f(a)\rangle$$

We need to operate $X^{a}\space (mod\space N)$ on a random value $X$ that we have picked, using quantum gates.

The number $a$ can be represented in the binary form as $2^{n-1}a_1 + 2^{n-2}a_2 + ... +2^0a_n$. We can use this binary representation to understand how we can apply a gate to each input qubit in our register making up $|a\rangle$.

$$f(a)=X^{a}\space (mod\space N)$$

$$f(a)=X^{2^{n-1}a_1 + 2^{n-2}a_2 + ... +2^0a_n}\space (mod\space N)$$

$$f(a)=X^{2^{n-1}{a}_1}+X^{2^{n-2}{a}_2}+\mathrm{.}\mathrm{.}\mathrm{.}+X^{2^0{a}_n}(modN)$$ ...