Throughout my research career I have been interested in the most fundamental issues. I got into quantum mechanics because it is the deepest knowledge known to science. I did various kinds of work on quantum field theory, in the hopes of making progress on quantum gravity. I worked on quantum measurement theory and so became an advocate of the many-universe interpretation. I saw that there was a need to extend the idea of Alan Turing and others of a universal computer to use quantum-mechanical physics. And I did that: I proposed the universal quantum computer and proved it was universal. I showed it had properties that no existing computer had.

  That raises two questions. First, how do you define "fundamental?"

A fundamental idea is one which is needed in the understanding, or in explanations of many other ideas. For instance, the laws of thermodynamics are fundamental laws. You don't just need them to understand how steam engines work, but to understand how microchips and supernovas work. The word "explain" is important here. Not just "predict." Prediction is a characteristic of scientific theory, but it’s not the most important one—the most important one is explanation. A fundamental theory is needed in the explanation of many diverse things. The more and more diverse phenomena the theory can explain, the more fundamental it is.

  Now the second question: What constitutes a universal computer?

It's perhaps not obvious to lay people that all existing computers—the one you have on your desk, the supercomputers that the National Security Agency uses, and the computer in your watch and so on—all of them are, in terms of their repertoire of possible computations, completely identical to each other. They differ only in speed and memory capacity. Any one of them, if you let it run long enough or give it enough memory, would be able to completely duplicate all the functions of any other one. That property is called universality. Alan Turing was the first person to postulate a universal computing machine and prove it was universal within a certain domain. But that was for classical physics, not quantum physics. My innovation was to redo his work using explicitly quantum physics instead of implicitly classical physics.

  When did you do that work; where was it published and what was the impact?

That was in the early 1980s and published in 1985 in the Proceedings of the Royal Society of London. That paper ("Quantum-theory, the Church-Turing principle and the universal quantum computer," Proceedings of the Royal Society of London A 400 [1818]: 97-117, 1985) began the modern subject of the quantum theory of computation, which asks about the many types of computation that a quantum computer can do but a classical computer cannot do, no matter how much extra memory and extra time it is given.

  Is it a difficult transition to move from tackling fundamental questions about the universe to tackling fundamental questions about computation?

What it mainly takes is for the link to be there. I'm not particularly interested in making new and better kinds of computers, nor in understanding the theory of computation for its own sake. What I want to work on is what is fundamental: to understand the important issues of the foundations of physics, what quantum theory means, what it is telling us about the structure of reality, and so on. To do that, it turns out one has to express the laws of physics and explanations of physical processes in terms of computation and information flow. And that is true, regardless of whether you're thinking of a computer or any physical process. The universality that exists in the world means that when you're studying the general theory of how information can flow around inside a quantum computer, you are automatically studying the general theory of how information can flow, period. That in turn means you're discussing physics in general, period, because any physical process can be regarded as information processing. Any kind of experiment you can think of doing—where you prepare some physical system in a certain way, according to a certain system or algorithm, and you let it do something and then measure it according to some algorithm and get a result, either a number or a yes or no—all that is information processing. The structure of the universe or of physical reality is based on information flow and the study of it amounts to the study of information flow. And the best formalism and language and theory for understanding that is the theory of computation—but computation as implemented in the deepest-known physical laws. That means the quantum theory of computation.

  One of your highly cited papers is "Conditional quantum dynamics and logic gates" (Physical Review Letters 74 [20]: 4083-6, 15 May 1995). What are you saying in that paper and what is the impact?

As I see it, the reason why that paper was worth doing was it showed that you could build universal quantum computers entirely out of a type of gate, called a conditional operation gate. The simplest of conditional operation gates is almost universal just by itself. It's called a controlled NOT gate. It's a two-qubit gate, where a qubit is the quantum equivalent of a bit, and it does nothing if the first input is a zero, and it flips the second input if the first input is a one. It's also called a perfect measurement gate because when the second bit is a zero, the output of the second bit is always identical to the input of the first bit. So the second bit has measured the first bit. In that paper we show how to build a general quantum computational network just from these controlled NOT gates and from one-qubit gates, which are overwhelmingly simpler to implement than two- or more- qubit gates. We were showing how to get to universality via conditional dynamics. It's nice from the implementation point of view.

  Another one of your highly cited papers was "Quantum privacy amplification and the security of quantum cryptography over noisy channels." Do you think quantum cryptography will be a practical method of insuring privacy in communication?

Some time in the next few years it's going to actually be implemented and it’s going to revolutionize secure communications. I am not an expert in experimental physics, and I'm far less of an expert in engineering or marketing, but I can still say that sometime in the next few years, the range, reliability, and scope of quantum cryptographic devices will be enough to allow them to be actually used in real life. That will mean that communication can be perfectly secure. Also, most of the existing classical secure methods becoming insecure because they will become vulnerable to attack by quantum computational algorithms. By sheer coincidence, quantum computational algorithms just happen to be particularly suitable to cracking classical codes.

  What about the future of quantum computation in general?

Practical applications of quantum computation in general are far more distant. Quantum computation is one of the greatest challenges facing experimental physics. Going to the moon is nothing compared with it. It is also a very beautiful area of study because it appears to involve practically the whole of physics and it stretches the theoretical and experimental resources of every branch of physics. It's cool in that way. But it does mean we are talking about decades before anything useful comes out. Although well before quantum computers are practical or before we know how to do quantum computation in the laboratory, the quantum theory of computation is already teaching us a lot about physics.

  What are your goals for your future research?

I don't really set goals. I have hopes. I just want to work on things that are fundamental. I have always wanted to do that. With or without success, this is all I have ever wanted to do.

Dr. David Deutsch
Centre for Quantum Computation
University of Oxford
Oxford, England