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.

Wednesday, August 03, 2011

Rethinking Geometric Complexity Theory

Recently there has been a great deal of literature on category theory and computational complexity. On the other hand I am currently unsatisfied with geometric complexity theory and I think knot theory can be used to counteract this.  I believe it can be reformulated into a more topological version that could cut down on the amount of computations.

See http://arxiv.org/abs/0908.1936

Therefore we try to formulate a new antithesis to turnings thesis.

The power of a oracle in $ALL$ deciding the entropy of a given language.

strategies

 

Also, Lance Fortnow lamented that Geometric Complexity theory is too complicated and would take one month to study to do useful results. Therefore, most of this post will try to simplify the thesis so that it wouldn't take a month for you understand geometric complexity theory. In effect this is an attempt to rewrite geometric complexity theory to be much simpler but still you can use the same tools. The time horizons are unreasonable for someone to learn so can we make shortcuts? To that end I try to employ shortcuts and attempt to attack the class of all languages. But first you must learn my approach.

 

 

 

Therefore, I wish to ask the question "What do you think would be a good way to speed up Mulmuley's program?" Therefore someone must bite the bullet and create tools to counteract the complexity of his arguments. To try this I wish to use ideas from category theory 

 

I have a few ideas.

 

 - Use ideas from category theory to simplify arguments. (Monoidal categories) [1]

 

 - Reformulate the program to tackle problems in topological computation (much research on topological quantum computation and even classical one) and show correspondance to representation of groups to the TemperleyÐLieb algebra [1]

 

 - Show theories in quantum computation are equivalent

 

 - Mix and match the above techniques. [1] [2]

 

 

 

My attempt to mix and match the above techniques is as follows. I wish to change the perspective of complexity theory to a topological one. Classes, and algorithms become probabilistic state spaces. A running of an algorithm becomes a path inside of one or more probabilistic state space. Algorithms eventually are bound inside a probabilistic state space such as a class. The reason for this probabilistic state space is that I am using tools from algebraic geometry / cohomology to create an new tools to attack complexity theory.  

 

We attempt to respond to what is unreasonable in complexity theory and create an oracle that can answer questions about the reasonable and unreasonable. 

 

 

 

My idea to mix and match the above techniques is as follows. First I try to take the idea of an oracle in $ALL$ [3] and what useful thing that oracle could tell me. The oracle in $ALL$ could be used. I use an oracle in $ALL$ to ask the question what is the Kolmogorov complexity of each complexity class. Then I assign a probability space to each complexity class which I define as the total state space of that complexity class. Any problems in that class will be bounded within each complexity class.

 

Therefore a central thesis would be as follows. Given any complexity class an element of that complexity class will be bounded by resource complexity and it will only exist within that probabilistic state space of that complexity class. To formulate this in the words of geometric complexity theory this would be a flip 

To formulate it in a new concept we take the idea of a flip and abstract it into three operations. There are flips from every infeasable and feasible complexity class. 

 

**Refrences**

 

 

 

[1] http://math.ucr.edu/home/baez/rosetta.pdf

 

 

 

[2] http://people.cs.uchicago.edu/~fortnow/papers/history.pdf

 

 

 

[3] http://qwiki.stanford.edu/index.php/Complexity_Zoo:A#all

Posted via email from The blog of a salty schemer.

Monday, July 18, 2011

Roadmap on what to do next

---------- Forwarded message ----------
From: "Cezary Bartosiak" <cezary.bartosiak@gmail.com>
Date: Jul 18, 2011 11:54 AM
Subject: Re: Roadmap on what to do next
To: "Joshua Herman" <zitterbewegung@gmail.com>
Cc: "Tanya Berger-Wolf" <tanyabw@uic.edu>

Hi,

These things should be done before you can rewrite:

* change DynamicStatistics interface to extend Statistics and remove DynamicStatisticsImpl
* Dynamic Statistics should also take a generic Interval

And these things can be done at the same time you rewrite:

* better Utility package for manipulating intervals:
- add
- remove (only the exact interval given)
- removeAll (all intervals in the window)
- union
- intersection
- difference
* remove unused variables, for instance low and high in DynamicModelImpl
* provide 3 types of snapshots:
- normal: enough when any of considered node/edge intervals overlap with a given time interval
- weak: enough when every of considered node/edge intervals overlap with a given time interval
- normal: enough when every of considered node/edge intervals is included in a given time interval

