DEUTSCH: If the system is a quantum computer, we can tell because of the answers that it gives us. Take Grover's quantum search algorithm, for instance. It works like this: Let's say you're writing a chess program; you're searching through all the possible continuations from a given position. From one position there might be 20 possible moves, and from each of those there are 20 for the other player, and so on, so after N moves there are 20 to the power N different possible continuations. And you want to program the computer to search through all those continuations to evaluate a given move. Say you want it to search through a trillion continuations. It is a trivial theorem of classical computation, that if you want to search through a trillion unknown things, you generally have to do a trillion physical operations of some kind. You might be able to do some of them in parallel, but a given computer will only be able to do a fixed number at a time in parallel. One way or another you have to do a trillion things, so if you want to use the same computer to search through two trillion things it must take at least twice as long, and so on.

But with a quantum computer, you could do better: First of all, to search through a list of a trillion things you need only do a million operations. In general, in order to search through N possibilities one need only do the square root of N physical operations. And then, if you let your quantum chess machine think for twice as long, it will examine four times as many continuations. Three times as long, nine times as many, and so on. The explanation of this, in terms of many universes, is very simple. It's just that there are the square root of N universes collaborating on such a task. But again, never mind the question of interpretation as such. If we just think of what this computation implies for the reality we find ourselves in, again, the answer is that reality is much bigger than it looks. The winning move, when we find it, logically depends on all the positions we searched. So as a matter of logic, those positions must all have existed somewhere, and been compared with the answer we got.

EDGE: There seems to be a gap here, between abstract information on the one hand, and physical objects such as computers and stars and universes on the other. What's the connection?

DEUTSCH: Ultimately, information has got to have a physical realization; that's why it does come down to atoms, or stars, or whatever, in the end. But because of the universality of computation you don't have to think in terms of specific implementations. I don't have to know whether my information is going to be stored in magnetic disc, or whatever. I just know that more information means a bigger object.

EDGE: Where is work on quantum computation being done?

DEUTSCH: More and more places every day, it seems. In the US alone there are about a dozen very high quality research groups working flat out on quantum computation, theoretical and experimental. Probably another dozen in Europe. Also Japan, Australia, Israel...

EDGE: Let's talk about practical things. You're at a Microsoft, an Intel, a Sun Microsystems, and you read about David Deutsch and his theories about quantum computing. How will it impact your business? What measures would you take?