I have. So I'm going to be talking about a problem that sits sort of at the intersection of quantum physics, computer science and mathematics, which is basically how do we actually go about proving that quantum computing is actually a thing? And to explain to you how we do that, I'm going to start with a small demonstration for which I need to volunteers from the audience. And yes, that will be the two of you then. Yeah. And the one of the. You were quicker, I think, behind you.
Yeah. Sorry. Right. Some chalk. There we go. So this is a list of words. And when I say when I say go, I want you to turn it over and try and find the word quantum as quickly as possible. Okay. Just point. Yeah. Ah. Just shout when you find it. Okay. All right. Here we go. One, two, three. Go. Got it right. I think you were a bit quicker. Let's try the second one. Ready. One, two, three. Go! Jesus. Really? Yup. Got it right. Let's try that again. Ready.
One, two, three, go. Well, if you're not quick, he's going to beat you. Got it. Yep. Okay, he's got it. He was quicker. It was. It's. I think it's in the back here somewhere. So thank you very much. Can we have a round of applause? You can make your way back. So I should say that I stacked the deck in Francis's advantage a little bit because these were actually unsorted lists and these were alphabetised ones.
So you notice that, especially in the last one, Victor had no choice but to just start reading at the top and make his way down. Whereas with this list, you can actually start searching in the middle, right? You open it up in the middle, you say, okay, I'm going for Quantum. So that's a queue. So go to the second half, etc. Right. So the way that you approach this problem depends entirely on how it's structured and that's a general feature of problem solving.
So if you think that this pile of books represents your list that you want to search through, then for an alphabetised list, you have nothing. You have no no other option than just to start at the top and work your way down. Whereas for the sorted lists you can start in the middle and do this kind of divide and conquer approach, which is of course much faster. Now you might ask yourself, what happens if one of the two of them reads much faster than the other one?
Well, then the answer is very simple. You just make the list longer, because if I make the list twice as long, then the guy who gets the unsorted list has to read for twice as long. Whereas the guy who gets the sorted list only needs to do one extra search step because once he halves the list down the middle, it's as long as he started with. So for any reading speed, I can make the structured search win by just making the list big enough.
And this turns out to be a very fundamental fact about how algorithms work, which is that scaling is the way to see what a good strategy is through all of the trivial details. So that brings me to my first recap of what you have. What I have told you so far, the structure of a problem dictates how fast you can solve it and how fast means with what kind of scaling in the size of the problem. So in this case, with what kind of scaling in the length of the list.
But that can be anything reading. So then a very natural question to ask is, is it also allowed to depend on the make of the computer? Because as we all know, there are very many different kinds of computing technologies. So this is a very this is actually Babbage's analytical engine. So this is a mechanical computer, a very early proposal. This is ENIAC, one of the world's first electronic computers. Well, I guess we are all familiar with this.
And a very natural question to ask yourself is, does it matter for this kind of scaling, which kind of computer I use? And the answer that you get back from a computer scientist, if you ask him this question, is no. And that negative answer goes under the name of the church Turing thesis.
And basically, if you want to state this formally, what you do is you introduce this kind of machine, which is a kind of generalised computer, and then you, which is called a Turing machine, you prove that this is equivalent to each of these computers and therefore they're all equivalent to each other. And then you say this machine can efficiently simulate any realistic model of computation, which basically boils down to all computers are the same.
And so why do you need to extend the church during theses in your life? The reason is that this is the thing that makes the mathematics of problem solving, which goes into the name of complexity theory. It's the idea that makes that bit of mathematics make sense because if it mattered what computer you would solve it on, you could never be able to make an abstract statement about which problems are hard and which problems are easy.
So this is the thing that causes this entire field to make sense in the first place. Right now we're going to bring in the quantum because that is, after all, the thing that you all came for. So it turns out. And this by now, you should understand how incredibly strange and surprising this is. But it turns out that you can search an unstructured database on unstructured list, not in any steps, but in square root and steps if you use quantum mechanics.
And that is very, very, very surprising. And that basically causes everything that I told you up to now to collapse, essentially. So we are left with this kind of three way contradiction that is known as Shaw's trilemma, which basically works like in like an Escher impossible triangle. Two of the three sides can make sense. But then when you when you've decided which of the two, which of the two sides have to make sense, then the third side pops out of the page. It can't make sense.
And so the three sites are either to extend the church during theses has to be wrong or we have somehow misunderstood how quantum mechanics works. Or we have somehow completely misunderstood how to classify the darkness of computing problems. So I also want to stress that none of this hinges on us actually building a quantum computer. This is entirely a theoretical problem.
So. Merely having the idea of a quantum computer already causes this problem to appear, and it has deep implications in computer science, physics and complexity theory because it one of the founding statements of one of these three fields has to be incorrect. And this is a problem that is fortunately amenable. And this is what makes it really interesting for me as an experimental physicist. It's a problem that is amenable to experiment, to experimental investigation.
So you can do an experiment where you can test this. So how do you go about solving this trilemma? You basically go and look for the simplest physical way. That you can build, that you can encode a problem in some machine that gets way easier when you use quantum mechanics. Then you build that machine. You see, if it really goes faster.
And then you do you do this thing that we did here where you basically get rid of all the trivial details by making the problem bigger and bigger so that you only you're only left with the interesting scaling at the end, just like we did earlier. Yes. There we go. So it turns out that the simplest possible problem that you can implement involves photons.
So particles of light. And you have probably all seen on a dark evening when you're looking out of the window or when you're looking, for example, out of the window of a car or a train, you see this reflection of yourself. Right. And the reason why you see this is because when you have a plate of glass, a little bit of the light that falls on it is actually reflected. It comes back. And so you see kind of two images here. You see the outside world and you see or you see yourself.
And it turns out that you can engineer this into a thing that lets 50% of the light through and. Reflects the other half, which is known as a beam splitter. You can just buy these things that are actually not very expensive. And now if you send a single photon on either side of this beam splitter, something very interesting happens. Which is that. The two photons clumped together. They bunched together. So this photo comes in from this side dish.
So the red circles are the photons, right? So. Comes in from this side, the other one comes in from that side. Then there's four possible scenarios, but it turns out that these two in the middle are never actually observed in nature. So you either get this one or you get that one. And interestingly enough, if you can cut an eight this problem.
So if you put a whole bunch of these beam splitters after each other and you feed them with photons, then that turns out to implement precisely the kind of problem that we are looking for, namely one that is easy for a quantum machine, but hard for a classical computer. And so that goes. Doing that experiment goes under the name of both and sampling. So this is basically nothing more than this concatenated network of beam splitters.
So here they are represented as little channels where the light goes through. And at one of these crossings, light has the opportunity to jump from one channel to the other. So this implements this 5050 splitting. You send in the photons in some arbitrarily chosen bunch of these of of these channels. And your task is to guess where they will come out. And this machine is kind of a strange computer because like everything in the world, it's a computer that mostly computes itself.
So what happens is this Boston sampler, you're just the problem that you're trying to solve is what would this machine do? Right. And of course, every machine is a simulation of itself. So the motion sensor to simulate self, the classical computer has to keep up. And as I said, as you make the problem bigger and bigger in this case, that means putting in more and more photons. It gets harder and harder for the classical computer to do so.
So then how big is big enough? State of the art at the moment is about five photons and about ten of these channels. And we need to go to about 50 photons or 50 particles of light. And about two and a half thousand channels. And so I want to stress that this boson sampling machine is not a universal quantum computer. So it's not programmable and it doesn't solve any problem that has any practical purpose. So it's purely meant. So it's a little bit.
You can kind of compare a Boston sampling machine versus a universal quantum computer to, let's say, one of these things. I hope that there are people in the audience who remember what these things are. This is an old adding machine where you typed in two numbers and you pull the crank and you typed in a number, and then you pulled the crank again, and then it would add the two numbers for you. So this is a computer of of sorts. But you can program it.
You can tell it to run windows. Windows for you write it does one thing and that's the thing that it does. And the Boston sampler is pretty much the same. It just does the one thing that you've built it to do and you can't solve, you can't run programs on it, you can't solve things with it.
So it's entirely a proof of principle apparatus. And then I wanted to conclude by just very briefly showing you a few of the things that you might see in your tour that you have either already done or are going to do. So the tour will take you to some of the experimental labs where work is being done to realise many things, but among them this idea. And so you need a bunch of experimental equipment to get this to work. One of them is a photon source, which you see here.
So light comes in from the side. Laser light. This metal cylinder here is actually a microscope objective which focuses the light down into this crystal here, this white thing, which is where single photons are produced. And then there is another microscope objective that takes the photons out into the rest of the experiment. This is the network. So this is this middle bit. What you see here are three layers of beam splitters.
So each one of these slabs here is a little chip where we have written little guides that the light can follow. So this is basically like a switchyard for light. So this thing here and you see here. You can see some some lines running that way. Those are the optical fibres which carry the photons from the place where they are generated to the place where this interference happens.
And then finally there are the Photodetectors because of course, having generated the photons, you also have to have the ability to see them. So you can see here, you can see the photon detectors. But here is a box where the photons come in. There's fibres that go into this thing. Photons go up in here. They're detected. And the electrical signal goes out here to our computer, which runs the search detection event.
So in conclusion, I want to stress I've presented just a tiny bit of quantum science that goes on here in Oxford that I personally work on, that Dan that personally has my research interest. And that is not to say that there isn't a whole lot else going on here. So I would say enjoy the opportunity to walk around, look around, ask questions. And there's lots of interesting stuff going on here. And with that, I would like to conclude. Thank you very much.