Topological quantum computing

March 30, 2006

In the latest (April) issue of Scientifical American, Graham Collins has written an article on the theoretical possibility of a topological quantum computer, which can simulate any computation of a usual quantum computer within any desired non-zero approximation. Also, the operation of a topological quantum computer cn be simulated efficiently to arbitrary accuracy on a conventional quantum computer. In some sense, a topological quantum computer, is, to some approximation, as good as a usual quantum computer in computing, and vice versa.

This is good. Now, the attraction of a topological quantum computer is that it employs the topology of space-time paths in 2 + 1 space, or, more in more picturesque language, the topology of knots (and links) in 3-space. The interesting and useful thing about this is that by definition, the topology of a mathematical knot in 3-space is not unstable if you perturb the knot a little bit; by definition, the topology of the knot is stable.

The topological quantum computer uses two-dimensional quasiparticles called anyons, which are so called as they don't have to be bosons or fermions – their phase can change by some complex number that is not 1 or -1 if you interchange two anyon's positions (this is from the article – I'm not a physicist so excuse any misconceptions here!).

The article says something which struck me as very interesting:

Michael Freedman, now at Microsoft, lectured at Harvard University in the fall of 1988 on the possibility of using quantum topology for a computation. These ideas, published in a research paper in 1998, built on the discovery that certain mathematical quantities known as knot invariants were associated with the quantum physics of a two-dimensional surface evolving in time. If an instance of the physical system could be created and an appropriate measurement carried out, the knot invariant would be approximately computed automatically instead of via an inconveniently long calculation on a conventional computer. Equally difficult problems of more real-world importance would have similar shortcuts.

Now, if a knot invariant, which can be easily calculated from (potentially very large) square matrices is all you need to construct a computation of a topological quantum computer, and if a topological quantum computer can "approximately" do any computation that a usual quantum computer can do, does this mean that a normal boring everyday computer running maple or mathematica or even matlab can "approximately" simulate a quantum computer?

In the article, they give a topological quantum computer version of a CNOT gate (CNOT stands for controlled not) – which is just a tangle on six piece of string. You can write down a knot invariant for the closed version of this tangle by taking the quantum (super)trace of an at most 18 by 18 matrix (employing the 2-dimensional irreducible rep of the quantum (super) algebras related to sl(2) or osp(1|2)). This is not very hard to do.

The article says the following:

Acting on qubits, any computation can be built from a network of CNOT gates and one other operation – the multiplication of individual qubits by a complex phase.

Of course, the details are no doubt more subtle.

Links from the Scientific American article:

Topological Quantum Computation – Lecture notes by John Preskill –

 Anyon There? David Lindley in Physical Review Focus, Vol. 16, Story 14; Nov 2, 2005.


Tel’s comment on my IQ tests post

March 20, 2006

My friend Tel wrote a comment on my post on IQ tests, and I liked it so much that I’ve taken the liberty of reproducing it below, along with the offensive question.

The article Tel links to is well worth reading, as it summarises nicely the kinds of arguments I wrote in my post. The offensive IQ question was:

John likes 400 but not 300; he likes 100 but not 99; he likes 3600 but not 3700. Which does he like: 900, 1000, 1100, 1200.


Hi Sacha,

Horrible question, the “obvious” answer depends on the assumption that 
John is as mathematically naive as the writer of the question.

This month’s issue of the AustMS gazette has a nice article by Imre

Problem 1.         1,2,3,x,…                 Find x.

He goes on to give examples which show the question is ill-formed. The
question in the intellignece test and many questions like it are
ill-formed and thus do not  have a solution.

See Bokor’s article, well worth the read

Published article – Two generalisations of the binomial theorem

March 20, 2006

My first refereed article has just been published in the Gazette of the Australian Mathematical Society – here is the article in pdf format and the table of contents of the volume is:

This article is effectively Appendix B from my thesis, although it may look slightly different, and it answers two of the math exercises I set in an earlier post. I decided to submit it for publication as I couldn’t find these generalisations in the literature and I thought that other people might find them interesting or useful.

Opinion piece on the role of Universities in the SMH

March 16, 2006

Steven Schwartz, the new Vice-Chancellor of Macquarie University, has written an interesting opinion piece on the role of Universities in the SMH, partly in response to recent comment that engineering graduates weren’t graduating with sufficient skills:

To quote two paras:

We have put so much emphasis on the utilitarian aspects of our activities that organisations such as the business council have become convinced that universities exist mainly to confer economic benefits. Now, economics is vital. The country needs educated people and graduates need jobs. A sound economy is also essential if we are to achieve our social goals. But first we need to have goals. Otherwise, we are a nation of means without ends.

What should universities be striving to achieve? According to the Nobel laureate Friedrich Hayek, social institutions such as universities should be judged by the extent to which they promote human liberty and freedom.

As someone who likes liberty, freedom and the promotion of imagination, I’m quite attracted to Hayek’s view.

The Continuum Hypothesis

March 15, 2006

The Continuum Hypothesis is very interesting. According to mathworld, It is a proposal (originally by George Cantor) that there is no infinite set with a cardinal number between that of the infinite set of integers and the larger infinite set of real numbers. It is easy to show that the second infinite set is larger than the first – 1st year students are shown this (think Cantor’s diagonal argument which would be familiar to most tertiary maths students who have studied topology or analysis).

Is the Continuum Hypothesis true? To quote from mathworld,

Gödel showed that no contradiction would arise if the continuum hypothesis were added to conventional Zermelo-Fraenkel set theory. However, using a technique called forcing, Paul Cohen (1963, 1964) proved that no contradiction would arise if the negation of the continuum hypothesis was added to set theory. Godel’s and Cohen’s results established that the validity of the continuum hypothesis depends on the version of set theory being used, and is therefore undecidable (assuming the Zermelo-Fraenkel axioms together with the axiom of choice).

Ok, I’ve just rewritten what’s in the link! You might enjoy clicking on the link and learning about the Axiom of Choice and set theory. One thing I’d like to do is to learn more about this.

In general, I like things to be as free and general as possible, so I like the idea (see the link) of adopting an axiom which (together with the Zermelo-Fraenkel axioms and the axiom of choice) would imply that the continuum hypothesis is false.

Human Rights forum

March 12, 2006

Yesterday Mr T and I went to Leichhardt town hall for a very interesting forum on human rights and potential human rights laws in Australia. The speakers were Rob Hulls (the Victorian Attorney-General), former Senator Susan Ryan (from New Matilda) and Julian Burnside, a very erudite human rights QC.

The New Matilda draft Human Rights Bill looks well-worth having a look at – an interesting feature of it is that the model is one in which each Bill is assessed against Human Rights laws, and if the Bill is thought to not be in accordance with the Human Rights laws, then the AG and Parliament are informed of this and they respond in whatever way they think appropriate. So it doesn’t involve Judges striking down laws.

Mathematics Genealogy Project

March 8, 2006

Over at the Mathematics Genealogy Project, the American Mathematical Society (of which I am a member) is creating a voluntary database of mathematics PhD graduates and their supervisors, going back as far as possible.

I’ve put my details into the database but so far they don’t appear. But if you put my supervisor’s details into the database: (Ruibin Zhang), the “math genealogy” below appears. Carl Gauss is one of my mathematical forebears! He is my mathematical “great-great-great-great-great-great-great-great-great-grandfather”.

R. B. Zhang: Ph.D. University of Tasmania 1986
Dissertation: The Gauge Technique
Advisor: Robert Delbourgo

Robert Delbourgo: Ph.D. 1964
Dissertation: The Gauge Technique
Advisor: Abdus Salam

Abdus Salam: Ph.D. University of Cambridge 1952
Dissertation: Renormalisation of Quantum Field Theory
Advisor 1: Unknown
Advisor 2: Nicolas Kemmer

Nicolas Kemmer: Ph.D. Universität Zürich 1935
Advisor: Gregor Wentzel
Gregor Wentzel: Dr. phil. Ludwig-Maximilians-Universität München 1921
Dissertation: Zur Systematik der Röntgenspekten
Advisor: Arnold Sommerfeld

Arnold Sommerfeld: Ph.D. Universität Königsberg 1891
Dissertation: Die willkürlichen Functionen in der mathematischen Physik
Advisor: C. L. Ferdinand Lindemann

Carl Louis Ferdinand Lindemann: Ph.D. Friedrich-Alexander-Universität Erlangen-Nürnberg 1873
Dissertation: Über unendlich kleine Bewegungen und über Kraftsysteme bei allgemeiner projektivischer Maßbestimmung
Advisor: C. Felix Klein

Christian Felix Klein: Ph.D. Rheinische Friedrich-Wilhelms-Universität Bonn 1868
Dissertation: Über die Transformation der allgemeinen Gleichung des zweiten Grades zwischen Linien-Koordinaten auf eine kanonische Form
Advisor 1: Julius Plücker
Advisor 2: Rudolf Lipschitz

Julie Plucker: Ph.D. Philipps-Universität Marburg 1823
Dissertation: Generalem analyeseos applicationem ad ea quae geometriae altioris et mechanicae basis et fundamenta sunt e serie Tayloria deducit
Advisor: Christian Gerling

Christian Gerling: Dr. phil. Georg-August-Universität Göttingen 1812
Dissertation: Methodi proiectionis orthographicae usum ad calculos parallacticos facilitandos explicavit simulque eclipsin solarem die
Advisor: Carl Gauß

Carl Gauß: Ph.D. Universität Helmstedt 1799
Dissertation: Demonstratio nova theorematis omnem functionem algebraicam rationalem integram unius variabilis in factores reales primi vel secundi gradus resolvi posse
Advisor: Johann Pfaff

Johann Pfaff: Dr. phil. Georg-August-Universität Göttingen 1786
Dissertation: Commentatio de ortibus et occasibus siderum apud auctores classicos commemoratis
Advisor: Abraham Kaestner

Abraham Kaestner: Ph.D. Universität Leipzig 17
Dissertation: Theoria radicum in aequationibus
Advisor: Christian Hausen

Christian Hausen: Dr. phil. Martin-Luther-Universität Halle-Wittenberg 1713
Dissertation: De corpore scissuris figurisque non cruetando ductu
Advisor: Johann Wichmannshausen

Johann Wichmannshausen: Ph.D. Universität Leipzig 1685
Dissertation: Disputationem Moralem De Divortiis Secundum Jus Naturae
Advisor: Otto Mencke

Otto Mencke: Ph.D. Universität Leipzig 1665, 1666
Dissertation: Ex Theologia naturali — De Absoluta Dei Simplicitate, Micropolitiam, id est Rempublicam In Microcosmo Conspicuam
Advisor: Unknown