Something I hear people discuss quite frequently is the question “What’s the big result of the last year or two in field X?”
My current answer to this question, in the field of quantum information science, is Raussendorf and Briegel’s cluster-state model of quantum computation.
This model tells you that, in order to quantum compute, it suffices to prepare a single quantum state (the “cluster state”), and then do local (i.e., single-qubit) measurements on that state.
Such measurements suffice to write in the initial state of the computation, the dynamical operations performed, and to read out the results of the computation!
In Debbie Leung’s memorable metaphor (memorable if you’re a Unix nut, anyway!), you simply “ping” Nature, and she computes. No “dynamics”, in the usual sense of the word, just ask questions of a suitably correlated state! Those questions don’t even have to be nonlocal; all the nonlocality is carried in a single, universal state.
Whatsmore, if you believe the Church-Turing-Deutsch thesis, you can efficiently simulate an arbitrary physical system this way.
I’ve spent most of the last two months thinking about this model, and the better I understand it, the more interesting and beautiful it seems.
(Disclaimer: I guess I should say that I’ve got a bit of a personal interest in advertising this work, since I’ve done some related work.)
Well this isn’t quite fair, is it? You don’t just need the state and the local measurements, you need to be able adapt your measurements as you go along. So it’s not just that you’re “ping”ing: you’re adaptively “ping”ing.
Two questions: can you construct a classical universal computer which uses a given random distribution and adaptive measurements to get universal quantum computing?
If you don’t allow the adaptive measurements, then you are moving closer to the relm of “pseudotelepathy”. In these pseudotelepathy games, you win (or win more often) a game with quantum correlations which you would lose if you used classical correlations. But there is no communication allowed. So if you take a cluster type model and look at getting rid of the adaptive part, are their algorithms which are more powerful than classical algorithms? I think the answer is yes from quant-ph/0205133. So maybe this isn’t a question. Doh.
Dave: I wasn’t intending to mislead; you’ve got to cut the list off somewhere! Otherwise, you end up with lots of other things — you need cluster states, single-qubit measurements, ability to adapt basis, quantum memory, fast classical computation, noiseless classical communication fast on the timescale on which decoherence occurs, etc.
The question you raise is fascinating. (If you delete “quantum” at the point where I think you mistakenly inserted it!) It’d be nice to have either an example, or some solid, general no-go theorems.