Weekday Update with Addison Cugini

So far this week I have been playing around with learning and implementing Quantum Algorithms. Since I have already created the framework to build a Quantum Fourier Transform (QFT), I decided to start work on implementing Shor's algorithm for prime factorization which uses the QFT to amplify certain select probabilities. This makes for a good demonstration that everything built up until now is working correctly.

Here's a quick overview of what the algorithm needs to factor a number. It starts by picking a random number, a, less than N and makes sure that it is co-prime to N using Euclid's (classical) Algorithm. A superposition of many states |0>...|k>...|2**n> is made using Hadamard Gates (where n is the number of qbits in a quantum register). It then does the controlled-mod operation (a**k % N) of this register and stores the result in a second register. The second register is measured, collapsing the state of the first register into only the values which result in a particular value for the second register (this is due to the first and second register being entangled by the controlled-mod operation). We can take the QFT of this to derive the order of a in modular N arithmetic. This can be used to derive prime factors of N.

As we can see, the algorithm requires me to add a few new things to my code. First, it requires a system of measurement. To start, I have made measurement a function that takes in a state and the qbit it wishes to measure. Eventually, I will make this a Gate object. In addition, a controlled-mod gate is needed to make the algorithm work; eventually, I will want to develop a way to build this out of elementary gates, but for now I have simply overwritten the apply method for a controlled mod gate that knows how to directly apply itself to a state.

For now, I am applying the Quantum Fourier Transform gate by gate, which makes it rather slow (5-qbit long numbers like 21 take way to much time and RAM). I plan on making this a gate in and of itself that knows how to apply itself using a FFT, but also knows how to decompose itself into the individual gates that make it up. That way, user can choose to apply gates in a way they see fit.

Here is an example of my code factoring 15:

In [14]: shor(15)
a= 11
N= 15
Hadamard Gates Applied
controlled Mod'd
measured 2
QFT'd
measured 1
|1000000000001011>
r= 2
Out[14]: (5, 3)
#comments such as "Hadamard Gates Applied" are so that one can keep track of where in the algorithm we are

All in all, this week is going quite well.