EDGE: In what direction are you asking the most questions at the moment?

DEUTSCH: The direction of even deeper connections between physics and the theory of computation. We've got the quantum theory of computation — which, by the way, is THE theory of computation. As I always say, we have to regard the Turing theory (the traditional theory of computation) as being just the classical approximation to the real, quantum theory of computation. We already know of a few issues in theoretical physics (like the Maxwell Demon question, and the relationship of thermodynamics with statistics) which it is useful to regard as computational questions — questions about how information can or cannot be processed. What I am aiming for now is a new kindof theory, quantum constructor theory, which is the theory of what can be built, or more generally, the theory of what can be done, physically.

We build computers and skyscrapers and space ships, and we clone animals, and so on. At root you can regard all of these too as computations, because when you build a space ship and fly it to a different place, you get new information, or rather a different perspective on the same information, which is just what happens when you input information into a computer and look at the output. However, flying in a spaceship is not quite the same, even computationally speaking, as putting a camera on the space ship and letting it go somewhere, and watching, because, for instance, there's a time delay, so the machine gets harder to interact with if it's far away. Experience is inherently interactive, so there's a fundamental difference, imposed by the laws of physics, between the information processing you can do by going there vicariously using a robot and what you can do going there in person.

I've been thinking about those questions; that is, what sorts of computations do physical processes correspond to; which of these 'computations' can be arranged with what resources? And which sorts can't be arranged at all? What little we know about this new subject consists of a few broad limitations such as the finiteness of the speed of light. The theory of computability and complexity theory give us more detail on the quantum side. But a big technological question in my field at the moment is, can useful quantum computers actually be built? The basic laws of physics seem to permit them. We can design them in theory. We know what physical operations they would have to perform. But there is still room for doubt about whether one can build them out of actual atoms and make them work in a useful way. Some people are still pessimistic about that, but either way, that debate is not really a scientific one at the moment, because there is no scientific theory about what can and can't be built. Similar questions are raised by the whole range of nanotechnology that has been proposed in principle. So that's where a quantum constructor theory is needed.

EDGE: Why specifically a quantum constructor theory?

DEUTSCH: Because quantum theory is our basic theory of the physical world. All construction is quantum construction.

EDGE: What is distinctive about a quantum computer, compared to the computers we know today?

DEUTSCH: Quantum computing is information processing that depends for its action on some inherently quantum property, especially superposition. Typically we would superpose a vast number of different computations — potentially more than there are atoms in the universe — and then bring them together by quantum interference to get a result. Other quantum computations, notably quantum cryptography, couldn't be done by classical computers even in theory.

EDGE: What is the importance of this work?

I think that in future, quantum mechanics textbooks will use quantum computations as their introductory examples, rather than calculating the energy levels of the hydrogen atom and suchlike, which contain a high proportion of irrelevant stuff. Quantum computation gets down to basics, because quantum computation is the basics.

EDGE: But for you, the main application of the theory is to change our sense of the nature of reality?

DEUTSCH: Yes. However useful the theory as such is today and however spectacular the practical applications may be in the distant future, the really important thing is the philosophical implications — epistemological and metaphysical — and the implications for theoretical physics itself. One of the most important implications from my point of view is one that we get before we even build the first qubit [quantum bit]. The very structure of the theory already forces upon us a view of physical reality as a multiverse. Whether you call this the multiverse or 'parallel universes' or 'parallel histories', or 'many histories', or 'many minds' — there are now half a dozen or more variants of this idea — what the theory of quantum computation does is force us to revise our explanatory theories of the world, to recognize that it is a much bigger thing than it looks. I'm trying to say this in a way that is independent of 'interpretation': it's a much bigger thing than it looks.

EDGE: What do you mean by 'bigger'?

