Latest / Strachey Lectures / Strachey Lecture: Quantum Supremacy

Transcript

Strachey Lecture: Quantum Supremacy · Strachey Lectures

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