Introduction to Quantum Computation

I thought I might try a different topic that tends to blend math, computer science, and physics. We probably won’t be doing any physics here, but the math and computer science are going to matter a little. There’s the approach that most computer scientists take: know what you have, and use it. For instance, we don’t question how our computer is built. We know we have certain operations that we can do down on the bit level that can be built with certain types of gates (like AND, OR, NOT, NAND, XOR, etc). This is about where we stop. We don’t go into details about how we go about building and implementing these things with wires and how the bits could be represented using voltage/amperage. Well, we can do the same thing with a quantum computer. We can ask what operations do we have and then go about making up quantum algorithms without worrying about the super precise details of how exactly this computer will be built.

NOTATION:

A quantum bit (or qubit) is a 1 or a 0 just like a bit in a computer (except much better). We will denote these single qubits as and . This is the dirac notation. Okay so more is going on here than I let on. You can think of the bits as spanning a 2-dimensional vector space and and are an orthonormal basis. The reason we need this is because actually a qubit can be more than just a single bit, it can be a superposition of bits. In general our qubit is a wave and it is , where and . So we can (and will) compute on this wave to give us the added power of working with both bits at once. Eventually we will want an answer and will need to measure the wave. Measuring will force the wave to collapse down to a single bit or , and it will be with probability and with probability . Thus we can think of as giving us a discrete probability distribution (this will become a much more useful statement when we work with more than just 2 bits).

Anyway, so we come to our computation point. We know our bits, but what can we do with them? In physics, the interpretation is that any quantum compuation must be a reversable process. In mathematics, what we do to must keep it as a probability distribution. Our computations will be linear functions on the vector space with basis . But there are more restrictions the reversability/keeping psi as a probability distribution forces the operators to be unitary. In other words, if we write , then our computations (or operators) are exactly the matrices such that (t is transpose and * is the complex conjugation). But you already knew that if you knew the definition of unitary. A computation can then be written as . This completely specifies how to do quantum computations on a single bit. Next time we will probably do an example (like NOT) and talk about extending to multiple bits.

Implicit Rules of Society

It’s kind of weird how many rules are implicitly followed in society. One is that green light means go at an intersection and red light means stop. Really, you must follow the red light rule for your own personal well-being, but what if you just didn’t go on green light? You don’t injure yourself, but you are holding up other people who would like to get by you. This happened to me today. I was the second person in line at an intersection and waited through 4 green lights because the person refused to go for some reason. The lanes were single and too narrow to go around. We were absolutely stuck. It was kind of annoying since I had a massive headache and people were beeping and I just wanted to get home, but reflecting on it is kind of interesting and funny. Somethings are hard to figure out whether we don’t do them out of courtesy or because it’s against the law. We don’t go punching people in the throat because that’s assault. But waiting through a green light? It’s not reckless driving. It’s too cautious if anything. But why don’t we go into a church and scream blasphemy? That isn’t attacking anyone, but it’s rude? I don’t know. It seems weird to me. Maybe some of the traditional implicit rules need to be broken.

Finite Fields (Final) Part 3

So now we come to how to implement this on a computer. If I’ve done my job in the previous two posts, then it should be obvious but I probably didn’t. You might just say that you could precompute those tables and then do a lookup whenever you do an operation, but that’s impossible! At some point you won’t have space for the table anymore; plus reading from disk is slow. We want to use the two fastest operations on a computer: xor/bit shifting (I didn’t use the word ‘and’ deliberately to try to be less confusing). Okay, so you are probably familiar with encoding polynomials as bit strings if you took linear algebra. Just place the coefficient in the appropriate spot of the vector. For example . Using this we can now define our operations on bit strings (what the computer has to work with anyway). In , we can do all this naturally. It will be left as an exercise to ponder how to do it with different primes.

Addition is clearly xor which is equivalent to addition mod 2 bitwise. Take the two polynomials in the example in the previous post: . Much less work and much less computation and much faster on a computer than what we did before.

Let’s take a peak at our last table for multiplication. Letting the cat out of the bag right now, multiplying any polynomial by x is the same as right shifting one unit (with one caveat).

Power table for :

n   

0    

1    

2    

3    

4    

5    

6    

7    

8    

9    

10  

11  

12  

13  

14  

Okay, so the first 4 are clear from what I said previously. The thing that changes is when you shift a 1 off the right side (meaning that you have encountered an ). So after the shift that throws the 1 off the edge, you xor your with the result. For it was easy: . Now I haven’t done the analysis, but to me it looks like on average a multiplication in will take operations (THE FASTEST operations). Even if I’m wrong, this is pretty amazingly good considering where we started from and what these things look like when written all the way out not in bit form.

Finite Fields Part 2

