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