Friday, August 6, 2010

QMul, QAdd, and QPow

My time this week has been spent working on Matt's project. In my last post, I mentioned how there was difficulty teaching the code to adhere to special quantum rules as the quantum objects get swallowed up inside Mul, Add and Pow objects. In order to remedy this, I needed to create a new set of binary operation classes that adhere to these rules with the same op-priority as other quantum objects.

To do this, I put logic inside the binary-ops' __new__ method which called a set of logic rules. These rules return an instance of the correct object if an object should be created or raise an error if the input expression is nonesense. For this to work, binary-op objects must know to what quantum type they evaluate (e.g. to what Hilbert space they belong as well as whether they act as a Ket, Bra, or Operator when evaluated). Thus, I used __slots__ to contain 'hilbert_space' and 'evaluates' attributes; these attributes are set during initialization in the 'rules' class methods. To make this simpler, all Quantum Objects inherit from a QuantumBasic class which contains the op_priority information, __slots__ for 'hilbert_space' and 'evaluates', as well as the __mul__, __add__, __pow__ methods which call the __new__ method of our new binary operations.

I mostly have this logic working such that it can flatten non-commutatively for QMul and commutatively for QAdd. However, I still need to get the .expand() method up and working. That said, there is still much testing that needs to be done before I can get this integrated with my code, which makes me worried as the GSoC pencil down date fast approaches.

Friday, July 30, 2010

Integration of General Quantum

This week, I started to integrate Matt Curry's general quantum stuff into my code; this was done both to prevent replication of code in our two modules and to test to see if his code worked in a practical problem.

That said, I spent quite a bit of time this week inside Matt's code. Dr. Granger and I ported my represent function into Matt's code so that we could represent not just Qbit systems, but also other systems by specifying a BasisSet and how to represent an individual State or Operator in the Basis. Matt and I worked together on developing validate functions that use the new op.priority feature to check to see if Quantum expressions are valid; testing this is still ongoing and has serious limitations because Sympy's AssocOp classes cannot know the special rules that go along with its args. This leads to issues that are hard such as how to call our validate functions automatically when all quantum objects are held within a Sympy binary-operation (e.g. Mul(Operator, |Ket>) + Mul(Operator, |Ket>).

While helping Matt get his code up and working, I was also busy inheriting and porting features from Matt's code. This was a pain as little changes caused large errors throughout my code; I especially had a hard time dealing with the ket attribute inside State since Sympy keeps all attributes inside an args list rather than an ensemble of separate attributes with their own names. This ultimately meant that I had to rewrite how I parsed the args for Qbit, making args[0] be a tuple which contained the real attributes and args[1] be information about it being a ket.

As I continue to play with Matt's code, I get a better idea of the serious design problems he is running into. These issues have apparently been run into before with Matrices (The issues with Matrices are very similar in that they have special rules for what can be multiplied and need to maintain these rules even when held inside a Mul object). The Matrix class got around this by standing alone, not inheriting from Expr, and rewriting its own __mul__ method; this meant that, since Expr's don't know how to multiply by Matricies, Python would default to the Matrix's __(r)mul__ method. This is quite kludge-y, I should hope we come up with a better solution than this. The addition of op-priority is a good start to the fix, but will only fully work if the Mul object itself knows how to use this feature.

I need to clean up both my and Matt's code in the following weeks as I would like to have a good product by the end of GSoC.

Friday, July 23, 2010

QALU and Measurement Gates

As I said in the last blog post, measurement has been implemented as a one-shot irreversible function in my code; I made it a function because measurement should not distribute to each orthogonal state inside the quantum state of the system. This could not easily be implemented in Sympy as every object (including my gates) is assumed to be distributive. This leads to some generality problems as one cannot construct a general circuit object with a mix of measurement gates and Unitary Gates. I did a one-shot measurement rather than an ensemble measurement as the one-shot measurement was needed immediately for my implementation of Shor's algorithm.

This week, I fixed these problems. In order to ensure measurement did not distribute, I had to subclass Gate into a NonDistributiveGate class which would be given special logic inside my apply method. This required me to carefully review apply and make sure that the .expand() method was used judiciously so that integer factors combined correctly while ensuring that gates did not distribute to the individual orthogonal states. This took much longer than I thought it would. I have also begun to implement a notion of ensemble measurement which will return a tuple of measurement outcomes.