In my previous post, perhaps I was being a little sloppy. I appologize, but I was just trying to do a quick refresher, not teacher a course. Also, before I get flamed for saying “that’s the whole story behind finite fields essentially”, maybe I should change that statement to “these are the big results you usually take away and remember 5 years after you’ve learned about them and haven’t used them since.” There is certainly a very rich structure and many more fascinating results about finite fields — some of which I will be using today. Today, I will talk about constructing a finite field of order , tomorrow, about implementing it. I think the best nonmasochistic field to try to construct will be GF(16) (finite fields are often called Galois fields, hence GF when you don’t want to latex it). So in our case, we have p = 2, n =4. So we must find where p(x) has degree 4 and is irreducible (in GF(2)). Well, is a nice candidate since it has no linear factors (x+1 is the only choice for linear), and hence no cubic factors. You can verify that it is irreducible by squaring the quadric irreducible (and see that it isn’t p(x)). Again, this was probably clear right off for anyone that got past the first post, so hang in there with me. Here we go:

Elements look like: . For addition, we have it easy since the degree of f(x) + g(x) can never increase, so we will get a field element that has already been reduced modulo . For example:

(we used the fact that in GF(2), 2 = 0).

For multiplication, we can capitalize on the fact that we know (by virtue of how cosets work). Thus whenever we see , we can replace it with (in GF(2)). So if we know what all the powers of x larger than 4 are, we can do usual polynomial multiplication then replace those with the reduction. Example first:

Gah, thats a lot of writing. I should pause to say that we typically let then do everything with alpha, but I didn’t want to add a layer of complexity for this explanation. So we can see that specifying the replacement for each power of x (or alpha) would tell us how to reduce modulo p(x), and we only need 15 entries (why? — think of |GF(16)*|).

Power table for :

n   

0    

1    

2    

3    

4    

5    

6    

7    

8    

9    

10  

11  

12  

13  

14  

