00:00:00.000 David Quantum Computing is becoming quite important in the world to no small degree based on your personal contributions.

00:00:07.000 I'm not so interested on the applications, can we factor large numbers and steal money through bank transactions or catch spies?

00:00:16.000 But what it is, fundamentally, and what it possibly can tell us about the nature of reality.

00:00:23.000 That's really why I'm interested in it as well. I came to this from a physics point of view, not a computation point of view.

00:00:33.000 So, one of the things that really attracts me about the theory of quantum computation is what it tells us about what kind of thing a law of physics is.

00:00:47.000 It's been a mystery to philosophers and physicists for decades, what I think Eugene Wigner called, the unreasonable effectiveness of mathematics in the natural sciences.

00:01:01.000 Especially when we realize that the set of computable functions, which are familiar to us, the made of things like addition and multiplication and so on, from a mathematicians point of view,

00:01:14.000 they form an infinitesimally tiny subset of the set of all possible mathematical relationships, and yet physics is made entirely out of those.

00:01:25.000 And if it weren't, we wouldn't be able to know any physics.

00:01:30.000 So, when it became more and more obvious that computation is built into the laws of physics at a fundamental level,

00:01:42.000 a lot of people immediately jump to the conclusion, oh well, the reason that mathematics is useful in the physical sciences is that the world is a computer.

00:01:51.000 And we are just programs running in that computer or something like that, or we are just a simulation running in a computer.

00:01:58.000 So, it seems to me that that misses the whole point of the lesson of the universality of computation for physics, because it requires a notion of what is or isn't computable that is outside the physical world, so that it was set by God or something to be a certain set, and that's why our universe only instantiates that set of mathematical relationships.

00:02:25.000 Well, then you may, that doesn't solve the problem. You may as well have said that God set up just our universe with those relationships.

00:02:32.000 The middle man.

00:02:33.000 Yes, get out, remove the middle man.

00:02:35.000 So, I think the real important lesson of quantum of the universality of computation as revealed by quantum computers to be part of physics is that computers can be built, universal computers can be built within the universe.

00:02:53.000 That is really the amazing thing, because however the universe was, you could imagine some kind of super computer with unknown mathematics that simulated it.

00:03:04.000 But the amazing thing about our universe is that you can make an object, such a computer that can simulate any physical process, that's what universality is.

00:03:15.000 And this object, the set of all its possible motions, that is the set of all possible programs that could be programmed into it, is in one one correspondence with the set of all possible motions of anything.

00:03:30.000 And that is telling us something about the universe from the inside. It's telling us something about what laws of nature actually are.

00:03:41.000 Okay, now how does the quantum part help us?

00:03:46.000 When the theory of computation was first discovered by Babbage and then developed by Alan Turing during the 1930s, it wasn't realized that this was a branch of physics at all.

00:03:59.000 It was invented as a branch of mathematics to study mathematical proofs. And the theory was built up from a conjecture that a certain type of abstract object, the Turing machine, could represent all things that could be computations.

00:04:23.000 What quantum computers, and then, historically, what happened after that, is that people began to worry that the physical world might not be able to instantiate these operations perfectly.

00:04:38.000 And therefore the real world might be a weaker kind of computer than the Turing computer, that it might be an idealization.

00:04:46.000 Now when we studied this more carefully, and this is where quantum computers began to come in, we found that not only can a universal computer exist physically, but it's more powerful than a Turing machine.

00:05:00.000 And what the mathematicians were doing unconsciously is that when they invented these abstract objects, they were applying their intuition about physical objects.

00:05:12.000 They know that that's what they were doing. And because they were applying their intuition about physical objects, they got it wrong.

00:05:19.000 They thought about computing, making marks of squares of paper, and then as Feynman remarked, they thought they understood paper.

00:05:29.000 But in fact, paper like everything else obeys quantum mechanics, and the real computation in the world is quantum computation.

00:05:36.000 The theory of computation is the theory of quantum computation, and that is a theory of physics. So that means that the theory of computation is irretrievably within physics because of the quantum theory of computation.

00:05:49.000 Now what is briefly the quantum theory of computation? How does that work? How is computation and quantum theory quantum mechanics integrated into a quantum theory of computation?

00:06:02.000 The theory of computation within any laws of physics is the theory of how you can use physical objects to represent abstract objects.

00:06:13.000 So you want to represent the integers one, two, three, and you can use physical objects like fingers to say that will be one, that's called two, that's called three, and so on.

00:06:23.000 And the computers are ways of instantiating abstract objects and their relationships in physical objects and their motion.

00:06:35.000 Now what happens with quantum computers is that we simply take the deepest physical theory, we have quantum theory, and we say what kind of information processing does quantum theory in general allow, and what does it not allow, and that's the theory of quantum computation.

00:06:51.000 And when you do that, what do you find compared with a classical computer when you make this quantum computer?

00:06:59.000 You find a number of similarities, and we find the reasons why the Turing theory worked as well as it did, and then you find a number of dramatic differences between the quantum computers and classical computers.

00:07:17.000 One that's got the most attention is that for certain types of calculation, quantum computer can perform it exponentially faster than any classical computer.

00:07:29.000 So you could have, people haven't built quantum computers yet, but we hope that they soon will.

00:07:34.000 And when a quantum computer is built, a small quantum computer with a few thousand qubits, that's the quantum analog of bits.

00:07:43.000 Compared to the billions of bits in our normal desktop, you know, or even our mobile phones.

00:07:49.000 In other words, a very, very weak, comparatively weak quantum computer could perform more computations simultaneously than could be performed by the entire visible universe if it was all made into computers.

00:08:03.000 In fact, when I say more, that's an understatement, it exponentially more than that.

00:08:08.000 But only for certain types of computation, and that's a token of the fact that the whole notion of computation is different in quantum computers.

00:08:18.000 It's not that, like with all classical computers, you can say that one computer is ten times as fast as the other.

00:08:24.000 With quantum computers, they are vastly faster than classical computers for some more computations, and the same for others.

00:08:32.000 And interestingly, they're not slower for any computations, because a quantum computer among its abilities is to simulate a classical computer.