Another thing I have been putting off is the creation of a set of quantum logic which implements common arithmetic quantum mechanically; this logic would be key in doing a legitimate and realistic simulation of all processes needed to do Shor's or Grover's algorithms. Making this logic required a look through the literature on reversible logic and a review of my old notes from my assembly language class. Reversible logic requires some junk bits which store extra information; since I am simulating a quantum computer and not a purely classical reversible machine, I can cheat a little and use measurement to irreversibly destroy information which bring down the number of necessary junk bits and the logic needed to manage them. Thus, I was able to implement a quantum mechanical Add, Bitshift and Multiply. I still need to create logic which can take powers and preform the mod function. Also, I might want to consider optimizing the number of gates and junk bits needed for these operations as they require quite a few.

The addition of tests to my code has been going smoothly as well. If I want to merge this code by the end of GSoC, I will need to begin to base my code off Matt Curry's code and document-test my code like crazy. These will likely be my primary concern for the next few weeks.

Thursday, July 15, 2010

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.

Friday, July 9, 2010

Testing and More Testing

Last week, I wrote about how I was working to make my code create matrix representations of arbitrary gates. This week was a little bit slower and mostly involved writing tests to ensure that my code was really working.

There were a few minor changes that I ended up having to make so that everything would work for arbitrary 3-qbit gates. To check my sanity, I followed through an example in "Quantum Computation and Quantum Information" by Nielsen and Chuang and saw if my results matched theirs. This example had a set of single and 2-qbit gates that formed a quantum Fourier transform on a three qbit system, they also showed the matrix that would represent this transformation. Thus, this was a good way to make sure everything in my apply and represent functions was consistent with the text. After realizing that I was reading the circuit diagram upside down and backwards, I was able to confirm that my code produced the same results as the book. I repeated this for a few other select examples and came to a similar conclusion.

All in all, I am making good progress towards simulating a quantum computer.

Thursday, July 1, 2010

Multi-Qbit Gates and Gate Simplification

One of the greatest things about Sympy is its ability to maintain symbolic representations of items inside Mul, Pow, and Add classes. This makes symbolic manipulations possible before ever doing any calculations. This week, I started developing gate simplification code.

The first step in the gate simplification process is sorting the gates, which cannot be done using Mul's built in sorting functions as the commutativity rules for gates is not as simple as 'does' or 'does-not' commute. Gates commute with other gates that do not act on the same qbit; in addition, the ZGate, pi/8-Gate and phase gate always commute with themselves. I chose to use a bubble-sort to do the sorting as it was very easy to ensure a bubble-sort doesn't incorrectly exchange elements; it would be much harder to have a merge-sort or other NLogN algorithm do this.

Once the gates are sorted, keeping in mind special commutation relations, the code can then preform gate simplifications. The Hadamard, X, Z, and Y gates all produce Unity when squared. The pi/8-Gate produces the phase-Gate when squared, and the phase-Gate squared produces a Z-Gate. I have implemented these very simplistic rules.

Another thing I did this week was implement intrinsically multi-qbit gates. Before explaining how this works, I'll need to get some nomenclature out of the way. For multi-qbit gates, the first bits it acts on are called the control bits with the last bit representing the target bit. To start, I first generalized the apply method so that it could take in a square powered of 2 sized matrix and apply it to any given state. Thus:

In [8]: apply_gates(CNOTGate(0,1)*(x*Qbit(0,0) + y*Qbit(0,1) + z*Qbit(1,0) + w*Qbit(1,1)))
Out[8]: w⋅|01> + x⋅|00> + y⋅|11> + z⋅|10>
#This is as we would expect as it chose to flip the first bit contingent on the 0th bit being True

To prove to myself that the code was actually working, I created an arbitrary 4x4 matrix with symbols for each element that are in alphabetical order. I then applied the gate to Qbits with the control and target set to all 4 of their permutations and several 'junk' bits that should not change the result of the output. By hand, I figured out how the state should change. Here is one of the four inputs that I put in:

In [14]: apply_gates(Arb(2,0)*(Qbit(0,1,0)))
Out[15]: a⋅|010> + e⋅|011> + i⋅|110> + m⋅|111>


