# The Shor Circuit

We'll take a look at how we can implement Shor's Algorithm through a quantum circuit that is similar to QPE.

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

Get hands-on with 1200+ tech skills courses.