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} + ... +X^{2^0a_n}\space (mod\space N)$$

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

Now that we have reduced our problem to each qubit, we will make an abstraction here for the sake of simplicity that we have a quantum gate $G$ that can perform the calculation $X^{2^{n-i}}a_i \space (mod \space N)$ using classical logic. This classical logic is, in fact, the slowest part of the algorithm. Various optimizations have been achieved, but they’re out of the scope of our course.

Let us focus on the quantum aspect of the algorithm. Recall that we need to do $|b\rangle \oplus f(a)$. So as always, to implement the XOR operation, we need a controlled version of this $G$ gate. Let’s have a look at our quantum oracle now.