After doing this, I also checked the 8 possible unique inputs for an arbitrary 8x8 matrix.

The step of representing these gates as matrices acting in arbitrary Hilbert spaces was non-trivial as it is not generally possible to express the matrix as the tensor product of several unities with the matrix in the special 2 qbit case. Fortunately, this article had an example of how several different multi-qbit gates could be expressed in Dirac Notation starting at page 35. With the help of Dr. Gutierrez, I was able to determine a general method for expressing a multi-qbit gate acting on any number of qbit(s).

After coding this method in, I tested the code exhaustively by making an arbitrary 4x4 and 8x8 gate matrix and saw if my apply method (which I am fairly confident works) agrees with my matrix-represent method. After changing some small mix-up's with Endian-ness, I found that the two functions agreed as to the results of applying the gates.

I added many more tests to my code this week, but I clearly need more to make sure that everything actually works. Also, I still need to develop basis transformations for states and gates.

Friday, June 25, 2010

More On Operations

I added some more functionality to the code this week.

I gave the code the ability to build single qbit gates that work in multi-Qbit settings.
In order to do this, I had to take the matrix-representation of the gate operating on a single Qbit and take the tensor product of it with Unities; these Unities belong in the place of the qbits that are unaffected by the gate. Thus, a Hadamard Gate on the 1st bit in a 4-qbit setting is the tensor product (I x I x H x I), where I is a 2x2 unity matrix and H is the Hadamard Matrix.

For this to work, I would have to implement a Kronecker (Tensor) Product for matrices. The Kronecker Product function that I created does the Kronecker Product for an arbitrary number of input matrices of arbitrary size. I also produced test files that tested the Product against the Kronecker product that already exists in a Python library called Numpy. With this product working, I was able to make the single qbit gates act on any number of qbits.

Dr. Granger told me to implement an apply method which would be able to apply the gates to any number of qbits without doing a full matrix representation using Tensor Products. To do this, I used Qbit objects to represent a single state inside a ket with a probability amplitude multiplying. This works like this:

In [7]: circuit = HadamardGate(0)*XGate(1)*Qbit(0,0,0,0,0)

In [8]: print circuit
Out [8]: H(0)*X(1)*|00000>

In [9]: apply_gates(circuit)
Out[9]: 2**(1/2)/2*|00010> + 2**(1/2)/2*|00011>

This output is clearly much cleaner than the output given by the represent() function, which prints a long matrix. Having an output with states inside kets multiplied by their respective probability amplitude makes quite a bit more sense than a long column matrix. As such, I taught the code to take the matrix representation and turn it into this format using the matrix_to_qbits function.

The ability to switch the matrix representation into an expression in Dirac Notation allowed me to test to see if the apply and represent functions produced the same results. The testing stage of my code is far from complete so I need to continue debugging and creating tests in my test file. Also, I plan on creating a simpgate() function that will rearrange gates so gates that operate on the same qbit are grouped together (gates that operate on different Qbits commute; if they operate on the same qbit, they do not) and then make any obvious simplifications.

Friday, June 18, 2010

First Week of Coding

This week, I split my time between learning more about Quantum Computation and actual coding for my project.

So far, I have taught my code how to create a single Qbit of definite state and build the single Qbit gates that are to operate on it. I have built into the gate classes the ability to represent themselves in different bases (right now I have only implemented the |0> |1> and |+> |-> bases). To see how this all works, let me show an example of me creating an XGate operating on a single Qbit of definite state |1> and then representing it in the |0> |1> basis:

In [2]: circuit = XGate(0)*Qbit(1)

In [3]: circuit
Out[3]: X(0)⋅|1>

In [5]: represent(circuit, ZBasisSet())
[1.0]
[ 0]

This is exactly what we would expect as the XGate acts in the same way as a classical NOT gate would, switching the Qbit from the state |0> to the state |1>. We can of course make the number of gates we apply more complicated, with a Gate having an X, Hadamard and Z gate applied to it in that order:

In [7]: circuit = ZGate(0)*HadamardGate(0)*XGate(0)*Qbit(1)

In [8]: circuit
Out[8]: Z(0)⋅H(0)⋅X(0)⋅|1>

