Who is the microphone working? All right. So, so, so thank you so much for inviting me here. Thank you, Leslie, for the unbelievably kind introduction. It's it's an honour to give this lecture and to be here at Oxford, you know, among so many old friends and colleagues and also, you know, at a place that played such a pivotal role in the birth of quantum computing. So when I did a Google image search for quantum computer, this is one of the first things that came up.
So I'm not really sure whether that's what they look like. I mean, it may become apparent in this talk that I am a theorist rather than an engineer. But one of the most interesting things and what I want to tell you about today is that despite being about as far as you can possibly get on the theoretical and of quantum computing, even I am actually talking to the engineers and the experimentalists. And I will tell you something about about why. So so the title of the talk is Quantum Supremacy.
So I should, you know, admit at the outset that it's a little bit of an unfortunate term. It's a term that's come into use. You know, a few years ago, I think it was John Prescott who first started using it, but I don't know.
So, so, so I come from the US. I don't know how many of you here follow the news, but in the US there's a presidential candidate by the name of Trump and he so because of his candidacy, people have actually asked me about whether I will formally disavow quantum supremacy and quantum supremacists.
You know, I when when when Mr. Trump was asked whether he would disavow white supremacy, you probably all know his his his reply was that he needed to research it further when it when it comes to quantum supremacy. I too need to research this further. So but but but in this talk I'll tell you about the research that I have done and that my colleagues have done on this topic. So so what? So what exactly do we mean by do do people mean by this term quantum supremacy?
So so it's a term that's basically just used to refer to a certain task that people are, I would say, racing to achieve right now, which which is to to do some experiment in quantum computation, you know, hopefully with hardware that will be available in the in the near future. So, you know, five years or maybe even less than that which will, you know, not break any cryptography. It will not, you know, factor an enormous number, will not do do anything of any practical use to anyone.
That's still a ways off, but it will do something that, while useless, is nevertheless hard. Okay. Something that we can have some sort of confidence or reason to believe is hot would be hard to simulate using a classical computer for for some meaning of the word hard. Okay. You know, it would take manifestly more time to get the same sort of result using classical computation.
This is a milestone that, you know, despite sort of being claimed, you know, every week or so in the popular press, I would say, has not yet been achieved. But, you know, if we do a fair comparison, that is if we compare quantum computation, you know, not against a just, you know, a a poor classical algorithm, but against the very best classical algorithms that could be designed that can be devised for the same sorts of tasks. Okay. But but it is plausible for reasons.
I'll go into that within a few years. We will have the capability to, to do something with quantum mechanical hardware, you know, which is a well-defined mathematical task, but for which, you know, we could argue that a classical simulation would take a lot longer than then. Than than than than. Then the quantum computation.
I think that this will be a major milestone. This will sort of cast a severe doubt on what we call the extended church Turing thesis, which has been sort of a foundational belief of computer science since the 1960s. And for me personally, you know, this overthrowing this extended church Turing thesis is really, you know, the reason why I got into quantum computing in the first place. Sometimes people ask, well, you know, what is the the biggest application of a of a quantum computer?
Right. And you may have heard of some of them. You know, is that breaking all the cryptography that we use on the Internet today or is it simulating quantum mechanics itself, you know, for designing drugs or designing new materials, which you might say is a more positive application for humanity than, you know, breaking codes and reading people's email. Okay. Or is it optimisation or machine learning?
You know, those are certainly huge application areas, but for those, it's less clear how much advantage a quantum computer would really give us even even if we had one. My my answer to that has always been that, you know, there is one application of quantum computing which is more important to me than any of those, and that is to disprove the people who say that it's impossible. Okay. That's that that that that's why I am in this.
I think that quantum computing is in some sense, the most stringent test of quantum mechanics itself, that, you know, that we maybe that will that we're going to see in our lifetimes.
And, you know, if it is worth building the Large Hadron Collider or worth building Lego, which, you know, are these amazing, wonderful machines that, you know, so far mostly, you know, sort of triumphantly confirm our existing theories, then surely it is worth it to see whether quantum mechanics, you know, still holds in this regime of computational intractability. And, you know, and I, I spend a lot of time, you know, on my blog and elsewhere just arguing against quantum computing sceptics.
And, you know, I would just I would I would just like to see them admit that they were wrong. I'll, I'll, I'll I'll I'll confess to that mode of, you know, of course, you know, if they if they turned out to be right, you know, in some sense, that's that's the even that's even a more exciting outcome to me because that, I think would force a revision in our understanding of physics itself.
If there's really some deep and fundamental reason why you cannot build a quantum computer, then that, you know, we would have to rewrite the textbooks to explain why. Write a believing you can build a quantum computer is just the conservative option. Okay. But, you know.
But either way, I would like to know the truth. Okay, so, so, so so this is, you know, sort of what I've been advocating to the, you know, experimentalists is sort of to disentangle the, so to speak, the question of, you know, what a quantum computer would be practically useful for from the question of just can we demonstrate to everyone satisfaction that we can achieve, you know, a clear quantum speed up at all and just focus on doing the latter first.
Okay. And that just seems like the right order to me. And and I am actually very, you know, because of developments within the last five or six years, I am very optimistic that this clear quantum speed up will be achievable, you know, relatively soon. But there's a lot more that has to happen in terms of engineering, and there is also more that has to happen in terms of theory. Okay. In terms of understanding what is or isn't, hard to simulate using a classical computer and why.
Okay. And so that that's what I'll focus on more in this talk. Okay. So first of all, so what is this extended church Turing thesis that I'm so interested in trying to refute? Well, so the original church Turing thesis was a statement about compute ability.
Okay. And the way that I would interpret it is as a statement that everything that is computable, you know, by any device that you can physically build is also computable by a Turing machine, which is, you know, just a mathematical idealisation of what we mean by a computer. You know, it's not clear that church or Turing themselves ever, you know. White said that. But but in any case, that's what they should have said.
So, you know, I think that, you know, 80 years, you know, after church and touring, you know, this this thesis remains on very solid ground. As a as a as a as a as a statement about our laws of physics. You know, you know, there is maybe, you know, one person who is who has tried to fight it. Sir Roger Penrose, who I guess is also here in Oxford.
But, you know, it is, you know, almost a you could say a backhanded compliment to the church during theses, sort of how hard he has had to work to develop any sort of alternative to it. Now, the the extended church during theses sticks its neck out further and it talks about what is efficiently computable. Okay. It says that anything that we could efficiently, feasibly compute by a physically buildable device, meaning let's say, you know, our rough and ready approximation in computer science.
But, you know, meaning, you know, anything we can compute in polynomial time, you know, using resources that scale like the problem size to some fixed power ought to be computable in polynomial time using a Turing machine, meaning, you know, it should be in the complexity class P or at any rate, at least in the complexity class of BPP, which is the probabilistic version of P. Okay, there should be a, you know, a deterministic or probabilistic Turing machine to,
you know, efficiently simulate whatever we can do in the physical world. Okay. Now, you know, just just the very fact that I had to equivocate between deterministic or maybe probabilistic, you know, I think illustrates that, you know, this thesis from the very beginning was on shakier ground than the compute ability one. Okay. But probably most of you know that in the 1990s this extended or polynomial time church Turing thesis developed really, really serious fissures.
So Peter Shaw came along and those are supposed to be cracks in the foundations of the church, or indeed, as some people said, that they looked like horns. But I just I'm just not good enough at PowerPoint.
Okay. So so Peter Shaw developed discovered a polynomial time algorithm for factoring integers using a quantum computer, which is a problem certainly that no one has proven is is hard for a classical computer but that we, you know, for better or worse, we believe that enough that we base the security of most of our electronic commerce on on the belief that that and related problems are hard.
Okay. So, you know, the way you know, let me let me show you a different maybe more more unusual way to State Shaw's discovery. Okay. You know, Shaw's theorem is not merely about, you know, a hypothetical future in which quantum computers are built. It's a hardness result for a problem that could concern us right now, namely the problem of simulating quantum mechanics. Okay. This is a problem of enormous concern to chemists and physicists.
That's what, you know, a significant percentage of supercomputing time is actually used for today. And Shor's theorem, in some sense explains why simulating quantum mechanics seems to be hard in terms of more standard problems in computer science. It says that if you had an efficient algorithm for simulating nature, for simulating quantum physics using a conventional computer, then you would also necessarily have a fast classical algorithm for factoring integers.
Why? Because a simulation would in particular have to be able to simulate a quantum computer running Shor's factoring. Okay, so. So it was, you know, an amazing connection between ideas that really sort of started off this field. But now, you know, because this is a computer science lecture series, I thought, you know, at some point for for those of you who are, you know, remaining innocent of it, I need to explain what quantum mechanics is.
I don't have a lot of time to do that, but fortunately, I think I can do it in one slide. Okay. So, you know, I think that physicists, you know, really, you know, did a remarkable job of sort of making quantum mechanics look, you know, really complicated and, you know, and hard to learn. You know, indeed it is if you really care about, you know, making predictions about actual physical systems. Okay. But I'm a computer scientist.
I don't you know, and, you know, the marvellous secret in quantum information is that quantum mechanics turns out to be just remarkably simple. Once you take the physics out of it, and the way that I, you know, and many of us in this field think about quantum mechanics is that it's a certain generalisation of the rules of probability themselves. Okay. So I think of it as sort of not even physics in the usual sense.
It's it's more like an operating system that physical theories can run on as application software. Okay. And so, you know, we all know that in probability theory, you would describe your knowledge of a physical system by using a list of non-negative real numbers which add up to one and which we call probabilities. Okay. And which describe the likelihood that you'll find the system in one configuration or in another one if you if you look at it.
But now, in addition to looking at a system of one thing you can also do is transform it somehow. Like if you have a coin that you flipped before looking at the coin, you know, you could just flip it, you know, and that would correspond to taking your vector of probabilities and acting on it by a linear transformation, which has to have the property that it maps any normalised probability vector to another probability vector.
Okay. So any linear transformation that does that, we call a stochastic transformation. Okay. It's a given by, you know, a non-negative matrix where all the columns come to one. It's a made it's a matrix that preserves the one norm. Okay. Now, if you know, without knowing anything about physics, let's say you were a mathematician in the 1800s.
If someone had come to you and said, I want you to invent a theory which is just like this one, just like probability theory, except it should be based on the two norm rather than the one norm. Because you know the two norm is the one that, you know, that sort of God prefers in every situation. Okay. You would you would be more or less forced to invent quantum mechanics. Okay. You know, this is not the usual story above of how you know where it comes from.
You know, usually, you know, you tell a whole long tale about, you know, I guess a box that emits radiation and, you know, hydrogen atoms and so forth. Right. That is the story of how these rules came to be discovered, which is, you know, an important and fascinating story that took place between 1919 25 or so. But if you just want to know, at the end of the day, what are the rules?
They are like the rules of probability, except that instead of a vector of non-negative real numbers, now we describe the state of a system using a vector of complex numbers, which we call amplitudes. And if you measure a, you know, a system, then these amplitudes become probabilities. Right. So, you know, it would you know, you don't want a theory to tell you you'll have a -10% chance of, you know, seeing some outcome, let alone an 80% chance.
Okay. But so you can, you know, each amplitude becomes a probability by taking its squared absolute value. Okay. And measurement, you may have heard, is a destructive process. So the system, you know, when you look at a system, you force it to collapse to one of the outcomes. You know, it makes up its mind, you know, it becomes outcome I with probability, absolute value of alpha survival squared. And then and then it sticks with that choice. Okay.
Now, in addition to looking at a system, you can also act on it, which now means taking this vector of amplitudes and acting on it using any linear transformation that preserves the two norm. Okay. That we call a unitary matrix. It's just a complex generalisation of an orthogonal matrix. Okay. And so so those are the two rules. You can make a measurement that gives this probabilistic result, or you can transform your state by a unitary matrix.
Okay. And are all of the differences, you know, all of the weirdness is of the quantum world that you've ever heard about are just ultimately traceable to the fact that amplitudes are based on the two norm and therefore work differently than classical probabilities do, which are based on the one norm. Okay. So all right. So now I need one slide to tell you what is quantum computing?
So so this this idea dates back to the early 1980s when a few physicists like Richard Feynman and, of course, David Deutsch, who's a here in Oxford, started, you know, noticing that if you want to simulate a quantum system using a conventional computer, it seems to require an exponential blow up in the amount of time. Why? Because, you know, the rules of quantum mechanics say that you need to assign an amplitude to every possible configuration that your system could be in.
Okay. So if you had an bit's or, you know, as we call them, qubits, quantum bits, there are two to the N possible configurations of those qubits. And the rules say that every one of those two to the N possibilities gets an amplitude. Okay. So just to keep track of, say, a thousand particles, you know, nature off to the side somewhere needs to maintain a vector of two to the thousand complex numbers.
And whenever something is done to the particles, nature needs to take that vector of size two to the thousand and multiply it by a matrix. Okay. So, you know, that's just seems like an enormous amount of effort for nature to be going to. And, you know, and it you know, it raises the, in retrospect, obvious question, you know, why don't we, you know, take that regimen of, you know, how hard quantum mechanics is to simulate and turn it into lemonade, okay?
Of, you know, build a computer that would itself exploit, you know, this these amplitudes that could be, as we say, in a superposition of all of these states. Okay. So now, of course, the question arises, supposing we built such a computer, what would it be? Good for five men in Deutsche were only able to give one real answer to that question, which is that it would be good for simulating quantum mechanics.
Okay. You know, I think that that remains maybe possibly the biggest, you know, real practical application that a quantum computer would be known to have. Okay. But one important point that I should clear up is that, you know, in like almost every popular article that's been written about this subject for the past 25 years, you know, it has described a quantum computer as a device that would just try each possible answer in a different parallel universe.
Okay. Or, you know, in a in a in a different brands. Okay. That is that that that that that that is not how it works. Okay. You know, and, you know, I don't care whether you believe or don't believe in, you know, the reality of parallel universes. Okay. It's you know, that's just that that description that you constantly see of a quantum computer is wrong for just a straightforward technical reason.
Okay. It's wrong because you while you can create a superposition over all the possible answers to some problem. So giving each possible answer some amplitude, if you, you know, at some point you have to measure the computer to see what state it's in. And if you just make a measurement not having done anything else, all you're going to see is a random answer. Okay. And if you just wanted a random answer and you could have picked one yourself with a lot less trouble.
Uh huh. So, you know, the only hope of getting a speed advantage from a quantum computer is to exploit the ways that amplitudes are different from conventional probabilities, and in particular, the fact that amplitudes can also be negative or complex or whatever. And so the goal in quantum computing is always to choreograph things so that the the amplitude, the final amplitude for the correct answer is very, very large, so close to one.
Whereas the final amplitudes for the incorrect answers are very small, close to zero. Okay, if you can arrange that, then when you measure the computer, you should see the right answer with the high probability, you know. And if it's mere a computer that is merely correct, 70% of the time, I should say, is perfectly fine for our purposes because, you know, if you're not happy with a 70% chance of correctness, then just rerun the computer 100 times and take the majority answer.
Okay. So but but now how do you boost the probability of the right answer? The what that always involves is sort of choreographing a pattern of quantum interference. So the idea is that for each wrong answer, there will be sort of some contributions to its amplitude that are positive and others that are negative. So on the whole, they will cancel each other out. Okay. Where is the amp? The amp? The contributions to the amplitude of the correct answer should all be in phase with each other.
So all positive or negative, if you can arrange that, then you know, then that's that. That is how you get a quantum speedup. It was not obvious to anyone that, you know, that that that this very strange hammer will actually hit any of the nails that we care about in computer science. You know, besides simulating quantum mechanics itself. Okay, but, you know, being computer scientists, we can associate any concept with a an inscrutable sequence of capital letters.
So this is what was done by my advisor, Ramesh Fasoranti, and his student, Ethan Bernstein, in 1993. When they define the class bq p or bounded error quantum polynomial time. This is the quantum generalisation of the class P, you know, of problems efficiently solvable with a classical computer. Okay. And this is just all the problems that are solvable efficiently by a quantum computer with a bounded probability of error.
Okay. And so, so now Shaw's great discovery in the nineties could be phrased the saying that the factoring problem, strictly speaking, a decision version of the factoring problem is in this complexity class BQ P and that this was the discovery course that made many people interested in quantum computing who who had not been before like the intelligence agencies. Okay. So just to show you, you know, a little map of the world to orient you a bit.
So, you know, here is p problems efficiently solvable with a classical computer. Here's M.P. the problems whose answers are efficiently checkable by a classical computer, you know, at the top of end. Are the famous NPR complete problems. Okay. And, you know, already here there are profound questions like the P versus NP question that you may have heard of.
So now BQ P is a generalisation of P. So, you know, a quantum computer can only simulate a classical one, but it might be able to do more work. And so what she showed is that BQ P contains at least one NP problem, namely factoring, which is not known to be in p. Okay, so you know, I drew bq p with a wavy border because everything quantum is spooky and mysterious. Okay, but yeah, but we do know a little bit about this class now.
So we so, you know, you know, in particular, you'll notice, you know, a factoring. So you may know is neither known nor believed to be np complete. There are excellent theoretical reasons why it should not be an and p complete problem. And to this day, you know, we do not know whether bq p contains NPE. Okay. We don't know if there is an efficient quantum algorithm to solve the NP complete problems.
Many of us would conjecture that the answer is no, that, you know, quantum computers will give you at most a limited advantage for that. Certainly Shor's algorithm takes advantage of very, very special structure in the factoring problem. You know, ironically, some of the same structure that makes factoring so useful for public key cryptography.
Okay. Well, in the other direction, we also don't know whether BQ P is contained in NPE, so a quantum computer might be able to solve problems for which a classical computer cannot even efficiently verify the answer. Okay, that will be important later in the talk. Now we do know that the BQ P is contained in well, in polynomial space, in particular in a class called P to the sharp p, which means are might as my students today call it hashtag P.
Okay. Which means, you know, all the problems that you could solve if you had an oracle for counting problems for, you know, counting the number of solutions to some combinatorial problem. So, so, so in particular, that means the quantum computers will at most get an exponential advantage over classical ones, right? They will not do anything that is classically computable, like the whole thing problem.
Okay. It also means that in our present state of knowledge, we really have no hope of proving unconditionally that quantum computers are more powerful than classical ones. Or in other words, that bq p is different from P. Okay. And that's a very important point. Okay. But the reasons for it have in some sense nothing to do with quantum computing. Okay. They're just we don't even know how to separate P from P space, for example.
Right. And if those two were equal, then certainly, you know, a P and BQ P would get you know, would get sandwiched together, too. Okay. So any evidence that we're going to offer, so in this talk that a quantum computer is achieving supremacy is going to have to be conditional on some hypothesis, on some kind of complexity, theoretic, hardness, conjecture. And the question that will interest us is which conjecture? You know, how safe and believable conjecture can we make it?
Okay. So now you might say, well, you know, sounds like quantum computers just refute this extended charge Turing thesis. What more proof could anyone want? You know, then that they do factor in. Okay. There are two drawbacks, as I see it. Of of of of Shor's algorithm as, you know, evidence for quantum supremacy.
Okay. The first is just the obvious one that, you know, as you may have heard, building a actually building a quantum computer, which is scalable, which they could factor a thousand digit numbers, turns out to be rather hard.
Okay. The world record, you know, after about well over $1,000,000,000, I guess, of investment in this field, you know, over 20 years of brilliant experimental effort has been that there is now there are now quantum computers that can factor 21 into three times seven with high statistical confidence. Okay. I think 35 may be on the horizon.
Okay. But, you know, you you know, the the there's a huge problem called decoherence, which means sort of the unwanted interaction between the quantum computer and its external environment, which, you know, in effect prematurely measures the computer. Okay. And if you want to build a scalable quantum computer, you need to get this decoherence down, if not quite to zero, then to a very, very low rate.
And so, you know, the experimentalists have made enormous progress toward that goal, but they're not there yet. But, you know, you might ask, well, you know, couldn't we just take systems that they already have that they're, you know, in the lab. Right. You know, I mean I mean, there are lots of molecules where, you know, for which the Schrodinger equation seems kind of, you know, hard to solve.
Right. But, you know, unfortunately, in those cases, you know, we don't know whether the hardness is, you know, is actually asymptotic or, you know, in nature the kind that a theoretical computer scientist can analyse or whether it's merely that, you know, someone will will write down the ground state of this particular physical system and win the Nobel Prize for it. But that Nobel Prize will be maybe only out of one effort, you know.
You know, maybe it won't be an exponentially scaling amount of effort. Okay. So so then you might ask, can't we at least meet the experimentalists halfway? So I like to put it that is, can't we say, look, you know, you don't have to build a full quantum computer that will factor numbers with Shor's algorithm.
But just do you know something, you know, closer to what you can do today, that you know, that we as computer scientists can then interpret as solving a problem, that we understand, that we can argue about the hardness of.
Right. And, you know, and and if we forget about, you know, the problem having any practical importance, then that may dramatically expand, you know, the number of places we could work for that, you know, you know, the the other issue is, of course, you know, factoring might, for all we know, have a fast classical algorithm, you know, I mean, you know, if a fast factoring algorithm were discovered, the way I like to put it is that might collapse the world's know digital economy.
But it's not it would not be known to collapse the polynomial hierarchy or anything like that. Okay. So you know that factoring from a theoretical standpoint is just this one particular problem, right? You know, if it had a fast a classical algorithm, it's not known to have any sort of wider consequences for other things. So, you know, wouldn't it be great if we could prove, for example, that, you know, if you could efficiently simulate a quantum computer classically?
So like if P were equal to BQ P, then P would also be equal to N.P. Okay, that would be a wonderful result. Okay. Now, we don't know how to show that, I should say. But, you know, in this talk, I'll show you how we can now come closer to that than one might have thought possible. Okay. So, you know, I think that in this quest for quantum supremacy, you know, physicists are really going to have to think more like applied cryptographers have been thinking for a long time.
Which means, you know, you define a clear mathematical task that you can perform with the quantum hardware, hopefully of the near future. You think hard about how your worst enemy would perform that task or appear to perform it using only classical resources. You know, a an excellent a historical analogue in physics for this is the violation of the bell inequality.
Right. Which only just a year ago, you know, people managed to violate it in a way that closes off essentially all the loopholes as to how, you know, nature could have been doing this in a way that was secretly classical behind the scenes.
Okay. So we want to do a computation where, you know, we can then convince a sceptic that, you know, that this computation was not done in a way that you understand in a way that was, you know, secretly, that you can sleep easy at night interpreting as, you know, just maybe it's just classical behind the scenes. Okay. So, you know, so that means that, you know what, for one thing, you know, you should publish benchmark challenges.
You should say, here is what I did. And, you know, here is a benchmark. We challenged classical sceptics to do the same thing with their classical computer in any comparable amount of time. You should also be able to isolate a very, very clear assumption that says, look, you know, if you could simulate my complicated system efficiently with a classical computer, then you would have to be solving this easy to state problem. Okay. So then people have a clear target to aim at, right?
That if you believe that this clear problem is hard, then my quantum system is hard to simulate. Okay, so the same kind of game of reductions that people play in cryptography, you know, and you should leave a safety margin. So I'm not interested in, you know, doing something like a factor of two faster than, you know, we could do it with, you know, a reasonable multicore classical computer. You know, I would like a factor of a billion faster. A factor of a trillion.
Okay. So. So when when these are your goals? One of the things that we discovered within the last six or seven years is that you find yourself driven to consider what are called sampling problems, which are broader than the problems that we usually think about in theoretical computer science, which are just decision problems, you know, with a yes or no answer.
Okay, so in a sampling problem, you're given an input, say X, and your task is to output a sample, you know, either exactly or or better yet, just approximately from a probability distribution. Say this of X over strings. Okay. Say over end bit strings. Okay. And so, so. So there, you know, these are problems that don't have a single valid output. You know, your goal is to sample. Okay. These are also, you know, you know, I mean, many computer scientists have studied these problems as well.
Like, you know, you you want to sample for a random point in a convex body. You want to sample a random matching and a graph. These would be examples of sampling problems. Okay. And so what we found is that, you know, sampling problems can be, number one, much easier to solve with devices that fall short of universal quantum computers. Okay. You know, which might be available with technology of the near future.
Number two, sampling problems can be much, much easier somehow to argue are hard for a classical computer to solve. You know, but the sampling problems that we'll talk about, you know, they they don't have practical applications that I know of, nor is it very easy to verify the result with a classical computer. So you do give something up. Okay? Nothing's free.
Okay. So a an example of these sampling problems that we've sort of learned to focus on in quantum supremacy research is what's called boson sampling. So this is something that my student, Alex, AKA and I proposed in 2011. And it's basically it's a very rudimentary type of quantum computing which involves only identical non interacting photons. Okay. So the classical analogue of our system is something called Galton's Board, which you can see in many science museums.
It's where you drop balls one by one into a lattice of pegs and the balls sort of bounce around randomly. And then you see that the the bins they land in at the bottom approximates a binomial distribution. Right. So this is not a universal computer. But, you know, if you didn't know any other way to calculate binomial calculations, you could use this thing to estimate them, you know, be not, you know, I mean, maybe not entirely useless. Okay, so what is the quantum analogue of Gorton's ball?
Well, we could replace the pegs by beam splitters. We could replace the balls by photons. Okay. And then, you know, physicists have known even since the eighties that, you know, that you already with just two photons and one beam splitter, got some very interesting phenomena. So this is true. Here's an effect called the Honjo mandel dip it is. You shoot two identical photons at the exact same time. They are the two arms of a 5050 beam splitter.
Okay. And the photons never directly interact with each other. Right. I mean, they have in the sense that there's no force acting between them, certainly not at low energies. Okay. So and nevertheless, what you find, if you do this experiment perfectly, so is that 50% of the time the two photons both end up in this arm. 50% of the time, they both end up in that arm. Okay. And they never end up in separate arms. Okay.
So somehow they become perfectly correlated, even though they have never interacted. Okay. So so you know what on earth is going on. Okay. So, you know, just like with everything else in quantum mechanics, there is an answer. You know, it's not just mysterious, confusing whenever there is an answer. And the answer involves the amplitudes having minus signs.
Okay. So basically what happens is that in when you write down the quantum state of the system, there are two possible there, you know, and you write the amplitude for the two photons to go down separate arms. There are two different contributions to that amplitude, one that comes from the photons going like this, and the other that comes from the photons going like that and crossing each other. And one of the contributions is positive and the other one is negative.
So they cancel each other out and you never see them going down. Separate arms like the amplitudes where they go down the same arm reinforce. Okay. So the basic idea is that if you have any photons, then you actually do find the amplitude for them to end up in some given configuration, you have to sum over third of all, any factorial possible ways that these photons could be rearranged since they're identical particles, bosons, namely right.
And swapping two of them does nothing to the state of the world. Okay. So you have to add. So just to find the amplitude for one configuration, you have to add up in factorial complex numbers. And if these are pointing in different directions in the complex plane, then those contributions could cancel each other out. Okay. So the formal set up is that, you know, you have a network of beam splitters, let's say, with an input modes, some larger number M of output modes.
So an identical photons enter one per input mode. We assume for simplicity, let's say that they all leave in different modes. They don't have to, but if the number of modes is large enough, then with high probability they will go, in which case there are m choose n possible, you know, configurations of the output. Now to find the probability of one of those output configurations.
Now what you need to do is so you look at the network of beam splitter and you look at the sort of section of a unitary matrix that that defined. So it would be an M by end matrix whose columns are all orthogonal unit vectors, and then the probability of a particular outcome is just going to be given by the squared absolute value of the permanent of the appropriate end by end sub matrix of that and by and matrix. Okay. So now what is the permanent of a matrix?
Well, if you know what the determinant is, the permanent is the same thing but without the minus signs. Okay, so it is this, it's an extremely important function in theoretical computer science and combinatorics, which so happens to also play an important role in physics, namely in, you know, giving you the amplitudes for identical bosons.
Okay. And so the permanent of an end by end matrix is just the sum for all and factorial permutations of, you know, the product of the entries along that permutation. Okay. And so, so, so, so amplitude. So the amplitudes for identical bosons are permanence, by the way, the amplitudes for identical fermions are determinants. Okay, so, you know, these these two functions that play such a wonderful role in computer science are also, you know, show up in nature.
And so then the probability is just the absolute square of the amplitude. Okay. And so, so, you know, this was noticed in the 1990s I think by Troy Lansky in Tisch. B people realised that this is an amazing connection because the permanent is very, very well known to computer scientists as a hard function.
In fact, the permanent valiant proved in the 1970s that it is complete for that class sharp p that I mentioned earlier, the class of all counting problems which is even above the NP complete problems. Okay. So, so this immediately raises a question if a, you know, photon amplitudes are given by permanence of matrices, then could you just use a system of identical photons to calculate the permanent of any matrix of your choice.
Right. You know that and thereby solve, you know, and p complete problems and even even more than that in polynomial time. Okay, so this seems, you know, too good to be true, right? You ought to be suspicious of any such thing. Okay? And in this case, you know, the answer turns out to be no. Okay? This this does not let you calculate the permanent of a matrix of your choice.
The reason why not is interesting. Okay? It is because, once again, it's, you know, amplitudes in quantum mechanics are not directly observable. At some point you've got to measure this. So some when you measure it, you're just going to see a single, you know, a configuration of the photons with probability given by the absolute square of the permanent of an associated matrix. Right. So you don't directly observe permanence. Okay.
Now, it's true that if you repeated this experiment enough times, you could use this to estimate the squared permanent of a matrix of your choice. But in general, you know, to embed. Your matrix as a sub matrix of a unitary matrix.
You need to make it so that its permanent is exponentially small, which means that if you wanted a decent estimate for the permanent, then you would need to repeat this experiment an exponential number of times, which means that in the end you're getting no advantage over what you'd get if you just used, you know, a classical computer with it with with brute force. Okay. So then, you know, so then this raises the question within, then why is boson sampling interesting?
If it doesn't let you calculate the permanent? Okay. So what Pop and I did was that we looked at what boson sampling does do, which is that what samples are a random matrix, if you like, in such a way that matrices with large permanence are somewhat more likely to be sampled than matrices with small permanence. Okay, now what is such an ability good for? Well, I have no idea. Okay, but we can give evidence that even that sampling task is already classically hard.
Okay. So. So the first sort of theorem that we observe is that, you know, if there were, say, a polynomial time classical algorithm that could sample from exactly the same distribution as the system of a bosons would sample from in the ideal case, then this would have a striking consequence for complexity theory. It would mean that the P to the short p would equal BP to the NPE, which, if you don't know what that means, you could take my word for it that it's bad.
It would it would mean that, you know, two complexity classes would, you know, that are both very powerful would be equal to each other. And that's a problem because one of them is supposed to be way more powerful even than the other one. Okay. So P to the sharp p contains the entire polynomial hierarchy, whereas BP to the end is contained within the polynomial hierarchy. Right. If those two became equal, then the polynomial hierarchy would collapse to the third level.
Okay. Which is, you could say is in some sense almost as bad as P and P, but sort of just sort of at a higher level up. Okay. So, you know, the reason why this would happen is basically that if you had a fast classical sampling algorithm for for boson sampling, then, you know, you could take a permanent, which is a sum of both positive and negative terms, you know, and you could represent it as a sum only of of of non-negative terms.
Okay. Because you could represent it as the probability that this classical algorithm will produce this output, let's say. Right. Which is then, you know, just you're just counting how many different randomness as different sequences of random bits. Could this classical algorithm be fed that would cause it to produce this particular outcome as its output? Right now, that might still be an exponentially hard problem.
But unlike the, you know, directly simulating a quantum system, that is just a problem of summing a whole bunch of non-negative terms. Okay. And that is the sort of thing that we know how to do in a complexity class like BPP with an oracle for. You know, so randomised polynomial time with an oracle for NP complete problems which again is unrealistically powerful but less so than a polynomial time with an oracle for counting problems.
Okay. If these two are equal, then I think you know something way, way more perverse happens than there being a fast classical factoring algorithm, which is that the polynomial hierarchy collapses. Okay. Now, what we really want to do is say that even a classical algorithm that approximately sampled lot, approximately simulated a bosonic experiment would have unlikely complexity consequences.
That's a much more complicated problem. We conjecture that this would already imply a collapse of a polynomial hierarchy.
But. But we're. But we're not able to prove that the result that we can prove so that if there were an efficient classical algorithm to sample a probability distribution, which is even anywhere close, let's say in its total variation distance to the pub, to the distribution involving permanence that this bosonic system is supposed to sample from, then that would have the following consequence for complexity theory.
It would mean that there is an algorithm in this complexity class BPP with NPR Oracle, which would estimate the permanent of the permanent squared, let's say, of a matrix of independent Gaussian entries with high probability over over such matrices.
Okay, now we suspect that that task is already sharp p complete, which, you know, if so, we would get to have the consequence that even a noisy simulation of our experiment or even a simulation of a physically realistic version of this experiment would already collapse the polynomial hierarchy. Okay. This remains an outstanding open problem, though. You know, it's the problem about classical complexity theory, but which is, you know, inspired by this optics experiment.
Okay. So now an obvious difficulty with boson sampling is, you know, supposing that you do such an experiment, how does a classical computer even verify the result? So, you know, one way the obvious way to do it, if you like, is just to calculate the permanence of all the sub matrices corresponding to the outcomes that are observed, and then check whether these permanence are, as it were, anomalously large, you know, consistent with you're doing boson sampling of this.
This works, this is just fine. But you might complain. Well, wait, doesn't that entail calculating permanence? And wasn't the whole point of everything you're doing that the permanent is exponentially hard? Well, doesn't that defeat the purpose? Well, you know, you know, if maybe so if you had, you know, a hundred photons or a thousand photons. But our claim is that there is a sweet spot for quantum supremacy experiments.
The sweet spot would be, you know, when you're dealing with about 30 or 40 photons, okay, in which case we'd be dealing with the permanence of 30 by 30 or 40 by 40 matrices. Okay. Such permanence are difficult to calculate with a classical computer, but they're not impossible to calculate. Okay. With enough effort, you could calculate the permanence with a classical computer in order to verify that the experiment was working as intended.
But you could see that the doing, the result classically was taking you much more effort. It was a lot harder. Okay. And so this is really the sort of the sweet spot that we're hoping to aim for now. What is the current experimental situation with Bose on sampling? Well, last summer, a year ago, the group at I guess down the road at Bristol reported a boson sampling experiments with six photons, you know, beating three or four photons that had been done previously.
And so basically, you know, they they you know, it was an incredibly hard experiment. I think they only managed to see 15 events or so. Okay. But they but they, you know, to within experimental limits, they confirm that the amplitudes for processes involving six photons are indeed given by the permanence of six by six matrices of complex numbers, you know, as quantum mechanics said all along that they would be okay, but now we have direct confirmation of it.
Okay. Now, scaling up to a larger number of photons, like 30 or 40 presents a very hard engineering problem. And the basic reason for that is that you need all the photons to arrive at the detectors at the same time. If you want to see, you know, this interference pattern, we're all in factorial possibilities contribute to your amplitude. Okay? And right now we just there do not exist on earth photon sources that are good enough for this purpose.
Okay? There are sources that sometimes limit a photon, but you can't control exactly when. And so then, you know, if you have any of these, you know, imagine how long it takes until they all happen to emit a photon at exactly the same time. Well, you know, the time you have to wait grows exponentially with an okay. So that that that's really the problem here. Okay. There is an amazing idea that could help with this, which on my blog I named scattershot B.S. Scattershot both on sampling.
Again, it was it's a beautiful idea. It was proposed right here in Oxford by an Ian Walmsley group. Steve Carl Palmer, the one who, who explained it to me. And you know, and the idea here is that you can have a whole bunch of photon sources which are not deterministic, which will, you know, amid a photon whenever they feel like it. But they're but they're heralded. So each one, when it does admit a photon, it also emits a partner photon going in the opposite direction.
That tells you that, yeah, a photon was flying out this way right at this time. And then, you know, let's say you have a thousand of these sources and let's say that within a given time window, only ten of them happen to generate a photon. Okay, well, then at least we know which ten they are, and whichever ten they are, we just define those after the fact to be our initial state for our boson sampling task.
Okay. And since we didn't care any way about exactly what distribution we were sampling, as long as it was some distribution, that's classically hard. We don't really care which sources happened to be the initial ones. Right. We could get the experiment, decide that for us. Okay. It's a beautiful idea, but. All right. But given the difficulties in scaling this up, you know, it is worth considering whether boson sampling like ideas could be ported to other quantum computing architectures.
You know, where where we're maybe progress will come sooner than it would than it will come in optics. So this. It's just, you know, I just tried to take like 5 minutes or so. Okay. So I just want to tell you a little bit about what we've been working on recently.
So, you know, in a few years, we are very likely to have 40 or 50, very high quality qubits with controllable couplings in, you know, to possibly, you know, either or both of of two architectures, superconducting qubits or trapped ions. Okay. So there's been amazing progress made along these lines. You know, the ones that were sort of most, I would say laser focussed on scaling up right now are the, you know, possibly the group of John Martinez at Google now formerly UC Santa Barbara.
Okay. But there are other groups, you know, all over the world who are working who are also working on these two approaches. And I should say, by the way, that, you know, you may have heard there's this company, D-Wave, it's called, which, you know, has you know, you know, says that they have a thousand qubits.
But we don't you know, we don't really know what to say about sort of the the quality of those qubits or, you know, are they good enough to do something which is hard to simulate with a classical computer, you know, even in principle, you know? And so personally, I am sort of way more excited about 40 or 50 qubits that I under that I understand, than about a thousand qubits that I don't understand. Okay.
And Martinez, you know, is aiming to get, you know, within the next few years, sort of 40 or 50 qubits that seem like they would be good enough for a real quantum supremacy demonstration. And so that that's sort of the exciting thing. But this is going to require thinking of sort of new ideas beyond boson sampling, right? We now have both the burden and the opportunity to sort of adapt, you know, our complexity theory to the hardware that's going to become available within the next few years.
Okay. So I think, you know, 40 or 50 qubits are still not going to be enough for quantum error correction, you know, or to any substantial degree that what you do factor any interestingly large number or anything like that. But it may very well be enough for a convincing quantum supremacy demonstration.
Okay. So I would say that our duty as theoretical computer scientists is to tell the experimenters what they ought to be doing with their existing hardware or with, you know, the stuff that they're planning to build within within the next couple of years and how to verify the results and what can be said about the hardness of simulating the resulting system with a classical computer.
Okay. So you know, ah, so, so I have recent joint work with Ritchie Chen from Think VI University and well, you know, we've been thinking about just, you know, what if you just took, you know, Martinez's 40 or 50 qubits and all you did was you just applied a random quantum circuit. Okay? So you just did a bunch of random unitary transformations between, you know, neighbouring pairs of qubits and this like a two dimensional lattice where they're arranged on a chip.
And then you measured the result, okay, you're going to see some sample from some wild probability distribution. Okay? So, you know, not very interesting in itself, but what can we say about the hardness of sampling from that same distribution with a classical computer? Can we say anything analogous to what we said with boson sampling? Okay. And so, you know, we've to some extent been able to do that.
Okay. And, you know, what we can actually do in this case is just forget about are you sampling from the right distribution or not? We can just say here is the statistical test that you would apply to the outcome of this experiment.
Right? Like here's a test that you would do which involves, you know, calculating the probabilities for the observed outcomes, just like with with boson sampling, you know, seeing if the experimental results are consistent with with, with, you know, with, with, with what the theory predicts. And and now we will just directly reason about how hard would it be for a classical impostor to do anything whatsoever that passes that same statistical test?
Okay. Regardless of whether or not they would act, they would actually sample from the same distribution or from anything close to it. Okay, so we'll have a purely operational thing. We can tell the experimentalists. Okay, can they do this test? And if you see outcomes of your in your hardware that pass this test, then under a very plausible complexity hypothesis, you know. You are doing something that, you know that could not have been faked classically in any reasonable amount of time.
Okay. So, you know, the verification of the outputs, there are various ways you can do it. You know, you know that the amplitudes should be like distributed, like Gaussian random variables. You can use that to your advantage, you know, are theorems about sort of mixing that you can you can exploit here, you know. So concretely, you could apply a very, very simple test. Like just say take all of the outcomes after you repeat this experiment, say 50 or 100 times.
So see 50 or 100 outcomes you don't need. Importantly, you don't need to repeat the experiment an exponential number of times. All right. So you don't need to characterise the entire probability distribution, which would be way too expensive. Okay. You just need to repeat the experiment some small number of times and then for example, just check. Do it. At least 60% of the outcomes that you've sampled have a reasonably large probability according to this theoretical probability distribution.
If they do, then you declare that the test has been passed. Okay. And then what we'll do is we'll say, how hard would it be for a classical sceptic to generate any samples 3x1 up to x t that would pass this same test. Okay. And we make a sort of admittedly strong hardness assumption, okay. But one that just talks about, say, an ordinary decision problem.
Basically what it says is that there should not be any polynomial time classical algorithm that given a random quantum circuit, just sort of guesses whether a certain the probability of some particular outcome is greater than or less than some threshold with with a probability which is even like two to the minus n better than random guessing and being the number of qubits. Okay. That's admittedly a pretty strong assumption. Okay.
You know, and in particular, there is a classical algorithm that will guess the answer with probability like a half plus one over exponential and m the number of gates in the quantum circuit. Okay. But will choose a number of gates which is larger than the number of qubits like, you know, quadratic, larger, let's say. Right. And so then this is going to be much smaller than that. Okay. So yeah. And then we don't know how to refute that conjecture.
And what we can prove is that if this if you believe this conjecture, you know, if it holds, then it is hard for a classical imposter to do anything that would, you know, that would that would pass the same statistical test that that the quantum device passes. Okay. So, you know, and there are some, you know, relatively simple reduction to prove that. Okay. So we you know, we we have we thought about what is the you know, how would you simulate a class A quantum computation classically.
Right. There are sort of, you know, different ways to do it. Like the the Schrodinger approach would say just store the entire quantum state in memory, you know, and that uses two to the N time and also to to the end memory.
The Feynman approach, if you like, wejust calculate each amplitude, one by one, is a sum of contributions that uses vastly less memory, only a polynomial amount of memory, but it uses an exponential, you know, uses a much greater amount of time exponential in the number of gates rather than just in the number of qubits. Okay. And so you might ask, could you get the best of both worlds? We observed that you could.
For those of you who know classical computer science, you can do it using an analogue of Savage's theorem. Okay. So it's like, you know, you can do it using a recursive divide and conquer approach where you could actually simulate a quantum circuit using polynomial amount of memory and using an amount of time in only grows like the number of gates to the power of the number of qubits. Okay. But that, you know, this still does not falsify that that that that hardness conjecture that I made.
So the best things that we could figure out how to do, you know, still, you know, I mean, it's a very interesting question. Is that optimal? Could you improve it further? But if this is the optimal thing, then, you know, then, then, then then this conjecture that I made ought to be true, in which case, you know, the random quantum circuit would indeed suffice for a quantum supremacy experiment.
Okay. So, you know, there's yet another approach to quantum supremacy, which is called for your sampling, because I'm running out of time. I think I'm going to skip over this. We have some new results about this as well. There's some beautiful work by Bremner, Joseph and Sheppard about it. We have a sort of a new kind of way of talking about the computational hardness of a four year sampling, which involves some new kind of structural complexity theory and involves pseudo random functions.
But again, because I'm out of time, I think I'm just going to go to the conclusions. So conclusions are, you know, in the very near future, we might be able to perform, say, random quantum circuit sampling, you know, perhaps also for your sampling with 40 or 50 qubits.
Okay. And, you know, I think a central question is, you know, once we can do this, how do we verify that something classically hard was achieved and that therefore, you know, the extended church Turing thesis was real, you know, if not refuted, then at least strained. Okay. You know, and the problem is, you know, there is no direct physical signature of quantum supremacy. Right. Experimentalists keep asking me for that.
But there's not one, because all the two premises means is that there is not an efficient classical algorithm to do the same thing. And if you want to talk about the non-existence of an algorithm, you are sort of forced to talk about complexity theory.
And, you know, I think that as quantum computing theorists, we would be urgently called upon to think about this, even if there were nothing theoretically interesting to say about it, even if it were just merely, you know, in the, you know, in the service of the experiments that are about to be done. Okay. But luckily for us, I think there is there are theoretically interesting things to say about it. So, you know, all the more reason to to work on this, some of the open problems here.
You know, what happens with boson sampling when there is noise and error in your system, in particular when let's say a constant fraction, 10% of all your photons get lost and never get detected at all. In recent work with Daniel Brode, we've been able to handle the case where a constant number of photons are lost.
If just a few photons are lost, then we can show that that that the the experiment you're doing still retains the computational hardness of the original better than sampling where nothing is lost. Okay. But if more than if a constant fraction of photons are asked, which is the more physically realistic thing, then we don't know what happens. Okay. So, you know, I would I would love to to show that, you know, prove that conjecture.
I mentioned earlier that, you know, that even a fast classical algorithm for approximate boson sampling or any kind of approximate quantum sampling, for that matter, would collapse the polynomial hierarchy. I've actually offered $1,000 reward for that for, for, you know, just a just for you. I will increase it right now to £1,000. Okay. But so we can and I very recently were able to prove that any implication like this would need to use what are called non relative ising techniques.
Okay. So it would need to use some interesting complexity theory. But you know, this is no abstraction to its being true. Okay. And then, you know, could there be an efficient, like classical cryptographic scheme in order to verify that a boson sampler is doing the right thing?
So, like, without having to calculate the permanent on your classical computer, could you sort of smuggle into the boson sampling matrix some sort of secret that then when you saw the output, you know, you would know that it was doing the right thing, even though you couldn't calculate the permanent. Bremner has given a proposal that's sort of like that for for your sampling. But we you know, we don't really know what to say about it. Security.
And in the case of boson sampling, we don't even have a proposal. So these are all things that, you know, I, I hope to think about. I hope to get others to think about. And thanks for your attention.