Topological quantum computing

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 –  http://www.theory.caltech.edu/~preskill/ph219/topological.pdf

 Anyon There? David Lindley in Physical Review Focus, Vol. 16, Story 14; Nov 2, 2005. http://focus.aps.org/story/v16/st14

Tel’s comment on my IQ tests post

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
Bokor:

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

http://www.austms.org.au/Publ/Gazette/2006/Mar06/bokor.pdf

Published article – Two generalisations of the binomial theorem

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: http://www.austms.org.au/Publ/Gazette/2006/Mar06/

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

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:

http://smh.com.au/news/opinion/priority-one-universities-must-teach-free-thought/2006/03/15/1142098523903.html

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

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

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

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
Dissertation:
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

 

IQ Tests

For a bit of fun I did the “IQ Tickle test” a year ago and just received the “detailed results” for free – of course I wasn’t going to pay for them when I did the test. While psychometricians may claim that a test is valid in some sense, the tests often have certain problems, and this IQ test demonstrates some of these limitations. I’ve been working as a test developer for a year, and so I’m more aware than previously of the pitfalls of tests (eg, a test can only capture very limited aspects of anything).

When I was a kid, I loved IQ tests, but of course, as you get older you become aware that things are much more complex than you thought they were as a kid, and in any event, there are all the problems associated with giving any credence whatsoever to test results, eg, what does a certain test result actually mean?

One question on this test in particular irked me:

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

(The arrow was my response and the tick is the “correct answer”.) The “answer” is supposedly 900. Why? Well, apparently all the numbers that John likes are squares of integers, those he doesn’t like are not squares of integers. This sounds fine at first glance, so ok, but this is only one possible answer.

The other three responses could equally well be “correct”, and this can be seen by turning the question into the following one which, to me, seems almost logically equivalent:

Given three points on a sheet of graph paper with x and y axes, which of the four following points also lies on a polynomial passing through the three given points and NOT passing through three other specified points.

(A difference between this problem and the Tickle problem is that points on an x-y plane need two pieces of data to describe them, while only one piece of data is given in the Tickle problem. Nevertheless, the principle is not dissimilar.)

Of course, any mathematician will immediately say “using Lagrange interpolating polynomials, I can, in principle, construct a polynomial passing through all three given points and also any one of the four potential responses and not passing through any of the points so specified”. 

The “answer” of 900 appears to be somewhat arbitrary.

In addition to this logical problem, there is also a problem in the way the Tickle question is constructed. Is John’s dislike of 300 related to his liking of 400, or does he just dislike the number 300 anyway, ie, are the numbers 400 and 300 specially connected in some way? This is unclear in the question. If I were writing the question I would say something like:

“John likes some numbers and dislikes others. Some of the numbers he likes are 400, 100, 3600. Some of the numbers he dislikes are 300, 99, 3700. Which of the following numbers does John also like?”

A problem with this wording is that the “pattern” of squares is not broken by the non-squares, so I would guess that more people would choose the “correct” answer.

I couldn’t work out a relation between the numbers he liked and the numbers he disliked, and so I guessed the answer (very usual behaviour for test takers). I was very surprised to learn that the “answer” was connected to squares of integers. Perhaps the “simplest” answer is what is required in these things. But what does “simplest” mean, and why is the “simplest” answer the correct one?

These are the sorts of questions that need to be raised in the construction of any test, and often they are, but can they be resolved in a satisfactory way?

Protests against the PM

On tonight’s news was a story on a protest against the PM – apparently eggs were thrown at the PM’s car.

Something I don’t understand is why people throw eggs at the PM’s car rather than engaging with the issues with argument.

On a related note, maybe it’s just me, but when trade unions protest against the new IR laws, it is unsatisfactory for them to say “they’re unfair, it’ll be terrible for working people” without backing up their claims with analysis and/or research.

Similarly, public policies should be backed up with analysis and/or research. Too often, especially in letters from government ministers supposedly explaining the reasons for a policy, is there limited or insufficient reason for the implementation of the policy. It is particularly annoying when you ask specifically for the rationale behind a policy and no rationale is provided, other than the bland “After the London bombings, the security environment is changed, and as agreed at the COAG meeting, all state and commonwealth governments are making these changes….” (eg on newish terrorism laws) – here I paraphrased what was contained in a letter from a government leader.

What – actual careful, sustained reasoning and analysis leading to policies? Perhaps it’s just too hard.

Chaitin -”The Limits of Reason”

Gregory Chaitin has written an article “The Limits of Reason” in the latest Scientific American (March 2006) (the obligatory link to scientific american is www.sciam.com). As an aside, Australian newsagencies sell editions of Scientific American about 2 months after their publication date, but I receive it promptly in the mail as I subscribe to it – very nice.

Chaitin writes that there cannot be any “theory of everything” in mathematics as there exist pieces of mathematics (eg his number Omega) that cannot be effectively compressed into a theory. While I don’t fully understand his article (I’ve only read through it quickly), I recall his previous article introducing Omega in Scientific American a few years ago made sense.

In the “Overview box”, the article is summed up (in the first dot point) by:

Kurt Godel demonstrated that mathematics is necessarily incomplete, containing true statement that cannot be formally proved. A remarkable number known as omega reveals even greater incompleteness by providing an infinite number of theorems that cannot be proved by any finite system of axioms. A “theory of everything” for mathematics is therefore impossible.

Interesting! Previously I’ve felt that mathematics could be seen as a beautiful gem, that different aspects of it were like different facets of the gem, and that there was an overall goal of unifying all the different aspects of mathematics, but I havn’t felt like this for a few years. Now I’m more interesting in constructing bits of mathematics.