Saturday, August 20, 2011

A simple introduction to topological quantum computation Part 1

Introduction and Big Pictures

Ever wonder about why knot theory is related to quantum theory? Ever wonder why your shoes tie the way they do but they still become undone? Ever wonder why you don't have a significant other? Well we will try to answer the first two questions but the third is beyond the scope of this post.  (The third is beyond the scope of the author at times....) Remember that computer science is based upon the idea of being effectively computable. That means that I can perform a set of steps (hereafter referred to an algorithm) in an reasonable amount of time. (The Church-Turing thesis). Quantum computers extend this and we will get into why they do in a little bit after preliminaries. The reason why you would want to study quantum computation is that certain algorithms have been proven to work much faster! We will get into how much faster and it really depends on the algorithm. The way that a quantum computer scales is much different than a classical one. The big picture of topological quantum computation is to do computation with topological states of matter. Now the question is what are those topological states. But first we need to know what topological states mean. Or even what topology is. Topology is similar to the study of geometry except for a few modifications. In geometry you study shapes. In topology you study things that are preserved under a continuous deformation. For example a topologist can't tell the difference between a coffee cup and a bagel! (pardon for the old joke).  

The reason is that they both have one hole or in other words they have the same genus.

Definition of a Knot

To first start off we must answer two questions. What are knots? The other is what are quantum computers? We can't answer both at the same time so lets start with the more visual question which is "What are knots? When people encounter knots they usually want to either undo the knot When you take out anything with a cord (such as headphones) and you didn't put the cord away correctly you encounter a knot. When you want to tie a boat to a pier to a boat you also have a knot(or even a knot to a pier but hey its up to isomorphism). A knot to a mathematician is a closed loop not an open one. What we think of knots  that we tie up with  are actually braids. There are many types of knots but the most common one is the unknot. The unknot is the same as a circle. Two examples of very common knots are below.   Exercises Can you unknot a closed loop with crossings? If you took your shoelace when it is knotted and melted both ends together to form a closed loop could you untie the shoelace?  (Try this in real life and see what happens)

Models of computation

Lets start on how quantum computers work. There are three models of computation that build upon each other. The deterministic model, the probabilistic model and finally the quantum model. The deterministic model can be understood through an elevator. Imagine there are a set of elevators. The elements of the elevators have buttons on each floor. One way to look at this is to create a matrix which describes where each elevator can go and a column vector describing where the elevators are currently. Therefore the state of the elevators can be described as a column matrix and the transitions of each elevators can be described as a n by n matrix. An example of this is to the the matrix below

.

The state of the elevators can be described by the matrix below 

 

 

Exercises. Create your own elevator system and see how it behaves. Extend the deterministic elevator system into a probabilistic model that follows these rules and attempt to compute the state of the system. After that replace the probababilities with complex numbers and see what happens. That is it for now! Good luck! :-)

 

Citations

 An Introduction to Quantum Computing. Noson S. Yanofskyphysics.quant-ph.

Yang--Baxterizations, Universal Quantum Gates and Hamiltonians. Yong Zhang (ITP, CAS), Louis H. Kauffman (Illinois, Chicago), Mo-Lin Ge (Nankai).Quant. Inf. Proc. 4 (2005) 159-197. physics.quant-ph (physics.hep-th physics.math-ph).

Posted via email from The blog of a salty schemer.