David Deutsch – making more sense than common sense

“Our best theories are not only truer than common sense, they make more sense than common sense.” — David Deutsch in The Fabric of Reality

It was recently announced that David Deutsch would be one of four recipients of the 2023 Breakthrough Prize in Fundamental Physics, alongside Peter Shor, Charles H. Bennett and Gilles Brassard. The Breakthrough Prizes (known as the ‘Oscars of Science’) were first set up in 2012 to celebrate the achievements of the world’s top scientists, and every year sees the presentation of three main awards, worth $3 million each, in the fields of Life Sciences, Fundamental Physics and Mathematics.

This year’s Fundamental Physics award celebrates the work of some of the most important pioneers in the field of quantum information. Charles H. Bennett and Gilles Brassard were part of a team of collaborators who discovered quantum teleportation, and they also developed an unbreakable cryptographic key distribution scheme built on the rules of quantum mechanics. On the other side of the quantum cryptographic tug of war, Peter Shor developed a factorisation algorithm (Shor’s algorithm) that is capable of breaking some of the most important cryptographic schemes used today.

David Deutsch
David Deutsch

Clearly Dr Deutsch will be in good company at the award ceremony, but his own achievements are no less impressive. Though many point to Richard Feynman as the founder of quantum computation, it was David Deutsch who described both the first universal quantum computer and the first universal quantum gate. On top of this, he also showed that a quantum computer could solve certain problems faster than any known classical counterpart. Not at all bad for a man who has never had a conventional job!

Early years

David Deutsch got his undergraduate degree in Natural Sciences from Clare College, Cambridge where he undertook Part III of the Mathematical Tripos, a one-year master’s program considered to be one of the hardest mathematical courses in the world. After graduation, he went on to Wolfson College, Oxford, where he studied quantum field theory in curved space-time for his doctorate under Dennis Sciama and Philip Candelas. In what might be considered foreshadowing of Deutsch’s own work, Dennis Sciama earned his own PhD under the supervision of Paul Dirac, making Deutsch the PhD grandchild of one of the founders and pioneers of quantum mechanics.

It was also whilst at Oxford that Deutsch learned of the Many Worlds Interpretation (MWI) of Quantum Mechanics, developed by Hugh Everett in his 1957 doctoral thesis. In the MWI, we live in just one of an uncountably large number of universes (an MCU-style multiverse if you will) that collectively represent every possible state of every quantum system that has ever existed. Think of this like there being universes for every different choice that you either made or could have made in your life (whether to go out partying or stay in, whether to call that girl back, whether to take a chance on the out-of-date milk etc.). Each time you chose one of the options available to you, but in other universes other yous chose differently. Taken together, your multiverse would contain versions of you that have lived every possible different life that you could have possibly lived.

In the Many Worlds Interpretation, we live in just one of an uncountably large number of universes that collectively represent every possible state of every quantum system that has ever existed

Bringing this back to quantum, the starting point is a quantum mechanical system that exists in a ‘quantum superposition’ of different states, literally meaning that the system is in each of the multiple states simultaneously. When this multi-state system is then measured, it switches to a single state system corresponding to the measurement result, which is most commonly interpreted by physicists as the multi-state system ‘collapsing’ to a single state at the precise moment of measurement. But in the MWI, it is instead postulated that there exist different universes where the system is in each of the different possible states, and that it is a cross-universe interaction between these different (uni)versions of the system that cause the multi-state phenomena of quantum systems prior to measurement. Therefore, rather than the measurement collapsing the system, the MWI says that the measurement instead stops the (already single state) quantum system interacting with other versions of itself in other universes.

Whilst this interpretation of quantum mechanics lacks widespread acceptance within the physics community, it would have (and still has) a large influence on Deutsch’s own research and philosophy.

Quantum research

Dr Deutsch continued his quantum research after completing his PhD in 1978, resulting in the publication of his 1985 paper: ‘Quantum theory, the Church-Turing principle and the universal quantum computer’. This represented the first formulation of the concept of a true quantum computer, built on the rules of quantum (rather than classical) mechanics.

Apparently, the insight for this work came from a conversation Deutsch had with Charles H. Bennett (one of the same men that Deutsch is now sharing the Breakthrough Prize with) in the early 1980’s. In this conversation, Deutsch complained that those who were working on the relatively new theory of computational complexity were somewhat wasting their time, as there was no standard computer with respect to which the complexity of a task could be determined. In other words, it could only be determined how complex a task was in reference to some computer, not how complex the task was fundamentally. Bennett, however, pointed out that there was in fact such a standard computer, that being physics itself.

Deutsch realised that Bennet was right, but also realised that the complexity theorists were using the wrong physics. In particular, they were using classical physics, which is just an approximation of the real physical laws at a large scale (i.e., the scale that we experience life at every day). In fact the problem ran deeper than this, as the modern concept of computing itself was built on the basis of classical physics, with Alan Turing’s own ‘universal computing machine’ (a mathematical machine that can compute any computable programme) being classical in nature. So Deutsch went back to the drawing board, and developed a quantum generalization of the Turing machine. The result was his universal quantum computer.

