What is Quantum Computing?
It’s something that could have been thought up a long time ago – an idea whose time has come. For any physical theory one can ask: what sort of machines will do useful computation? or, what sort of processes will count as useful computational acts? Alan Turing thought about this in 1936 with regard (implicitly) to classical mechanics, and gave the world the paradigm classical computer: the Turing machine. But even in 1936 classical mechanics was known to be false. Work is now under way – mostly theoretical, but tentatively, hesitantly groping towards the practical – in seeing what quantum mechanics means for computers and computing. In a trivial sense, everything is a quantum computer. (A pebble is a quantum computer for calculating the constant-position function – you get the idea.) And of course, today’s computers exploit quantum effects (like electrons tunneling through barriers) to help do the right thing and do it fast. For that matter, both the computer and the pebble exploit a q
