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, August 6, 2010
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.
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.
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.
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.
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.
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.
Subscribe to:
Posts (Atom)
