Abstract:
What sort of machines do useful computation in a universe described by classical mechanics?
The answer was provided in 1936 by the British mathematician Alan Turing,
and it’s known today as the Turing machine. But even in 1936 classical mechanics was
known to be false, and so one could have asked the question: What sort of machines do
useful computation in a universe described by quantum mechanics? In a trivial sense,
everything is a quantum computer. A pebble is a quantum computer for calculating the
constant-position function; current computers exploit quantum effects (like electrons
tunneling through barriers) to control computation and to be able to run fast. But
quantum computing is much more than that. In what follows we will present – in the
form of a biased, informal dialogue – a few key-ideas on quantum computing.