But why does it matter whether quantum or classical laws form the foundation of a computer? Put simply, both quantum and classical computers work by taking an input, performing a function on said input, and returning the result as an output. The input into a classical computer is made up of one or more bits, where each bit can be in either a ‘0’ state or a ‘1’ state. With a single bit, the two possible inputs to a computer are thus the ‘0’ and ‘1’ states themselves, but multiple bits can be combined to make larger inputs. For example, two bits can make four different inputs (00, 01, 10, 11), three bits can make eight different inputs (000, 001, 010, 011, 100, 101, 110, 111), and 300 bits can make 2300 different inputs (i.e., more inputs than there are atoms in the observable universe).

Quantum computers, on the other hand, use qubits instead, which can be in both the ‘0’ state and the ‘1’ state at the same time. Therefore, whilst a classical computer would need to perform a function on the ‘0’ and ‘1’ states in separate steps (i.e., as two separate inputs), a quantum computer can compute the results for both the ‘0’ and ‘1’ inputs simultaneously. In other words, a one-bit classical computer would take twice as long as a one-qubit quantum computer to compute the function on both possible inputs. This idea can also be extended to multiple qubits. For instance, two qubits can simultaneously occupy all four of the input states that two classical bits can form, and so a two-qubit quantum computer can do in one step what a two-bit classical computer could only do in four. Similarly, a three-qubit computer can act on eight states simultaneously, and a 300-bit quantum computer can act on 2300 inputs simultaneously. This (quantum mechanical) ability to perform a computational step on multiple input states simultaneously is known as ‘quantum parallelism’, and is at the heart of the speed advantage that quantum computers can offer.

3D render of qubit
Quantum computers use qubits which can be in both the ‘0’ state and the ‘1’ state at the same time. Whilst a classical computer would need to perform a function on the ‘0’ and ‘1’ states in separate steps (i.e., as two separate inputs), a quantum computer can compute the results for both the ‘0’ and ‘1’ inputs simultaneously.

Quantum parallelism is not the whole story however, because even though a quantum computer can compute all of this information simultaneously, you can only actually find out one of the results each time the computation is done. Remember that multi-state quantum systems transition to single state systems when measured, and so all the information about the other states is lost. In other words, if you use a quantum computer like a classical computer, then you might as well just use the classical computer to begin with!

But what if, instead of wanting to know each individual result of the function acting on each individual input, you wanted to know some global property of all the calculated results. For instance, consider the case where the input is a piece of a jigsaw puzzle, and the output is that piece’s position within the jigsaw puzzle as a whole. You’re not going to be interested in each individual result, but rather the sum total of the results (i.e., the completed jigsaw puzzle picture). So if there was some way to use all of the results in a computable problem to calculate a global property of the system (i.e., the picture on the jigsaw puzzle) that could give you the answer you wanted in a single measurement, then maybe quantum computers would be useful after all.

In his 1985 paper, Deutsch not only formulated the idea of a quantum computer, but also gave an example of exactly this. The problem being solved was determining whether a function that could act on one of two inputs was constant or balanced. In other words, did the function always return either a ‘0’ or a ‘1’ regardless of whether there was a ‘0’ or ‘1’ input (a constant function), or did it return a ‘0’ for one of the inputs and a ‘1’ for the other input (a balanced function). In the classical case, the answer could only be determined by inputting both the ‘0’ and ‘1’ inputs into the function. I.e., performing the function twice. Deutsch, however, was able to show that a quantum computer could obtain the answer after evaluating the function only once!

In fairness, there were some caveats to ‘Deutsch’s algorithm’. Namely, it only worked for a maximum of two inputs, and only resulted in a definitive answer 50% of the time. But both of these problems would be solved seven years later when Deutsch and Richard Jozsa created the Deutsch-Jozsa algorithm in 1992. This revised version of Deutsch’s algorithm, while of little practical importance, represented one of the earliest examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. In other words, it proved that a quantum computer could perform algorithmic processes for certain tasks faster than was possible on its classical equivalent, a concept that is now termed ‘quantum supremacy’.

But Deutsch wasn’t done with quantum computation there, and published another paper in 1989 in which he developed the first universal gate. In general, a universal gate is any gate that can be used a finite number of times to produce any other operation that is possible on a set of (bit/qubit) inputs. For example, in classical computation, the Toffoli gate (a three-bit reversible gate developed by Toffoli in 1981) can be used to reproduce any operation that can be performed on a Boolean algebraic logic circuit. Deutsch was able to extend this idea to quantum computation by showing that the Deutsch gate (a controlled-controlled-unitary gate) could be used to reproduce all n-bit quantum gates. Further, he showed that the Deutsch gate could also reproduce the Toffoli gate itself, proving that this single gate could be used to reproduce any classical or quantum operation to an arbitrary level of precision.

Proving the multiverse of madness?

With just the three papers discussed above, Deutsch was able to lay some of the most important groundwork for the second quantum revolution, just as Dirac had done for the first quantum revolution over 50 years prior. And yet Deutsch’s main interest in the real-world construction of a quantum computer seems to be less about what it could do, and more about why it would be able to do it. Specifically, computers perform a physical process when they make a computation, requiring physical resources. If a 300-qubit quantum computer were to be built, then the operations performed on this computer could conceivably use more resources than appear to be available in the entire observable universe. So where do these resources come from? Deutsch believes that the answer lies in the MWI of quantum mechanics.