DEUTSCH: What I mean is — suppose we were to measure 'amounts' of reality, the sizes of things, in terms of the amount of information needed to describe them. To specify the positions of the atoms in this room, I need three numbers for each atom. The more atoms I want to describe, the more numbers I need. The more accurately I want to do it, the more decimal places I need to give. So that requires a certain amount of information. I can think of doing that for the whole universe. That may sound a lot of information, because there are 10^80-odd atoms in the known universe, not to mention the other degrees of freedom. So it may seem unimaginably vast. Yet it is minuscule compared to the amount of information that would be needed to specify the computational state of a single quantum computer, sitting on some future laboratory bench. So in terms of world view, or conceptual model, a quantum computer is a much bigger object than the whole of the classical universe. This fact forces quite a change in our world view.

EDGE: So the theory tells us that a quantum computer is in itself a universe.

DEUTSCH: It would be an object far more complex than the whole of the classical universe. The whole of physical reality is like that too, of course, and we sometimes call it the multiverse. We see, very roughly, a classical universe out there because most of the multiverse is not directly accessible. You can only infer the existence of hidden quantum information indirectly, as in the entanglement experiments I mentioned.

To many people this conclusion was already compelling even before quantum computers. The many-universes interpretation was proposed in 1957. But you can construe all the earlier arguments as being computational arguments too. The people making them didn't think of them as such, but that's what they were. They were saying: we look around us and we see something that's approximately a classical universe, and we might expect that if you take quantum mechanics into account, that might add a certain amount of extra 'stuff' — like relativity did — which behaves differently but there's still roughly the same 'amount' of reality as we thought there was. But that's not what happens when you take quantum mechanics into account. Reality becomes a vastly, exponentially bigger and more complex thing than it was under classical physics.

EDGE: How can we tell that there's so much of this 'hidden information' in a quantum system?

DEUTSCH: Apart from quantum cryptography, it's unlikely to have practical applications in the near or medium-term future. It's theoretical. But as such it does give us some immediate benefits. One is the benefit of looking backwards. Let me give you a recent example from my own work.

Quantum mechanics, in the traditional formulation, seems to have a 'non local' character: that is, things you do HERE instantaneously affect things that happen THERE. It has been known from the beginning that this 'non locality' can't be used to send signals or anything. But still, philosophically, what are we to make of it? What sort of reality is quantum mechanics telling us we live in? And of course it's hard not to wonder: "well, if something gets there instantaneously, it is going faster than light. So in another reference frame it's travelling into the past. So it could create paradoxes; couldn't that solve the problem of consciousness, explain telepathy, summon up ghosts...?" — you name it. This non-locality idea is one of the things that's helped to fuel the appalling mysticism and double-talk that's grown up around quantum mechanics over the decades.

But once you understand that this is all about information processing, it becomes much easier to stop hand-waving and start calculating where the information actually goes in quantum phenomena. That's what Patrick Hayden and I did. The results (recently published in Proceedings of the Royal Society — click here [2]) blow the 'quantum non-locality' misconception clean out of the water. Doing things HERE can only affect things THERE (visibly or invisibly) once the information about what you've done here has travelled there in some information-carrying physical object. Nothing instantaneous; nothing non local, nothing mystical.

EDGE: What about the famous experiments that demonstrate quantum non-locality in the lab?

DEUTSCH: They don't. They demonstrate quantum entanglement: one of the fundamental quantum phenomena, but a local one. It turns out that when it look as though there's a non-local effect — as in Bell-inequality experiments — what's really happening is that some of the information in quantum objects has become inaccessible to direct observation. And in our analysis we actually track how this information travels during entanglement phenomena. It never exceeds the speed of light, and it always interacts in a purely local way.

By the way, the presence of such not-directly-accessible information can be seen as the very thing that's responsible for the power of quantum computers. The insights we gained from that work are leading in other very promising directions too.

EDGE: Such as?

Well, I am currently working on two spin-offs of that paper. One is work on the structure of the multiverse — making precise what we mean by such previously hand-waving terms as 'parallel', 'universes' and 'consists of'. It turns out that the structure of the multiverse is largely determined by the flow of quantum information within it, and I am applying the techniques we used in that paper to analyse that information flow. The other is a generalization of the quantum theory of computation, to allow it to describe exotic types of information flow such as we expect to exist in black holes and at the quantum gravity level. This is all in the context of my growing conviction that the quantum theory of computation isquantum theory.

