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