1 00:00:02,500 --> 00:00:18,810 I have. So I'm going to be talking about a problem that sits sort of at the intersection of quantum physics, 2 00:00:19,830 --> 00:00:27,420 computer science and mathematics, which is basically how do we actually go about proving that quantum computing is actually a thing? 3 00:00:28,290 --> 00:00:37,170 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. 4 00:00:37,830 --> 00:00:41,160 And yes, that will be the two of you then. 5 00:00:43,950 --> 00:00:47,190 Yeah. And the one of the. You were quicker, I think, behind you. 6 00:00:47,730 --> 00:00:52,000 Yeah. Sorry. Right. Some chalk. 7 00:00:52,200 --> 00:01:04,420 There we go. So this is a list of words. 8 00:01:06,940 --> 00:01:13,360 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. 9 00:01:13,810 --> 00:01:17,800 Okay. Just point. Yeah. Ah. Just shout when you find it. 10 00:01:18,070 --> 00:01:21,190 Okay. All right. Here we go. One, two, three. 11 00:01:21,220 --> 00:01:24,740 Go. Got it right. 12 00:01:25,330 --> 00:01:29,810 I think you were a bit quicker. Let's try the second one. 13 00:01:35,050 --> 00:01:39,100 Ready. One, two, three. Go! Jesus. 14 00:01:41,610 --> 00:01:47,620 Really? Yup. Got it right. 15 00:01:48,190 --> 00:01:55,340 Let's try that again. Ready. 16 00:01:56,510 --> 00:02:26,820 One, two, three, go. Well, if you're not quick, he's going to beat you. 17 00:02:33,500 --> 00:02:37,640 Got it. Yep. Okay, he's got it. He was quicker. 18 00:02:38,780 --> 00:02:43,650 It was. It's. I think it's in the back here somewhere. So thank you very much. 19 00:02:43,670 --> 00:02:49,360 Can we have a round of applause? You can make your way back. 20 00:02:54,180 --> 00:03:03,870 So I should say that I stacked the deck in Francis's advantage a little bit 21 00:03:04,410 --> 00:03:12,480 because these were actually unsorted lists and these were alphabetised ones. 22 00:03:14,100 --> 00:03:23,160 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. 23 00:03:24,000 --> 00:03:28,170 Whereas with this list, you can actually start searching in the middle, right? 24 00:03:28,170 --> 00:03:32,129 You open it up in the middle, you say, okay, I'm going for Quantum. 25 00:03:32,130 --> 00:03:35,670 So that's a queue. So go to the second half, etc. Right. 26 00:03:35,670 --> 00:03:44,880 So the way that you approach this problem depends entirely on how it's structured and that's a general feature of problem solving. 27 00:03:45,480 --> 00:03:57,510 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. 28 00:03:57,900 --> 00:04:02,040 You have no no other option than just to start at the top and work your way down. 29 00:04:02,790 --> 00:04:08,640 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. 30 00:04:10,310 --> 00:04:16,310 Now you might ask yourself, what happens if one of the two of them reads much faster than the other one? 31 00:04:16,910 --> 00:04:18,800 Well, then the answer is very simple. 32 00:04:19,430 --> 00:04:28,520 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. 33 00:04:29,000 --> 00:04:36,559 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, 34 00:04:36,560 --> 00:04:46,540 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. 35 00:04:47,530 --> 00:04:52,330 And this turns out to be a very fundamental fact about how algorithms work, 36 00:04:52,900 --> 00:05:00,790 which is that scaling is the way to see what a good strategy is through all of the trivial details. 37 00:05:02,610 --> 00:05:06,520 So that brings me to my first recap of what you have. 38 00:05:06,960 --> 00:05:08,370 What I have told you so far, 39 00:05:08,940 --> 00:05:17,420 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. 40 00:05:17,430 --> 00:05:20,759 So in this case, with what kind of scaling in the length of the list. 41 00:05:20,760 --> 00:05:31,430 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? 42 00:05:32,150 --> 00:05:36,590 Because as we all know, there are very many different kinds of computing technologies. 43 00:05:37,010 --> 00:05:41,749 So this is a very this is actually Babbage's analytical engine. 44 00:05:41,750 --> 00:05:45,170 So this is a mechanical computer, a very early proposal. 45 00:05:45,500 --> 00:05:49,250 This is ENIAC, one of the world's first electronic computers. 46 00:05:49,610 --> 00:05:51,500 Well, I guess we are all familiar with this. 47 00:05:52,760 --> 00:06:00,890 And a very natural question to ask yourself is, does it matter for this kind of scaling, which kind of computer I use? 48 00:06:01,760 --> 00:06:06,320 And the answer that you get back from a computer scientist, if you ask him this question, is no. 49 00:06:06,860 --> 00:06:11,780 And that negative answer goes under the name of the church Turing thesis. 50 00:06:12,560 --> 00:06:19,550 And basically, if you want to state this formally, what you do is you introduce this kind of machine, 51 00:06:20,120 --> 00:06:22,760 which is a kind of generalised computer, and then you, 52 00:06:22,940 --> 00:06:29,900 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. 53 00:06:30,710 --> 00:06:40,010 And then you say this machine can efficiently simulate any realistic model of computation, which basically boils down to all computers are the same. 54 00:06:43,920 --> 00:06:48,060 And so why do you need to extend the church during theses in your life? 55 00:06:48,660 --> 00:06:57,060 The reason is that this is the thing that makes the mathematics of problem solving, which goes into the name of complexity theory. 56 00:06:57,450 --> 00:07:05,519 It's the idea that makes that bit of mathematics make sense because if it mattered what computer you would solve it on, 57 00:07:05,520 --> 00:07:11,190 you could never be able to make an abstract statement about which problems are hard and which problems are easy. 58 00:07:12,480 --> 00:07:16,800 So this is the thing that causes this entire field to make sense in the first place. 59 00:07:18,690 --> 00:07:24,490 Right now we're going to bring in the quantum because that is, after all, the thing that you all came for. 60 00:07:25,380 --> 00:07:32,190 So it turns out. And this by now, you should understand how incredibly strange and surprising this is. 61 00:07:32,730 --> 00:07:38,670 But it turns out that you can search an unstructured database on unstructured list, 62 00:07:39,210 --> 00:07:45,180 not in any steps, but in square root and steps if you use quantum mechanics. 63 00:07:46,680 --> 00:07:55,140 And that is very, very, very surprising. And that basically causes everything that I told you up to now to collapse, essentially. 64 00:07:56,490 --> 00:08:04,410 So we are left with this kind of three way contradiction that is known as Shaw's trilemma, 65 00:08:05,310 --> 00:08:09,540 which basically works like in like an Escher impossible triangle. 66 00:08:09,570 --> 00:08:11,880 Two of the three sides can make sense. 67 00:08:12,690 --> 00:08:20,310 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. 68 00:08:20,610 --> 00:08:22,050 It can't make sense. 69 00:08:23,070 --> 00:08:32,280 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. 70 00:08:33,270 --> 00:08:39,210 Or we have somehow completely misunderstood how to classify the darkness of computing problems. 71 00:08:41,590 --> 00:08:47,960 So I also want to stress that none of this hinges on us actually building a quantum computer. 72 00:08:47,980 --> 00:08:51,550 This is entirely a theoretical problem. 73 00:08:52,530 --> 00:09:02,239 So. Merely having the idea of a quantum computer already causes this problem to appear, and it has deep implications in computer science, 74 00:09:02,240 --> 00:09:09,230 physics and complexity theory because it one of the founding statements of one of these three fields has to be incorrect. 75 00:09:10,420 --> 00:09:13,510 And this is a problem that is fortunately amenable. 76 00:09:13,810 --> 00:09:17,050 And this is what makes it really interesting for me as an experimental physicist. 77 00:09:17,410 --> 00:09:21,930 It's a problem that is amenable to experiment, to experimental investigation. 78 00:09:21,940 --> 00:09:29,250 So you can do an experiment where you can test this. So how do you go about solving this trilemma? 79 00:09:30,120 --> 00:09:33,720 You basically go and look for the simplest physical way. 80 00:09:35,200 --> 00:09:43,240 That you can build, that you can encode a problem in some machine that gets way easier when you use quantum mechanics. 81 00:09:44,250 --> 00:09:47,640 Then you build that machine. You see, if it really goes faster. 82 00:09:48,240 --> 00:09:56,580 And then you do you do this thing that we did here where you basically get rid of all the trivial details by 83 00:09:56,580 --> 00:10:02,640 making the problem bigger and bigger so that you only you're only left with the interesting scaling at the end, 84 00:10:02,670 --> 00:10:09,530 just like we did earlier. Yes. 85 00:10:10,250 --> 00:10:18,829 There we go. So it turns out that the simplest possible problem that you can implement involves photons. 86 00:10:18,830 --> 00:10:27,310 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, 87 00:10:27,610 --> 00:10:34,370 for example, out of the window of a car or a train, you see this reflection of yourself. 88 00:10:34,390 --> 00:10:42,400 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. 89 00:10:42,400 --> 00:10:46,180 It comes back. And so you see kind of two images here. 90 00:10:46,180 --> 00:10:51,010 You see the outside world and you see or you see yourself. 91 00:10:53,060 --> 00:11:00,350 And it turns out that you can engineer this into a thing that lets 50% of the light through and. 92 00:11:02,130 --> 00:11:05,940 Reflects the other half, which is known as a beam splitter. 93 00:11:06,570 --> 00:11:09,330 You can just buy these things that are actually not very expensive. 94 00:11:10,140 --> 00:11:18,750 And now if you send a single photon on either side of this beam splitter, something very interesting happens. 95 00:11:21,190 --> 00:11:26,579 Which is that. The two photons clumped together. 96 00:11:26,580 --> 00:11:30,680 They bunched together. So this photo comes in from this side dish. 97 00:11:30,720 --> 00:11:36,250 So the red circles are the photons, right? So. Comes in from this side, the other one comes in from that side. 98 00:11:36,610 --> 00:11:44,020 Then there's four possible scenarios, but it turns out that these two in the middle are never actually observed in nature. 99 00:11:44,560 --> 00:11:54,590 So you either get this one or you get that one. And interestingly enough, if you can cut an eight this problem. 100 00:11:54,980 --> 00:12:00,320 So if you put a whole bunch of these beam splitters after each other and you feed them with photons, 101 00:12:01,310 --> 00:12:06,350 then that turns out to implement precisely the kind of problem that we are looking for, 102 00:12:06,710 --> 00:12:12,710 namely one that is easy for a quantum machine, but hard for a classical computer. 103 00:12:14,950 --> 00:12:19,990 And so that goes. Doing that experiment goes under the name of both and sampling. 104 00:12:20,560 --> 00:12:27,610 So this is basically nothing more than this concatenated network of beam splitters. 105 00:12:27,880 --> 00:12:32,770 So here they are represented as little channels where the light goes through. 106 00:12:32,770 --> 00:12:37,479 And at one of these crossings, light has the opportunity to jump from one channel to the other. 107 00:12:37,480 --> 00:12:41,280 So this implements this 5050 splitting. 108 00:12:42,130 --> 00:12:49,000 You send in the photons in some arbitrarily chosen bunch of these of of these channels. 109 00:12:49,630 --> 00:12:53,190 And your task is to guess where they will come out. 110 00:12:55,880 --> 00:13:04,040 And this machine is kind of a strange computer because like everything in the world, it's a computer that mostly computes itself. 111 00:13:05,620 --> 00:13:14,080 So what happens is this Boston sampler, you're just the problem that you're trying to solve is what would this machine do? 112 00:13:14,990 --> 00:13:18,260 Right. And of course, every machine is a simulation of itself. 113 00:13:18,260 --> 00:13:22,850 So the motion sensor to simulate self, the classical computer has to keep up. 114 00:13:23,270 --> 00:13:29,120 And as I said, as you make the problem bigger and bigger in this case, that means putting in more and more photons. 115 00:13:29,420 --> 00:13:32,750 It gets harder and harder for the classical computer to do so. 116 00:13:34,970 --> 00:13:42,230 So then how big is big enough? State of the art at the moment is about five photons and about ten of these channels. 117 00:13:42,860 --> 00:13:46,550 And we need to go to about 50 photons or 50 particles of light. 118 00:13:47,060 --> 00:13:51,560 And about two and a half thousand channels. 119 00:13:54,080 --> 00:14:00,590 And so I want to stress that this boson sampling machine is not a universal quantum computer. 120 00:14:00,590 --> 00:14:05,870 So it's not programmable and it doesn't solve any problem that has any practical purpose. 121 00:14:06,350 --> 00:14:09,170 So it's purely meant. So it's a little bit. 122 00:14:09,990 --> 00:14:19,620 You can kind of compare a Boston sampling machine versus a universal quantum computer to, let's say, one of these things. 123 00:14:20,280 --> 00:14:23,550 I hope that there are people in the audience who remember what these things are. 124 00:14:23,910 --> 00:14:29,940 This is an old adding machine where you typed in two numbers and you pull the crank and you typed in a number, 125 00:14:29,940 --> 00:14:33,870 and then you pulled the crank again, and then it would add the two numbers for you. 126 00:14:34,350 --> 00:14:38,760 So this is a computer of of sorts. But you can program it. 127 00:14:39,000 --> 00:14:45,630 You can tell it to run windows. Windows for you write it does one thing and that's the thing that it does. 128 00:14:46,410 --> 00:14:48,299 And the Boston sampler is pretty much the same. 129 00:14:48,300 --> 00:14:57,270 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. 130 00:14:57,600 --> 00:15:10,750 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 131 00:15:11,110 --> 00:15:17,050 that you might see in your tour that you have either already done or are going to do. 132 00:15:17,620 --> 00:15:28,990 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. 133 00:15:29,830 --> 00:15:33,070 And so you need a bunch of experimental equipment to get this to work. 134 00:15:33,700 --> 00:15:37,330 One of them is a photon source, which you see here. 135 00:15:38,080 --> 00:15:41,230 So light comes in from the side. Laser light. 136 00:15:41,950 --> 00:15:50,589 This metal cylinder here is actually a microscope objective which focuses the light down into this crystal here, 137 00:15:50,590 --> 00:15:54,130 this white thing, which is where single photons are produced. 138 00:15:54,940 --> 00:16:00,370 And then there is another microscope objective that takes the photons out into the rest of the experiment. 139 00:16:02,530 --> 00:16:10,650 This is the network. So this is this middle bit. What you see here are three layers of beam splitters. 140 00:16:11,040 --> 00:16:19,470 So each one of these slabs here is a little chip where we have written little guides that the light can follow. 141 00:16:19,830 --> 00:16:25,740 So this is basically like a switchyard for light. So this thing here and you see here. 142 00:16:26,740 --> 00:16:29,380 You can see some some lines running that way. 143 00:16:29,740 --> 00:16:38,140 Those are the optical fibres which carry the photons from the place where they are generated to the place where this interference happens. 144 00:16:40,140 --> 00:16:46,650 And then finally there are the Photodetectors because of course, having generated the photons, you also have to have the ability to see them. 145 00:16:47,310 --> 00:16:51,540 So you can see here, you can see the photon detectors. 146 00:16:54,310 --> 00:16:58,450 But here is a box where the photons come in. There's fibres that go into this thing. 147 00:16:59,880 --> 00:17:03,690 Photons go up in here. They're detected. 148 00:17:03,690 --> 00:17:07,650 And the electrical signal goes out here to our computer, which runs the search detection event. 149 00:17:11,420 --> 00:17:22,700 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, 150 00:17:22,700 --> 00:17:26,330 that Dan that personally has my research interest. 151 00:17:26,930 --> 00:17:30,770 And that is not to say that there isn't a whole lot else going on here. 152 00:17:30,800 --> 00:17:36,800 So I would say enjoy the opportunity to walk around, look around, ask questions. 153 00:17:37,160 --> 00:17:41,270 And there's lots of interesting stuff going on here. And with that, I would like to conclude. 154 00:17:41,270 --> 00:17:41,960 Thank you very much.