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)=Xa (mod N)f(a)=X^{a}\space (mod\space N).

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

Ufab=abf(a)U_f|a\rangle|b\rangle = |a\rangle|b \oplus f(a)\rangle

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

The number aa can be represented in the binary form as 2n1a1+2n2a2+...+20an2^{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|a\rangle.

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

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

f(a)=X2n1a1+X2n2a2+...+X20an (mod 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)=X2n1a1(mod N)+X2n2a2(mod N)+...+X20an(mod 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 GG that can perform the calculation X2niai (mod N)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 bf(a)|b\rangle \oplus f(a). So as always, to implement the XOR operation, we need a controlled version of this GG gate. Let’s have a look at our quantum oracle now.

Get hands-on with 1200+ tech skills courses.