Speaking of that, another spinoff from the quantum theory of computation is that it provides the clearest and simplest language, and mathematical formalism, for setting out quantum theory itself. I'm planning a series of lectures on video which I think will be quite revolutionary. They will constitute a course in quantum theory for an audience that has no previous knowledge of it — say, university-entry level — all the way to leading-edge issues in quantum computation, in just twelve lectures (we're currently looking for a sponsor for them, by the way!).

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?

DEUTSCH: If computers are going to continue to become more powerful, processors and memory devices must become smaller. For that reason alone, quantum processes must be harnessed. Whether to make quantum computers or not doesn't really matter. Even to make classical computers out of atomic-scale components you'd have to use quantum physics and ultimately the quantum theory of computation. And once you're making those, the same technology could probably also make quantum computers. And the incentive would be there because of the various inherent advantages of quantum computation.

EDGE: How would you build one?

DEUTSCH: Proposed technologies for building them are at present competing. We don't know which way it's going to go. It could be ion traps or it could be quantum dots, or other solid state devices, or it could be superconducting loops. It could be molecules, or something we don't know about yet.

At present the biggest quantum computer in the world has about 3 qubits. Not much practical use, and it requires quite a large apparatus to make it work. Yet with three qubits you can already implement quantum algorithms that no classical computer using three bits could mimic.

Quantum cryptographic devices already exist in the laboratory. Eventually that's going to give perfectly secure communication. No longer will cryptography depend on the difficulty, or the intractability, of guessing an unknown key. It will simply be physically impossible to discover the key if you don't have the relevant physical object. So that is the ultimate in cryptography.

EDGE: We know that historically, advances in cryptography have been suppressed by governments. Could it be that quantum computers will never come on the market because people will make sure they don't?

DEUTSCH: If so, I know nothing about it. Both in Britain and America there are government agencies working on quantum cryptography, and as far as I can tell, they participate in much the same way as they would if they were academic institutions. Presumably they have their secrets — I hope they do! — but I'm not aware of them having tried to prevent any of these technologies from being developed, let alone theoretical advances. But I do find it a bit surprising, now that you come to mention it, that there isn't already a quantum cryptographic device on the market.

EDGE: For e-business?

DEUTSCH: No. The trouble is that at the moment quantum cryptography is severely limited in range. It can't be done through open air. It's got to be done through fiber-optic cable, and I think the world record is about 100 kilometers. But still, you could wire up the City of London, or central Washington DC, with absolutely secure communications. I don't know why that hasn't been done. I doubt that it has anything to do with sinister machinations by the government, though. It's probably just that it takes a long time for an idea to become genuinely commercially viable.

EDGE: What if there was a critical situation such as a war which required security?

DEUTSCH: In that case we already know how to build absolutely secure communications if we want to, at ranges of a few kilometers. Longer ranges would present a problem, but at least one group at Los Alamos is working on a system that would allow you to bounce quantum-encrypted messages off a satellite, and that would essentially solve the problem.

In the long run the problem could also be solved by quantum repeating stations. Unfortunately they would require much more sophisticated quantum computation than the raw cryptography does. They will come along eventually, perhaps in a decade or two.

Another thing that will come along — probably after more than a decade or two — is quantum cryptanalysis, where you would use a quantum computer to decrypt existing codes. Quantum decryption machines would render existing cryptographic systems obsolete.

EDGE: Ten years from now will I have any quantum-computer technology on my desk?

DEUTSCH: I guess not. But who knows? I've been surprised repeatedly by how well the experimentalists have been able to implement theoretical concepts in quantum computing. But apart from quantum cryptography I'd be amazed if anything technologically useful comes out in ten years, 20 years, even longer. But I've been amazed before.