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. Yanofsky. physics.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.

LeftParen

This seems to be an interesting new framework which uses some libraries from PLaneT.

According to the website

Features

Automatic creation of the basic directory structure of your project
A "Hello, World" with zero lines of code
Simple data persistance storage through the "record" abstraction
No databases or schemas
Session and cookie support
User accounts and authentication out-of-the-box
Easy form creation
Simple URL mappings (like Rails' routes)

Documentation is sort of lacking and I am currently figuring it out.
The website for the framework is at http://blog.leftparen.com/

Mashing up

Here is something that I did in yahoo pipes. It shows how that using a query from the user you can search multiple websites. It accomplishes this by sending a query to a few torrent search engines (mininova, isohunt, btjunkie, sumotorrent). This is accomplished by the URL builder module for each website. Then it fetches the RSS feed from all of those websites and puts them into a combined RSS feed (Fetch Feed Module) . The last two things that it does is it filters all of the unique RSS feeds and then sorts them by item.pubdate so that the latest torrents are found first in the pipe. 

Book of Poems Up On Lulu

My poetry book Dabru Emet is online at lulu. I used LaTeX to typeset the inside. Also, Emacs + AucTeX was my development environment It is available in digital and dead tree formats. From the text

The scheme
For when I found the holy lisp
So pure the curves that are parens
With a report merely one short text
Of beauty's simplicty

I knew that lisp was for me
But then there was a choice
Of thousand page lisp's
That is when I prayed for mercy

My goddess answered my call
With the flowers of recursion
And the lexical wildflower of scope
All around the syntax tree

I heard "Scheme shall show you the path
To beauty through simplicity
Not a thousand page tower of babel
But merely the essential fraction"

And I rejoiced and heeded her call
Found the purple tome of wizard's
The structure of the spells
And their interpretation

My eyes have been opened
To the spells of functions
And the beauty that lies
In the scheme that is

Blogged with Flock

Register To Vote for R6RS and R5.97RS.

Currently there is a vote for the ratification of R6RS. To vote you have to register with the draft committee. This involves giving your information and a short paragraph on your interest in R6RS. Also the final draft of R6RS is out.

Working Through SICP

Currently I am reading SICP. It is a great book as an introduction to computer science and programming with scheme. Right now I am about on the second chapter and have completed most of the exercises. It is really lots of fun doing the exercises and eventually getting the exercises done right. 

The Little Schemer Book Review

This book is an introduction to thinking about computation and consequently the scheme programming language. The only prerequisites needed for the book is arithmetic. It is written in a series of dialogues and has humor interspersed. Also it introduces the idea of recursion in lisp and this ends with the y combinator being fully introduced in scheme. The book introduces a subset of scheme with an atomic environment by creating the atom? function. The book ends with a full interpreter of the subset of scheme written in scheme.

I really enjoyed this book because it is very simple to understand. When I read this book I had little knowledge of programming and this book was a great introduction to scheme. I would recommend this book for a person who has no prior experience with programming or scheme in general.

R6RS preliminary report !

There is a preliminary report on R6RS.org in PDF format at R6RS PDF. It is a draft version and is currently incomplete but it reflects what the committee has decided so far. There is a public review process which allows you to suggest features or other changes available on the main page.

Multisets and structure

I am now trying to revise the structure of the wiki page and make it a much more formal document. Flow structure has been improved and I have added multisets / bags as a feature of the language. From the document itself.

These are lsets with the added feature of multiplicity. This means that an element in an multiset can occur more than once but when you bons (bag cons) the value to the set it increases the occurance of that element by one.


This was spurred on by a discussion from #scheme on irc.freenode.net with bpt. I give thanks to all of the people who have read the document and have offered constructive criticism.

Starting an implementation / new features

If you check the blog page I have added many new features and started to implement some of the features. So far I have implemented part of the set theory features. rel? and fun? predicates allow for the definition of finite functions. At this time the operations assume a finite set of values. Also I have started to specify the language in EBNF. For those who haven't been reading the blog the actual informal specification of the language is at Beyond lisp .

Beyond Lisp

I have started to rethink lisp from the bottom up for the past year. Lists are still important part of the language John McCarthy believes in attempting to rethink lisp's core into a new thing. I have been thinking about this idea for awhile and have recently had a deeper insight into not just processing lists. Instead we replace lists with a important abstraction in mathematics.

WARNING HEAVY UNICODE

LSEL

Instead of the LiSt Processing language we replace lists with a hybrid datatype called an lset. This is a set that is both a list and a set. It has the functionality of a set but the abilitys of the list. Here is an example.

Working with LSET's

(define X
 (generate
  ((in x R) (> x 0))))

(set? X) ;-> #t
(sar X) ;-> (1)
(sdr X) ;-> (2 3 4 ...)

Mu expressions (First Order Formal Logic Operators)

And , or, not are extended over first order logic but they can only be relevant to first order logic in mu expressions. These new operators can occur inside of a mu expression. A mu expression is similar to a lambda expression except instead of describing a function you describe a first order logic expression. For example.

Axiom of Extensionality

 
(mu (u X Y) (-> (== (∈ u X) (∈ u Y)) (= X Y))) 
 

Also we have a let-mu which allows you to compose multiple mu statements into a single statement.

 
(let-mu (xl xr) 
  (∀ (∈ xl  L)) 
  (∀ (∈ xr R)) 
  (¬ (≤ xl  xr))) 
 

would describe the surreal numbers in unicode.
Anyways that is what I have so far. Comments are appreciated!

A much more involved version of this document is currently being drafted on community scheme wiki. It is available at http://community.schemewiki.org/?beyond-lisp

Collatz Collector Program and M91 Program

I haven't posted in awhile so here is some from my code archive that I have written.
CollatzProblem and the
McCarthy91-Function.

(define (collatz n)
    (and (display n)) 
          (cond ((and (odd? n) (> n 1))
                 (collatz (+ 1 (* 3 n))))
                ((even? n) (collatz (/ n 2)))))

(define (optimized-collatz n)
  (begin (and (display n))
           (let (n (modulo 4 x))
 (define (f x)
    (cond
     ((= n 0) => (/ n 4)) 
     ((= n 1) => (* (/ 3 4) (+ 1 (g (- n 1))))) 
     ((= n 2) => (/ n 2)) 
     ((= n 3) => (* (/ 1 2) (+ 1 (* 3 n)))))))
(define (g x)
    (cond
     ((not (= n 0)) => n)
     ((= n 1) => (/ 1 4 (g (- n 1))))))))


(define (collatz-range n)
  (if (= n 0)
      (display "Finished")
      (and (display #\newline)
           (collatz n)
           (collatz-range (- n 1)))))
(define (m91 n)
   (begin (and (display n)) 
          (cond ((and (<= n 100) (> n 0))
                 (m91 (m91 (+ n 11))))
                ((and (> n 0) (- n 10))))))
(define (mc91 n)
  (display n)
  (cond ((< n 1) (display "Function only defined for positive values of n"))
        ((<= n 100) (mc91 (mc91 (+ n 11))))
        (else (- n 10))))

Current Surreal-numbers code

;;; -*- mode: scheme surreal-numbers -*-
;;;; Surreal Numbers Datatype

;;; This code is written by Joshua Herman and placed in the Public
;;; Domain.  All warranties are disclaimed.

;;; For more information about surreal numbers see
;;; http://en.wikipedia.org/wiki/Surreal_Numbers
;;; Note: some of the comments are in unicode
;;; Requires SRFI-9

;;;Some Helper functions

                                        ;(quote 0) is 0used for nullset

(define (nullset? x)
  (equal? x '(0)))

;;This tests if a given list has a specific element

(define (set? lat)
 (letrec
     ((S (cond
          ((null? lat) #t)
          ((member? (car lat) (cdr lat)) #f)
          (else (set? (cdr lat)))))
      (member? (cond
                ((null? lat) #f)
                (else (or (equal? (car lat) a)
                          (member? a (cdr lat)))))))))

                                        ;This takes a set and a function
                                        ;and a function which can
                                        ;compair two sets
(define (setcmp-f? test? lat1 lat2)
  (cond
   ((or (null? lat1)
        (null? lat2)) #t)
  ((or (not (null? (car lat1)))
      (not (null? (car lat1))))
        (test? (car lat1)
               (car lat2)))
    (else (set-cmp-f? test? (cdr lat1) (cdr lat2)))))
                                        ;This adds up all of the values
                                        ;in a given set (list of numbers)

(define (member>=? xl xr)
  (setcmp-f? >= xl xr))
                                        ;This compairs if each member of XL is
                                        ;greater than or equal to XR
(define (union set1 set2)
  (cond
   ((null? set1) set2)
   ((member? (car set1)
             set2)
    (union (cdr set1)
           set2)
    (else (cons (car set1)
                (union (cdr set1)
                       set2))))))
                                        ;This creates the union of two sets
(define first$ car)

(define (build s1 s2)
  (cons s1
        (cons s2 '())))

(define second$ (lambda (str) ((second str))))

(define str-maker
  (lambda (next n)
    (build n (lambda ()
               (str-maker next (next n))))))

(define frontier
  (lambda (str n)
    (cond
     ((zero? n) '())
     (else (cons (first$ str)
                 (frontier (second$ str)
                           (- n 1)))))))
;;;Surreal Number Code Starts Here 

                                        ;Surreal numbers are defined as follows.
                                        ;Given a Surreal Number X = (xl, xr)
                                        ;where XL and XR are sets.
                                        ;∀ xl ∈ L ∀ xr ∈ R : ¬(xl ≤ xr).
                                        ;For exlample {(0) |(0)} == 0 == { | } |#
                                       
(define-record-type :surreal-number
 (make-surreal l r)
  surreal-number?
  (l left-side)
  (r right-side))
                                        ;This defines the surreal number datatype
                                        ;as a record

(define (well-formed? surreal-number)
  (and
   (set? (l surreal-number))
   (set? (x surreal-number))
   (not (member=>? (l surreal-number)
                   (r surreal-number)))))
                                        ;Check for a well formed surreal number
                                      
(define (create-surreal-number l r)
  (if (well-formed? l r)
      (make-surreal l r)
      (display "Error in XL/XR Check Input")))
                                        ;This uses the well-formed as a
                                        ;sanity check and creates a surreal

(define zero (create-surreal-number '(0) '(0))) 
                                        ;Example (Zero)

(define (pretty-print-surreal surreal-number)
 (display "(") (display (l surreal-number))
 (display ",") (display (r surreal-number)) (display ")"))
(define (display x)
  (if (surreal? x)
      (pretty-print-surreal x)
      (display x)))

                                        ;Uses Knuth's method for displaying
                                        ;surreals
(define (surreal-dydactic-function a b)
  (/ a (expt 2 b)))
(define (Surreal+1 surreal-number)
  (make-surreal
   (surreal-dydactic-function (xl surreal-number)
                              (xr surreal-number))))

(define (+/-one? side)
  (and (nullset? (car side)) (nullset? (cadr side))))

(define (value surreal-number)
  (+ (addvec (xl surreal-number))
     (addvec (xr surreal-number))))
(define (add-surreal surreal-number1 surreal-number2)
  (make-surreal
   (union (xl surreal-number1)
          (xl surreal-number2))
   (union (xr surreal-number1)
          (xr surreal-number 2))))
;;;Finite enumeration is done by streams
(define surreal-number-set+
  (str-maker surreal+1 zero))
(define surreal-number-set-
  (str-maker surreal-1 zero))
(define surreal+1)
;;Stream Definitions

;;Example
;;(define int (str-maker add1 0))
;; (define (add1 n)
;;   (+ 1 n))
;; (define odd
;;   (str-maker (lambda (n)
;;                (+ 2 n)) -1))
;; (define Q
;;   (lambda (str n)
;;     (cond
;;      ((zero? (remainder (first$ str)  n))
;;      (Q (second$ str) n))
;;      (else (build
;;             (first$ str)
;;             (lambda ()
;;               (Q (second$ str) n)))))))
;; (define P
;;   (lambda (str)
;;     (build (first$ str)
;;            (lambda ()
;;              P (Q str (first$ str))))))

Reasoned Schemer Short overview

Fans of prolog and other logical programming languages will not be disappointed in this new book that just came. It deals with the extension of functional programming to include logic programming. It is presented in a dialogue manner that is easy to understand for beginners and advanced people. Reading the little or seasoned schemer books helps but is not required. All you need to know is functions can be passed as arguments to other functions and the syntax for let . The book is intended for beginners in logic programming and no prerequisites are needed. I highly recommend this book.

Siscweb

Lately I have been working on a website using siscweb. It is a really great framework that allows you to use scheme in a continuation web based framework. The resulting website can also be deployed in a J2EE application server which is different from other frameworks based in scheme which require their own server. For more information see SISCweb website

Zobrist Hashing

Okay, this is a new post in awhile. Currently I have read through the little schemer and done most of the exercises. I have also moved on and am currently reading the the seasoned schemer. I will put the Beyond Lisp idea on hold until I can get to the the reasoned schemer . Lately I have been programming parts of a Go AI. I am planning for this AI eventually to use (warning PDF) Termite so that it is able to distribute the AI across many systems as possibly a multi agent system.

Currently the part that I have programmed is a zobrist hashing program at zobirist hashing program As you can see it stores the Goban as a list. And requires SRFI's 27 and 60 .

Implementation of Beyond Lisp

Currently I am trying to implement the idea that I have which is outlined at Beyond-lisp-notes . Basically I will add the mu special form to the scheme language. This will take a formal logic expression and see if it holds true for a computer program. The syntax we will use is an automated theorm prover in first order logic. I am also thinking of adding mu-let which would take a set of mu statements and prove if they hold true given a set of data.

Requirements

The software package will require gandalf to be compiled on your unix machine. There is a windows binary that I will make available for windows computers. It will also require scsh because I am programing the program in that scheme environment. The Gandalf package is independant of implementation since it creates its own binaries.

Scsh
Gandalf

Informal proof of application of the theory of groups to computer programs.

First we take a binary operation we call our computer program. A binary operation in groups can be any abstract thing. This abstract thing is founded upon the idea of In this proof we use the binary operation as the evaluation of a computer program. Closure can be proven in the computer program by the simple fact that anything evaluated by the computer returns a value that is specified inside of the definition language. Here is an excerpt from my paper on the subject.

A informal definition of a Group which is a set of axioms that has closure, associativity , identity and inverse. Closure can be reasoned by given two functions the output is always something that the program could reason as an output which is provided by the language the program is programmed in. Associativity could be reasoned by taking the output of one program and then taking that output and evaluating that output into another function. Inverse can be reasoned with a program that returns the output given the input. Lastly there is a program that returns the identity of the function. This would be quotation of the function and then evaluating the quotation. We use first order logic to confirm these hypothesis's given a computer program and this hypothesis will prove that a set of instructions is a group.

Beyond Lisp

I have been working on a idea from John McCarthy's lecture on Beyond Lisp for awhile. There is now a wiki page up that discusses the idea (See links). It basically adds a new operator to lisp that allows you to reason using formal logic with a computer. It reasons on both inputs and outputs on the computer program. The next few posts will be outlining operators to the scheme programming language to extend it to allow for McCarthy's ideas. For more information see the links at the bottom of the page

Links
Beyond-lisp
ILC Confrence Lecture Description

My Journey To Scheme

I had been wanting to program for awhile. Since I was very little of course when I was about 10. I started off with Visual Basic which is such a depressing programming language. I lamented in a great deal of depressing programming languages for awhile. From VB to Java to HTML to javascript and the list would go on almost indefinitely. Until one fateful day I discovered lisp. The odd syntax really made me wonder what it was and how to program in it. After awhile I started to understand scheme and really got into learning it. It wasn't a depressing programming language at all but an elegant one. Something I hadn't seen in a programming language when I started learning it. For example lets compair two programs in scheme and Java.

Java Programming language

 
public class Hello {
    public static void main(String[] args) {
        System.out.println("Hello, world!");
    }
}

Scheme Programming language

(display "Hello World")

As you can see both are quite different. For example scheme uses prefix notation with parenthesis while Java uses a C like syntax. Also Java forces a object oriented system down your throat. The advantage to a prefix notation is that it is easly understood what does what. Display acts upon the argument "Hello World" and displays it. Java on the other hand makes you use the object system integrated in the language. That is one of the reasons that the Java program is much larger. This doesn't mean that Scheme can't have an object system but it could possibly have.