These two things, that should be done firstly, are very easy but I still have no time to do it :/ As you can see I develop several branches and this one has got lower priority to me. I would appreciate your help ;] Additionally I'm going to Scotland on Friday and come back on August 2nd.

If you have got questions related to these things don't hesitate to ask. I'll describe the idea related to generic interval soon.

On 16 July 2011 19:12, Cezary Bartosiak <cezary.bartosiak@gmail.com> wrote:
Hi,

I'm currently unable to use my PC - I contact you on Monday. I hope it won't be a big inconvenience.

Cheers,
Cezary

On 15 July 2011 22:47, Joshua Herman <zitterbewegung@gmail.com> wrote:
I was wondering where you want to take the dynamic statistics api.
Like whats on the roadmap and what I should refactor since I will be
rewriting it to support sliding windows? Thank you for your time.


Posted via email from The blog of a salty schemer.

Tuesday, March 09, 2010

Haven: An open source cloud engine.

This project Idea is more like a combination of plan9 and RenrakuOS with elements from singularity
but done correctly and much more open development.

I plan on having all running code as managed code all in a virtual machine. The
virtual machine will boot up across a group of diskless / nondiskless
nodes. There will be no file system but more like central database
that all nodes can access and write to. I plan on having a nanokernel
on the diskless nodes that will load four services 

All of the services run on a nanokernel.

Services on the system

  • the virtual machine (customized llvm or jvm)
  • synchronization of program (rsync with some authentication)
  • networking stack daemon (oskit derived)
  • database client to send and receive data (key value / SQL store) 

Process Design

Here is a diagram of how a individual virtual process will work in the system. 

Hosted by imgur.com

To put it in words a process is launched by the head node at start. It will perform a program read and a database read and distribute it to the nodes. The nodes will perform the task and then write their output to the database and then the program will terminate. The programs can access an internal network that is set up by the central server. The only services that will run on the nodes are the VM, the synchronization process and networking and database clients and the program to be performed.

 

The way you will push data is to use a dcvs or cvs and push code to the head server to be compiled.

The head node will have the management software that will have the main database that all of the nodes read and write
to. I don't plan on having a filesystem of any kind

I have a source code repository with some code that I plan on making an alpha release sometime next year. It is at https://launchpad.net/chicago-01

Posted via email from The blog of a salty schemer.

Thursday, March 04, 2010

Chicago-01 Project

This project Idea is similar to http://github.com/daeken/RenrakuOS
but with a more network aware setup.

I plan on having all managed code all in a virtual machine. The
virtual machine will boot up across a group of diskless / nondiskless
nodes. There will be no file system but more like central database
that all nodes can access and write to. I plan on having a nanokernel
on the diskless nodes that will load three programs
the virtual machine
synchronization of programs daemon
networking stack daemon
database client to send and receive data


The head node will have the management software
it will have the main database that all of the nodes read and write
to. I don't plan on having a filesystem of any kind

I was wondering what other ideas / comments you would have about this.
---- LOOK ITS A SIGNATURE CLICK IF YOU DARE---
http://www.google.com/profiles/zitterbewegung

Posted via email from saltyschemer's posterous

Sunday, February 21, 2010

Graph field automata (WORK IN PROGRESS)

Graph Automata have been the paradigm in the expression of utilizing
Graphs as a language. Matrix Graph grammars \cite{Pedro} are an
algebratization of graph rewriting systems. Here we present the dual
of this formalism which some extensions which we term Graph Field
Automata The advantage to this approach is a framework for expressing
machines that can use Matrix Graph Grammars.

http://arxiv.org/abs/0812.4009


---- LOOK ITS A SIGNATURE CLICK IF YOU DARE---
http://www.google.com/profiles/zitterbewegung

Posted via email from saltyschemer's posterous

Friday, February 05, 2010

Quantum computation and Knot theory

Lately I have been studying quantum computation and its interrelation with knot theory with Louis Kaufman . I have looked at software packages but there doesn't seem anything specifically for topological quantum computation. The main interrelation that I have been studing is the yang baxter equation and how that can be used as a braid operator. Specifically doing transformation on vector spaces which are unitary and reversibile you can basically allow for quantum computation. Interestingly enough these operations don't have to use the Quantum fourier transform to compute hard problems. The quantum Fourier transform usually allows you to solve special cases of the hidden subgroup problem. Instead the algorithms that you can express with knots can compute knot invariants which are still hard computational problems