In [9]: represent(circuit, ZBasisSet())
[ 0.707106781186547]
[-0.707106781186547]

A quick matrix multiplication confirms that this is the expected result.

In the future, I will want to make the 'represent' function output in the standard |ket> notation. Also, I will need to implement a simplify function which will make any obvious simplifications to the gates. To generalize these gates so they can operate on multiple Qbits, the code will need to take the Kronecker Product of the 2x2 matrix with several unity matrices. Also, I will want to create tests to automatically test the code.

Much of this week I spent reading through relevant resources. I thoroughly read the first chapter of Mermin's book "Quantum Computer Science: An Introduction". This book introduces Quantum Computation by first discussing reversible classical gates (some not all that useful) and then generalizes these gates to quantum computation; the book goes through quite a few gate equivalences that I will want to teach the code to recognize.

I also started digging through a article describing the Solovay-Kitaev algorithm which allows an arbitrary single qbit operator to efficiently be approximated in terms of our set of universal gates; I will want to teach my code how to do this.

Friday, June 11, 2010

Plans

I just turned in my last take home final today and am ready to begin work on my GSoC project.

Over the summer, I plan to implement qubits and gates as objects, which will be contained within a Mul object that shows how and when to apply gate operations. Together, this Mul object will represent a quantum circuit operating on a set number of qubits; thus, a Mul object containing these gates will represent some quantum transformation, such as a Fourier Transform. In order to carry this out, each gate will have to keep track of which qubit(s) it will operate on.

The first step towards this general goal is the implementation of single qubit gates and the single qubit. This single qubit will need to be viewable in any observational basis. It is here that I will start my work.

I still have quite a few details to hammer out, but I look forward to starting this!

Friday, June 4, 2010

No Time for Title

This week is dead week at Poly, so I didn't get much time to work or think about my project.

Matt Curry (who has a GSoC project involving the creation of a general quantum mechanical framework in Sympy) and I did get an opportunity to discuss with Dr. Granger how our projects would fit together. Matt will design code that will keep track of the Hilbert space in which a quantum state lives. This may be of some use to my project as an n-qubit system lives in a Hilbert space which is the direct product of n l2(2) Hilbert spaces. His work will also allow states to be added, multiplied by scalers and negated--This will also be useful and will be a great addition to code that I do. I'm starting to gain respect for how object orientation makes code reuse easy.

Anyway, my last final is this Wednesday, so I should be able to start really working on my project soon!

Friday, May 28, 2010

Beginning of GSOC

The Google Summer of Code began this week; I will be blogging each week for its duration.

This week has been busy. The quantum mechanics class I have been taking has focused on exploring the uses of the bra and ket notation. We have used this notation to generalize changes from various observational bases in both finite and continuous cases. Of special importance to my project, we looked at the transformations of a two state system.

Under the advisement of Dr Granger, Matt Curry (a fellow GSoC student) and I have spent some time looking at the Sympy code while trying to mimic some of its functionality in our own code. This has helped us learn about some of the neat Python tricks Sympy has used to function. For example, Sympy uses Python operator methods (such as __mul__ or __add__) to convert mathematical expressions involving objects into complicated symbolic expression objects. This has led us to notice functions such as Simpify which convert Python number objects into specialized Sympy objects--This allows the rewriting of many methods within the class. Writing code that functions similar to Sympy's has helped me get a better understanding of how it all works.

Overall, I'm very excited to begin work on coding for the Sympy project.


Tuesday, April 27, 2010

Google Summer of Code

While the Summer of Free Love came to an end with the sixties, the Google Summer of Free Code is very much alive. For those of you that don't know, the Google Summer of Code is a program where students throughout the world are given a stipend in exchange for working on various Open Source Projects.

A couple of weeks ago I submitted an application for the Google Summer of Code to Portland State University; I proposed a symbolic library for simulating quantum computation on a classical computer using Sympy. Sympy is a powerful Python library that can be used to manipulate mathematical expressions symbolically.

This monday, my application was accepted. I will be working throughout the summer with my mentor Dr. Brian Granger.

I am looking forward to this wonderful opportunity!

Thursday, April 8, 2010

In The Beginning

In the future, I plan to blog about my intrests in Physics, Mathematics and Computer Science.

Wish me luck!