As a recap, the MWI postulates that there is a multiverse containing different universes for every possible state of every quantum system that has ever existed. In this interpretation, rather than a qubit existing in two states at once, it instead exists in one of the two states in each of two respective universes, with the interaction between these two universes causing the strange ‘multi-state’ quantum phenomena that we observe. Using this interpretation then, rather than a single quantum computer (the one in our universe) calculating a one-qubit function for both input states simultaneously, it is in fact two quantum computers in two different universes that each do half the calculation. Extrapolating this to a quantum computer computing an n-qubit function, each operation that is computed would involve 2n quantum computers across 2n universes, each one calculating the result for just one of the 2n input states. In this way, each quantum computer would essentially be doing the same calculation as a classical computer (i.e., computing a function on a single input to get a single output), and so it is not hard to see how the collective resources of all of the universes would be able to carry out the collective calculation.

Quantum Computer 3D Render (Split)
The MWI postulates that there is a multiverse containing different universes for every possible state of every quantum system that has ever existed. Using this interpretation, rather than a single quantum computer (the one in our universe) calculating a one-qubit function for both input states simultaneously, it is in fact two quantum computers in two different universes that each do half the calculation.

Deutsch believes that there is no other interpretation of quantum mechanics that can answer this question as well as the MWI, specifically stating in his 1985 paper that quantum computer properties such as quantum parallelism place “an intolerable strain on all interpretations of quantum theory other than Everett’s” (referring to the MWI). So according to Deutsch, if a sufficiently powerful quantum computer is developed, and does operate as theory predicts, it would be very compelling evidence for the MWI. Or at the very least, it might force physicists to confront the weirdness of quantum mechanics more directly, and come up with alternative explanations.

Reconstructing physics

These days, Deutsch is content to step back and let the engineers figure out how to bring his quantum computer into reality. In the meantime, he is instead working with Dr Chiara Marletto on a new theory that could potentially subsume quantum computation and the quantum mechanical theory from which it springs. This new theory, known as constructor theory, aims to provide a new approach to formulating the fundamental laws of physics. In other words, constructor theory aims to change the underlying foundation of physics rather than the physical laws themselves, much like if you were to change the language in which a law book is written. The laws themselves remain the same, but the key point being that there might be certain concepts that can be better expressed in one or the other of the languages. Even more intriguingly, the new language might encapsulate new concepts that lead to new laws.

Currently, most of physics is explained in terms of dynamical laws. In other words, if you have a system with a certain set of initial conditions, there will be a law which will tell you how that system will (or, at least, how it is likely to) evolve over time. But there are certain things that this formulation of physics fails to explain (or fails to explain very well anyway). The interaction of quantum systems with gravity is one example. Einstein’s general relativity theory specifies that spacetime is curved by mass, but a quantum system with some mass may be in two or more positions simultaneously, breaking the structure of general relativity. A somewhat more abstract example is life itself. At some point, the universe went from containing just inert matter, to containing living things capable of highly accurate and reliable self-replication (i.e., one cell becoming two). Explaining this transition in terms of particles obeying the laws of motion would be incredibly difficult. 

Mulitverse Concept-1
Constructor theory aims to change the underlying foundation of physics rather than the physical laws themselves, much like if you were to change the language in which a law book is written.

Constructor theory takes a different approach, seeking instead to formulate physics based on the question ‘what tasks are possible, what are impossible, and why’. More specifically, the ‘what tasks are possible/impossible’ part would redefine physics in terms of a set of counterfactual statements, which specify what can and can’t be done. The ‘why’ part would then be about explaining why that set of counterfactual statements best expresses what we know about physical reality. It should be noted of course that physics already includes counterfactual statements, such as ‘energy in a closed system cannot be created or destroyed’ and ‘the speed of light is fixed’. But rather than these principles appearing because of the dynamical laws, constructor theory is seeking to use these statements as the very foundation of physics, and then build everything else on top.

One example of the theories use so far is in the field of quantum gravity. Whilst constructor theory does not itself provide a method for unifying the theories of quantum mechanics and gravity, it’s principles have been used to devise an experiment that could test whether gravity has quantum properties. This test involves two quantum masses which only interact with each other through gravity. If these two quantum masses entangle (interact) through gravity, then constructor theory heavily implies that gravity must be quantum. Specifically, a constructor theoretic principle called ‘interoperability’ implies that if entanglement can be generated in a medium (i.e., via gravity), then that medium must itself be quantum. In this way, constructor theory could point physicists in the right direction in the quest to unify quantum mechanics and gravity.

Whether or not constructor theory ultimately proves successful remains to be seen. But Deutsch himself believes in it, and you certainly can’t fault his academic intuition up to this point. In fact, it is precisely the ability to think differently that allowed him to do his ground-breaking research in quantum computation, and so it will be interesting to see where Constructor theory can be taken in the coming years.