David Deutsch

He is widely recognised throughout the scientific world as the man who has rekindled and sustained interest in Quantum Computing. This subject is not new, and indeed Alan Turing himself made a practical contribution to the subject. The concept has been discussed amongst physicists in the past but it is only since the seminal paper of David Deutsch in 1985 that the subject has really taken off.

In 1973 Charles Bennett, in an IBM Journal article, had shown that a reversible Turing machine was a theoretical possibility. And then Paul Benioff, Paris, gave a quantum mechanical description of a Turing machine in 1980. Then Richard Feynman, Caltech, in 1982 showed that while no classical Turing Machine could simulate certain quantum phenomena but that a "universal quantum machine" could do so. (Tony Hey of Southampton U. has recently published a book setting out Feynman's lectures on computing). But this work in the early '80s made little impact at the time because these were very theoretical concepts for which no machine design was provided.

In 1985 the scene changed dramatically when David Deutsch published his seminal paper describing the first true Quantum Turing Machine (QTM). Just as Alan Turing in his famous paper "On computable numbers..." gave more detail than he needed to do so in such a theoretical paper on how his machine might be achieved, so David Deutsch described how such a quantum machine might read, write, and carry out shift operations by quantum mechanical interactions.

Whereas a conventional classical Turing machine can only encode a bit as a 0 or a 1, his QTM could encode a qbit as a blend of 0s and 1s simultaneously. Thus the Quantum computer has the ability to perform calculations on all the inputs in the time it would take a classical computer to perform just one. This property he called quantum parallelism, and leads to the quantum computer being able to overcome certain practical but fundamental limitations of classical computers (for example as was subsequently shown, generating true random numbers, factorising large numbers, or speeding the retrieval of unordered information. ["Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer", Proc Royal Soc Vol A400, 1985]

Then in 1992 Deutsch and Richard Jozsa (at that time working with him in the Clarendon at Oxford) showed that for some problems the Quantum computer was exponentially faster than the classical machine. This led Peter Shor, Bell Labs, in 1994, to demonstrate an algorithm that would factorise a large integer in polynomial time, rather than in exponential time, thus being able, in principle, to defeat the widely used RSA cryptographic method. (That the approach works in practise has been demonstrated recently in both Oxford and MIT, albeit so far with a trivial problem).

A growing flood of practical work to build a practical machine was unleashed by David Deutsch's paper of 1985. Some five or more different approaches are being worked on in Europe and the USA. And there is now considerable work on quantum algorithms, for example Lov Grover (Lucent Labs) has shown how the time to retrieve information can be cut. David Deutsch himself continues to produce rapid solutions to practical problems. He acts as the focus and leading light to the ever-growing community. He has shown how quantum mechanical principles might be applied to obtain secure communications (1989). (This has now been demonstrated in demonstrations in Austria and Switzerland); and to quantum computational networks (1989).

It is too early to say that a useful quantum computer will ever be built and sold, though there are few working in the field who now doubt it. It is inconceivable that quantum mechanical approaches will not now find applications, for example in communications probably within the next decade or less. But in any case his work has made a major contribution to the theoretical underpinning of computation by extending the Turing machine principle. And he has served to launch a flood of work, both theoretical and practical, which cannot help but increase man's understanding of computation - and some say (including David) of the very way in which man thinks.

About David

David Deutsch was born in Israel in 1953, but he and his family moved to England in 1956. He was an exceptional school boy, winning a "round the world" scholarship when he was 17.

He went up to Cambridge in 1971, and read physics and then mathematics, obtaining a 1st.

He joined David Sciama's group at the Clarendon Laboratory in 1975. At first his work centred round relativity, but then he focused on quantum mechanics. He shared his time between the University of Austin and England on various grants and fellowships, including a prestigious Royal Society fellowship. He now holds a research post at Oxford, where he is recognised as one of the outstanding thinkers of his age.