15   (this was a check to see that indeed .

A couple of things to think about are that using a different p(x) would give a different table! But can you find an isomorphism between the two? I won’t do it, but the answer is yes. Also note that p(x) was primitive. In other words GF(16)* is a cyclic group generated by alpha. What would happen if it wasn’t? For example: is irreducible but not primitive. Try it out!

Finite Fields Part 1

Hey, so I really suck at posting consistently. Luckily I can be consistent with my experiment. I now have m2, m3, tritone. I actually have lost some ability, but that’s a good sign that I’m going to swing back soon and become even better (it’s a process called consolidation). On to today’s post. I’d like to do a quick review of finite fields because I came across something amazing. Doing operations in a finite field on a computer is much faster than your usual stuff (working in or , which we are more comfortable with as humans)! Let’s see why this was a counter intuitive result for me (perhaps it’s obvious to you). Here’s my naive way of doing in a C/C++ type of program (p prime, of course).

Addition: take , then (where most programming languages use x % y to mean “divide x by y, then return the remainder”). This is already horrible since division is the slowest (basic) operation on a computer.

Multipication: this is worse! Take , then . This is so much work: multiplication and division — oh my! Supposing p = 2, then we are really doing over kill on the work load since it is just asking whether the result of the multiplication is even or odd.

Okay, so it is worth noting that above by ‘+’ and ‘*’ I meant the usual addition and multiplication of numbers they teach you in grade school. Also, I may be beating a dead horse here by going even into this much detail, but you get the point now hopefully. Okay, so what we would like is a quicker way of implementing (which is slightly more general than above). So I’m going to go through some pain and complication to get at what the field looks like, but I won’t be proving existence or uniqueness (both of which are true when p is prime).

I’m going to assume so much background knowledge that it’s almost a moot point to do this, but it will introduce you to my notation for the next post (the actual point of this) and refresh your memory if you have seen it but haven’t worked with it in a while.

Theorem 1. Letbe a commutative ring. Letbe irreducible. Thenis a field, where is the ideal generated by p.

Proof. Take an undergrad algebra class. Well, seriously any abstract algebra book in the world has this proof, and it isn’t hard to just verify the field axioms on your own if you want to do it yourself.

Theorem 2. Let F be a finite field with prime characteristic (in other words ), let be irreducible. Then is a finite field of order (note: this isn’t the strongest statement that could be made, but it is enough for what we are doing).

Proof (sketch). Note that theoretically we’ve shown that exists and is unique for each p before now — we are now using this to construct a new larger field. Since F is a field, F[x] is a commutative ring. By Theorem 1, F[x]/(p(x)) is a field. But since the elements of F[x]/(p(x)) look like f(x) + (p(x)) with deg(f(x)) < deg(p(x)) = n [verify yourself], we can consider F[x]/(p(x)) to be an F-vector space with basis elements . If we count all the possible combinations of elements, it looks like where . Thus, by counting we can see that each coefficient has choices and there are n spots, resulting in elements.

Alright, that’s the whole story behind finite fields essentially — once you’ve shown that all finite fields of order are isomorphic and there are no other ones (i.e. none where ). Sure, these things are nontrivial, but you can look them up. I’m stating them to put all the cards on the table.

Intrinsic Meaning of the Arrow

I was thinking about arrows today after seeing them all over road signs and even on the road itself. The arrow is universal, no doubt about it. If I put –> on the page you know it means to your right. No matter which way you view it, the arrow indicates the correct direction despite the fact that the directions in words would be different. I can’t say “to your right” to the person standing on the other side of the screen from me. It would be their left. But where did this meaning come from? If we were to send off something into space and aliens were to retrieve it, would an arrow pointing to our planet on a map of the galaxy indicate to them where we lived? I doubt it. They may have no concept of an arrow, so the thing would just be a symbol with no clear meaning. It’s fascinating that something so intrinsic to us, so hardwired into us that it doesn’t require language could actually still be a construct like language. Something that requires an explanation to another species. Something that has meaning, but only once you know the way the meaning is encoded in the symbols. Perhaps the species has no limbs but it has language. It seems like part of the arrow could be an abstract representation of us pointing to something with our fingers. I’m going to keep my eyes open for some other things like this.

Moving On…

Alright, 90% on the nose! Except when my average reached 90%, I answered 10 more correctly in a row and it stayed there…so it wasn’t that close. For those keeping track (that’s not even me) I’m answering much faster now for 78 correct, 8 incorrect. It appears as if the 5th and 4th are the only things tripping me up still. Strange, the 4th is incredibly distinct…I know it when I hear it, but fool myself into thinking other things are it when they aren’t.

Experiment Day 2

Well, I’ve made dramatic improvements, but I think it has to do only with the fact that somewhere in the back of my head I’ve been this good before. Don’t attribute results due to 5 minutes of work (well, I guess 10 now). I have to admit 90% is hard to maintain. I only missed 11 out of 79 which gives 86%. Still, if you know them, you shouldn’t miss 11. So I guess I was correct in setting the bar this high. (Many learning experiments set the bar much lower than 90% correct.)

Real Life Experiment

Alright, now that I’m freed of the academic constraints of Institutional Review Boards and stuff that needs to approve experiments with human subjects, I’m free to conduct my own. Muahaha! No, seriously, I have a great experiment that’s going to make me put my money where my mouth is. I want to learn to identify the musical intervals again (I was okay at it in high school, but probably never as good as I should have been). Here’s the catch: I’m only spending 5 minutes a day on it. I’ve set my stopwatch to go off after 5 minutes, and already evaluated my base level identifying M2, M3, P4, P5, M6, M7, and Octave (reasonable place to start). The results were better than I expected, but that’s okay. I’ll probably get worse when I add more. So I managed 65 correct, 17 wrong for a total percentage of 79%. I plan to chop it off at 5 minutes everytime no matter what. This experiment is to prove what you can accomplish for 5 minutes a day (this is soooo minimal!!! — any normal person could spend much longer, but that’s not the point here). Think about it. Five minutes per day means you don’t change a single thing about anything in your life. Just when you would normally go to bed, stay up for 5 minutes and do this. It’s so simple. The catch is that you need to do it every single day. It builds up from repetition. Well, I shouldn’t be jumping the gun. That’s my hypothesis. I wish I had a “control” or another experimental group that did 40 minutes once per week and even something like 20 minutes twice per week. I guarantee the minimal time of 5 minutes per day will kill those other ones despite potentially doing more hours per week. Even 30 minutes twice a week which is twice as much time per week would probably fall flat compared to the 5 minutes a day. The moral should be to work at something every day even if it’s a super small amount rather than hitting it with all your effort on the weekend or whenever you have that large chunk of time free in a week.

The experiment: For 5 minutes a day, identify intervals played increasing melodically at my current level. If I reach 90% correct, I will add the next lowest interval (i.e. m2). We’ll see at the end of this how long it took to identify all the intervals with 90% accuracy, then I may extend to descending melodic and/or harmonic. Perhaps I’ll go to triads and such after that, who knows. I will use the musictheory.net trainer: http://www.musictheory.net/trainers/html/id90_en.html . I probably won’t be posting updates every day, but we’ll see.

What’s Goin’ On?

This is my third attempt at a blog. I plan on making it much less focused than my last two. I think I just overblogged myself into not feeling like writing any more on the same subject matter (despite still finding it extraordinarily interesting). I plan on writing about my new life in Maryland. Things I come across what I find interesting. Topics that are sure to be covered: math, writing, running, taekwondo, (any sort of exercise I suppose), food, environment, politics, philosophy, language, and computer science. I’m sure that’s way too short, but it gives you an idea. By the way, don’t mind the layout/categorization/links/tags. We’re still constructing this beast, and I’m sure it will get better whenever the guy I hired to build this place gets back from his lunch break. (What’s the difference between tags and categories?)