David Deutsch and universal quantum computing
David Deutsch's 1985 paper 'Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer' established the mathematical framework that underlies quantum computing today. Deutsch defined the universal quantum Turing machine, showing that logic operations could be represented as reversible unitary matrices acting on a register of qubits, which is the circuit model still used in quantum algorithms. While Richard Feynman had approached quantum computing from a physical modeling angle at roughly the same time, Deutsch's contribution was formalizing the computational complexity side and building the bridge between algorithm and hardware architecture.
- The 1985 paper was communicated to the Proceedings of the Royal Society by Roger Penrose, who later won the Nobel Prize for proving black holes are a physical reality.
- Deutsch's work was driven by a personal commitment to the many-worlds interpretation of quantum mechanics, which he considers the only valid interpretation.
- As a graduate student at Oxford, Deutsch met Bryce DeWitt, a theoretical physicist who had collaborated with John Wheeler at the Institute for Advanced Studies and who had worked on the many-worlds interpretation.
- Wheeler was the PhD adviser of Hugh Everett, the originator of the many-worlds hypothesis, and kept Everett's ideas alive after Everett was dismissed by Niels Bohr during a visit to Copenhagen.
Transcript
This chapter, from the episode video's captions · 568 words
1:06:26Fineman's keynote address at that conference. Um and as I said, you know, Fineman's keynote address was amazing, but that's not really why we have a trillion dollar ecosystem now. He approached quantum computing from this physical modeling perspective. At the same time, David Deutsch in England, he formalized the mathematics of quantum computational complexity in a 1985 paper, quantum theory and the church Turing principle and the universal quantum computer. Um, if you notice it is communicated by Roger Penrose, fellow of the Royal Society to
1:07:06the proceedings of the Royal Society. So, Roger Penrose is also in this story. um the great mathematician and physicist who won the Nobel Prize for his proof that black holes are definitely a reality. So he shows David Deutsch in this in this paper he defines the universal quantum turing machine. Okay. And that establishes the kind of quantum circuit model that we see today when we when we look at like quantum algorithms and you have like these blocks. We're going to see some of these later on. Um the logic operations are now represented by unitary matrices the the kinds of tofully gates and things like that that we were talking about earlier. Um these
1:07:47are reversible logic gates and they can act on a register of quantum bits or cubits. So this is where he's establishing you know I've got a bit the computer is made out of a bunch of quantum bits. I act on these bits with unitary matrices, unitary transformations and I can start computing things. >> Is this the first building the bridge from this theory and the software of the algorithm to now how that interacts with the the substrate of a hardware? >> Yeah, in some sense it's more like it's taking the building blocks that people had made earlier with the gates and things like that and Fineman saying that you know you've got these two-state
1:08:28systems. He's he's like, I can now build a touring machine that'll do stuff for me. >> The framework of how you would be able to make this actually productive. Yes. These concepts of productive. >> Yeah. Yeah. Exactly. And um side note, Deutsche's academic pursuit is driven by a commitment to the many worlds interpretation of quantum mechanics. He is fanatical about this interpretation. He thinks this is the only way to go. And you know, there's a lot of people that are very smart out there that are saying this is the only way to go. um during his Oxford studies as a graduate student um he met Bryce Dwit who's a very famous theoretical physicist who was a collaborator of John Wheeler at
1:09:09Princeton. I think Dwit was actually at the Institute for Advanced Studies. So he was not at Princeton at the time but he and Wheeler used to talk a lot and Wheeler was the PhD adviser of Hugh Everett who's the guy behind the Everett hypothesis of many worlds. Right? Everett went on to do um Rand and like you know national security apparatus type stuff because he got he got basically shot down by Neils Boore when he went and visited um Copenhagen. But >> Wheeler kept the idea alive of Everettian mechanics. Um Bryce Dit did a few >> things with Wheeler about that many
1:09:50worlds interpretation and they met at a pizza parlor in London.
From How Quantum Computing Actually Works (Part 1)
Part I of our quantum computing deep dive traces the field from Bell and Feynman to Deutsch and Shor—and explains what quantum computers actually do differently from classical machines.