The New Quantum Era

Sebastian Hassinger 0:02
The new quantum era, a podcast by Sebastian Hassinger and Kevin Rooney.

Welcome back to the podcast, we're very excited, we've got another really special guest for you today, another person, another distinguished researcher, I had the pleasure of meeting on my recent trip to Europe. Also a Dutchman, like Leo, like our last guest, Harry Buhrman is a professor at the University of Amsterdam. He's a director at the CWI, and he's the director at QuSoft as well. He's got a long and illustrious career in quantum information, he's going to take us through some of his earlier work some of his areas of interest. And then we're going to dive into some recent work, which we find really exciting,

Kevin Rowney 1:10
it's actually pretty cool. He gave us a preprint of a paper that is likely to be already up on archive by the time we air this presentation, but I got to read that that presentation, I started that that entire paper, and it's a it's a powerful framework, I think, to sort of see with clarity, you know, the nature of what will likely become the default quantum computing architecture for all systems going forward. And he's proving really cool results with respect to time complexity around that framework. So it's the papers called ultra fast quantum circuits for quantum state preparation. Many people that have got a CS background and some quantum background, I think it's a pretty straightforward read, but really cool results, I thought it'd be important, Sebastian to outline the core framework, just so that you go into this interview, the audience's is well prepared to take on some of these ideas. But it's almost like this core architecture he's talking about for a time complexity analysis that we think is going to be again, a standard part of the way QC is done is really, it's a four layer system that's repeated over and over again, that four layer system is based upon the regime of quantum error correction. But as Berman points out, we think and he thinks that that's got broad applicability across domains outside of quantum error correction. But there's four layers are, first that you set up a quantum state, and you run some quantum computing gates that do these transformations, these unitary transformations, which are so important to give such an advantage. But because there's noise or errors, you then do what's called a syndrome measurement. That's the second layer, right are removed computation there. Thank you, Sebastian, right, where you're looking at some number of the qubits that you just changed and updated. And then the third layer, the results of that syndrome measurement, go to the third layer, where there's a classical computation based upon that syndrome measurement, which gives you a way to perhaps nuance or adjust to the quantum state for error correction or for other purposes, right hands bit of computation. And then the fourth layer, some sort of like quantum computing gates that are applied to do adjustments and correction of the errors or, if Furthermore, enhance the computation. So that four layer sandwich, that four layer cake, so to speak, is then done over and over again, that's the framework in which this this new paper and a lot of Berman's recent research focuses on

Sebastian Hassinger 3:29
Yeah, I agree. Yeah, it really does feel like a foundational sort of conceptual architecture for for thinking of these quantum systems, which ultimately are going to need classical computation to be harnessed to, as you said, to implement error correction. And what's exciting about what Harry's talking about is that there may be near term computational gains that can be realized by by implementing that type of hybrid architecture, classical quantum architecture in the near term, which would be quite exciting.

Kevin Rowney 4:00
It's such a great time with this interview, I hope you enjoy.

Sebastian Hassinger 4:38
All right, we are joined today with a very special guest. We're very happy to have him with us Professor Harry Buhrman. He's a Dutch computer scientist who's made significant contributions to the fields of quantum computing and complexity theory. He holds a variety of positions. He's a group leader at Centrum wiskunde, and Informatica CWI and in the Netherlands, which is National Research Institute for mathematics and computer science. Additionally, a professor at the University of Amsterdam, and a director at QuSoft, which is a world leading and for quantum information Research Center in the Netherlands. So we're extremely happy to have Harry with us. Thank you so much. It'd be great Harry, if you wouldn't mind starting with sort of an explanation of how you ended up in quantum information, everyone takes their own path. And we always really enjoy hearing the twisted tale of how people get to where they're working in now.

Harry Buhrman 5:35
Thank you very much for the for the kind introduction and for having me on this podcast. That's really very nice. And, and I'm very happy that, that I am allowed to say something here.

Kevin Rowney 5:47
Great to have you on, really. Yeah. Yeah. So

Harry Buhrman 5:49
so my path into quantum information started quite some time ago, I have to say, because I started out as a computer scientist, I was really fascinated by computers when I was very young, about 12, or even younger, I mean, computers, you have to have to know we're not very widely spread by then. I mean, maybe maybe in big industry, but not in small homes, like like mine. And I was really fascinated by the fact that you had the computer and you could give it, you could give it a program, and you could give it tasks, and then it will just perform these tasks exactly, as you told it. And if you wanted to perform a task that would never stop, it would just go on forever. And then you could stop it, of course. And I was really fascinated by the power of what such a computer could do. And initially, I thought that any problem that you had, you could write a program, if you were smart enough, and then the computer would solve that program for you. Maybe it will take a while. But if you program smartly, it would it would actually solve that problem for you. And then I learned that there are actually problems that you cannot solve on a computer, which was due to a big hero of mine, Alan Turing, who will prove this in the 30s. And when I first saw that result, I just didn't believe it. I thought that cannot be right. I mean, they probably didn't think hard enough on how to solve that problem. How

Sebastian Hassinger 7:24
old were you, Harry, when when you encountered Turing's theorem

Harry Buhrman 7:27
then I was about that, that age, 14, 15 years old. And I was reading about it. And, and I didn't understand the proof then. But I thought, I mean, I was really blown away by the fact that you couldn't, you couldn't compute everything that you wanted to. So then I was really set on doing computer science and study that in the Netherlands, which I did. And I really enjoyed it tremendously. But I also found myself not so much interested in programming a computer, but more in understanding more about what this power is and what it's not also. So I ventured into theoretical computer science and also mathematics. And then I was lucky that I could do a PhD on these topics. To be precise on the area of complexity theory, computational complexity theory, which deals basically with this question which problems are computable in an efficient and fast way, and which ones are not with a famous P versus NP problem, sort of driving the field. This is a great unsolved problem, which asks for whether certain problems have fast, faster algorithms or proof that they don't have that. And nobody really knows how to solve that. And of course, this was a tremendous drive for me also to go into the field and of course, solve this problem, which is by to heart, and I didn't solve it. But that's, that's when I was doing a PhD on that. And in the, in the early 90s. I was also in Boston, as a PhD student for about a year or a little bit longer even. And, and one of the conferences there, there was a talk of Gilles Broussard that there was this was maybe 91 or 92. And he talked about this new complexity class called Quantum fast quantum polynomial time called BQP. And he showed some Oracle results how it somehow was different from classical complexity classes. So the ones I was used to like P and NP. And then I was really fascinated by this by this new new kid on the block. But I thought it would be too difficult for me to venture into this because I had not studied physics.

Sebastian Hassinger 9:50
Gilles is a pretty good salesman for Quantum Information Science, too. He makes it sound really cool.

Harry Buhrman 9:57
Oh, it was extremely cool, but I wasn't sure I wouldn't be able to do it because I did not have a study in physics, I just did math and computer science.

Kevin Rowney 10:05
Quantum quantum mechanics is a steep climb from computer science.

Harry Buhrman 10:09
It actually turns out, it's not at all that steep, but I just thought it was extremely difficult and esoteric and hard to get into. But then then, a few years later, I actually had a postdoc position here at in Amsterdam at CWI. And one of Gilles' students, Andre Berthiaume was also a postdoc here. And he gave a series of lectures on what actually this quantum computing is all about. And then I got sort of, into it, and I really understood. And at the same time, also, another important thing happened that was when Richard Cleve another person well known scientist from the from the area, also came to see CWI and had a sabbatical here. And then I got really into this on an easy in an easy way, because they, they knew sort of the rules of the game. And they could tell me what the rules of the game were. And then I could sort of understand that and start working in it. So I really owe a lot to them. And that's how I got into quantum information and working on on quantum computing.

Sebastian Hassinger 11:21
That's really cool. And I saw you you've done a fair amount of work in communication complexity as well. Is that right?

Harry Buhrman 11:28
That's exactly how it started because Richard Cleve kicked off. Well, that's not entirely to end, Andy Yao had already also some papers on communication complexity. But then Richard had the idea of enlarging the model with entanglement instead of quantum communication of entanglement. And

Sebastian Hassinger 11:49
I guess that brings that brings the Broussard and Bennett sort of influence into a communication complexity a little bit right with BB-84

Harry Buhrman 11:57
Yeah, yes. And then entanglement and for sure. Yes, absolutely. And also non local, non local games and Bell inequalities and all that sort of lead, Richard to study this. And then he came to CWI, and he had a problem where communication complexity problem actually where he thought he had a lower bound. So he had a quantum algorithm that was very efficient, that only used I think, one or two bits of communication and entanglement. And then actually, he was struggling with the lower bound for the classical lower bound. And it turned out and that's when, when I sort of started to work on this that we could show that there was a classical lower bound of only, I think, three bits or something, and that the actual actually also was a classical upper bound of three bits. So we had a problem where the content was one bit, say, and classical was three. And this was a hard sell. Somehow, Richard had tried an earlier version of this paper, and it was rejected on the grounds that, and actually that that paper was wrong, because it had way too big lower bounds. And it was it was rejected, on the fact that the the result was sort of not interesting. And but the mathematics was impeccable. And it turned out to be exactly the opposite. The mathematics was wrong. But the result was extremely interesting. And that sort of started kickstart at this field.

Sebastian Hassinger 13:31
That's fascinating. What year would that have been Harry?

Harry Buhrman 13:35
This must have been in 97, I think.

Sebastian Hassinger 13:40
Okay. Okay. So, so just after Shor's and just after sort of the, the, the interest in quantum is still on the rise at that point. So there's still as you said, like, some some, whatever resistance potentially at the editorial boards of papers on published journals, for papers that were looking at quantum information theory a little bit harder sell maybe than it is today.

Harry Buhrman 14:05
Yes, and no, because I mean, I think the after Shor's algorithm, I mean, it got really in this into the spotlights and and everyone was really sort of very much intrigued by what more it could do. And people still aren't. So it was gaining a lot of traction but but yeah, but somehow the the referees at the at this particular journal didn't really appreciate appreciate this result. But then it sort of took off and and that was for me a very easy way of getting into the fields.

Sebastian Hassinger 14:39
That's great. And you've had a very broad set of interests I mean, I have to ask without getting us derailed off of the the quantum information theory train but you've got some biology papers like the first peptides the the evolutionary transition between prebiotic amino How did you get entangled so speaking in biological papers

Harry Buhrman 15:00
I'm actually when I started my studies in computer science. It was a very popular study in the Netherlands. And it, it wasn't entirely certain that I was allowed to study it. Because if too many people apply for a study, then not everyone can take it. And they somehow have, they just do the lottery them, and they they flip a coin, and you're in and you're out. And so in addition to your first choice, for these, for computer science, you had to give a second choice of what you've what you wanted to study in case, you would not be able to you were not admitted to the to the, to your first choice. And my second choice was biology, because I always was fascinated by it, as well. And I still am. And I think it's also a beautiful area to work in. And at the time of these papers, or when when this paper started, we were starting a biology or computational biology group here at the CWI and I was asked to, to be one of the members of the of the committee to somehow figure out how to, how to arrange this and who to invite and what kind of direction to take. And I asked a very good friend of mine to help me biologists to help me with this. And, and he did, Peter van der Gulik, who is now actually in the group here, as well as the as the biologist. And he actually also came came to me with some computational problems in biology. And I was just so intrigued by it, that we started to work on it. And these papers came out of that.

Sebastian Hassinger 16:43
That's great. And I mean, it does feel like one of the areas that may be very strongly impacted by mature quantum hardware and quantum algorithms will be biology and biochemistry and the like,

Harry Buhrman 16:58
it could, it could very well be Because indeed, this biological processes, if you will look at them carefully enough, they are quantum mechanical. And sometimes you need the quantum mechanical description to understand them. And indeed, quantum computers could be of great help in simulating them and understanding them better than we currently do. That's awesome.

Sebastian Hassinger 17:19
And then I guess QuSoft was founded in 2015, or 2016. And that's sort of also I kind of think of around the same time as sort of the Dutch, sort of all of the Dutch efforts sort of coming together under eventually under quantum Delta in a very powerful sort of aggregated way. And I guess that's really, in a lot of ways. That's, that that's made your focus much more narrowly on quantum computation and quantum algorithms, as we as we sort of understand them today. So is, is that sort of your main focus now in terms of the the areas of study?

Harry Buhrman 17:57
Oh, yeah, absolutely. Indeed, it queues have started in 2015. But at that time, there was no quantum Delta. Yet. In the Netherlands, though, there was already the center in Delft called QuTech. And my sort of worry at the time, and maybe still a little bit was that all around not only in the Netherlands, but all around in the world and in Europe, as well, people were focusing almost exclusively on hardware, and then building very stable qubits and very stable operations on these qubits. And they were not thinking too much about what kind of algorithms do we run on this art? Where if we have it, not, so the focus was too much on hardware, and hardly on software, so to speak. And so I really thought it was important to have an institute focusing mostly on the software and instead of the hardware, and that's why I started QuSoft. And then. So this was 2015. And now this is, is much more accepted premise that indeed, we have to figure out what what kind of algorithms we need to run them what kind of algorithms we need to develop on what are the problems that are really useful to run on to solve? And in

Sebastian Hassinger 19:21
fact, I mean, I feel like in a way, your thinking has continued to evolve. And now you've been talking about how important it is to think in terms of co-design. So theorists and algorithm designers influencing the design of hardware systems, with an eye towards like, how do we implement this stuff? How do we actually make this stuff work in the real world eventually, which I think is a terrific area to focus on.

Harry Buhrman 19:46
Yeah, and of course that to go go somehow hand in hand, you need both right? You need software, people need hardware and hardware, people need software. So it's not that one can do without the other. And indeed, you're ready to talk about this code is and which basically says that you're developing them both together and somehow flows in or problems or difficulties in one area, sort of get solved by by by the other area. And the and somehow demands or questions that come up from the software side, give rise to maybe new hardware implementations. And ultimately, we will talk a little bit about that later. When we talk about this, this shallow circuits and mid circuit measurements,

Kevin Rowney 20:29
and maybe this is a good time to dive into that because this is a fascinating landscape of the the the ramified hierarchy of all these different time complexity and circuit complexity and communications complexity, you know, phenomenon in quantum computing, I think a lot of our audience is perhaps already familiar with the classical cases, right of time complexity, hierarchy questions. What are the big unsolved problems in this area for quantum is this is a sort of kickoff?

Harry Buhrman 20:56
Yeah, I mean, sort of, sort of certainly that I mean, that's sort of certainly one, one direction we're looking into this is maybe the area of quantum complexity theory, we you might call it. And indeed, you have this, this classical this big open problem like P versus NP. And basically, the problem boils down to proving that for certain problems, we don't have fast algorithms, solve the problems we solve in practice on computers, they do have fast algorithms, because we can solve them. But there are many more problems we would love to solve. But we just don't know how to do it, because we don't have fast algorithm. So we have to resort to approximation algorithms or sort of algorithms that sometimes don't give an answer at all, are completely wrong. And, and funnily enough, we really don't know a whole lot in classical computer science. And we don't know how to prove good, sort of lower bounds, we call them. Proving that for a certain problem, an algorithm needs to take more than, say, a linear time. And unfortunately, we don't really know how to do that, the best, the best we can do for specific problems is, I think, to prove a lower bound of five times n, so five times the length of the input. But for example, for problems like satisfiability, which is a key problem in the study, or the traveling salesman problem, or there's hundreds and 1000s of others, we believe that there is an exponential lower bound, we believe that takes exponentially many steps to solve instances of length n. But we're not able to prove more than five n for these, for these for this problem. And so there's a huge gap between what we can do and what we believe is true. And what we can prove is true. And so this is sort of a big, a big problem in classical complexity theory that we, we don't know a whole lot. And now the situation only becomes worse when you add Quantum. Because that only makes it in some sense more difficult. And our classical understanding, or lack of understanding is so big that it could, for example be that all quantum computers can be simulated efficiently on a classical computer. This is a world that is possible, although I don't think it's possible, and not many people think it's possible. But it could be the case. So on the other hand, we believe that there are problems that you can solve on a quantum computer, for example, like simulating certain quantum systems, or quantum chemical systems or physical systems. But probably the best example is factoring to to Peter Shor's algorithm, that we believe that that we know you can do efficiently on a quantum computer, but we don't think you can do it on a classical computer. So yeah, so this, this landscape of complexity theory has become much richer, we believe with with the advent of quantum computing, but we still don't know a whole lot there.

Kevin Rowney 24:24
So an even bigger array of even bigger unsolved problems now just yeah,

Harry Buhrman 24:28
yes. So yes, our problems have become bigger. But also more interesting, I would say,

Kevin Rowney 24:34
doubtless, and to what extent do you think it's possible that there could be a future where some of the classical time complexity problems the big famous ones, could be powerfully informed by quantum quantum information science and Quantum Time complexity discovery?

Harry Buhrman 24:50
Oh, yeah, it could, it could very well be that that. That by thinking about these problems in a quantum way, you get you get the night Here on how to solve the classical problem. There are there are actually examples of this. Not only in algorithm design, but also in proof proofs where by using your your quantum machinery and your quantum language, quantum information language, you can prove things that are purely classical have, in a way not nothing to do with Quantum. But you just borrowed the ideas from from the quantum world,

Kevin Rowney 25:28
I guess there was a big result maybe a year or two ago. MIP star equals RE,

Harry Buhrman 25:33
exactly. That's that's sort of the, I guess, by now the most famous example. But there are many others example, were using ideas from quantum information and also classical computer science, I have to say, they were able to prove a beautiful result that says that multi interactive proof systems, I guess we don't have to go into exactly what that means. But again, they were entanglement assisted very much like the model that Richard Cleve came up with. And they showed that this class is equal to the class of RE, which is all the problems that Turing was streaming off, including his halting problem that is not decidable. And that is sort of a beautiful result in in quantum information slash computer science. But the amazing thing I think, that comes out of this is that it implies that a certain conjecture in pure mathematics called Connes embedding conjecture is false. And this is just just amazing, right? It just says something about a deep mathematical problem that mathematicians have thought about for quite some time. And this is now solved by techniques and ideas from quantum information. You know, that paper was a tour de force, just amazing stuff. Yeah, that's amazing. And that paper builds up on a lot of other ideas that were developed before that,

Sebastian Hassinger 27:01
as is always the case. Yeah. Do you think I mean, from that perspective, do you think, Harry that over time, the distinction between classical information theory and quantum information theory will erode? And it'll be just one set of tools that you deploy on, you know, potentially, in terms of applicate, you know, implementation different types of hardware, but you think of them as one sort of set of intellectual tools?

Harry Buhrman 27:27
That is quite, quite likely. I think it's, it shows that it's rich, too. And I think these results also show that it's probably the right way to think about these problems. And yeah, I think this is just, this will be part of our toolkits, just as I mean, there's examples of this, like, you can look at problems in mathematics, with just real, real numbers. And then and then there are, there are beautiful examples where if you go to the complex numbers, suddenly, beautiful results fall out by just using complex numbers. And by now, complex numbers are part of our general toolkit,

Sebastian Hassinger 28:08
right. And they're, they're sort of the native language of qubits. So they're unavoidable when you're thinking about quantum computers.

Harry Buhrman 28:15
Yes, and but then quantum information gives you an even broader Toolkit, which which is useful in its own right. And so I definitely think that it will be part of a more general form of mathematics or general part of mathematics. So it shows

Kevin Rowney 28:31
you and your team are playing in some really rich, interesting territory right now. I'd love to hear more about some of the your team's recent results. I there's this new paper that I think it says archive or is it just a preprint?

Harry Buhrman 28:47
Yes, it should, it should be on the ArXiv. Probably, it probably has appeared when they spoke podcast has appeared, but it has not appeared while recording it. But it should appear somewhere tomorrow or so. Yeah, this is this is something that came out of this co-design world where we were talking and we were also observing the quantum hardware that is currently available. And this, this hardware, unfortunately, is still quite noisy and unstable. And we know that if it at some point is stable enough. So the noise is suppressed enough so that the native implementations are not too noisy, then with the use of error correction and fault tolerance, we can make logical qubits which can be alive for much longer time then then the qubits, the physical qubits that we have currently. But we're not yet there. So this regime is hopefully coming in, hopefully coming soon, but it's not yet there. And so we're currently in this regime, which John Preskill called NISQ, where we have this noisy qubits that we can only use for a very limited amount of time, because when we, when you use them longer, they have completely decoherence. And they're completely random. And so your computation doesn't carry any information anymore. And so we were thinking of what can we do in this particular setting. So you need, you need computations that are that are very fast, because if they take too much time, but the qubits are, are gone, too in unit in computer science lingo, constant depth circuit and the depth or is somehow the time your computation takes and the size is somehow what you can do in parallel. And then, in addition, sort of working towards this advent of error correction and fault tolerant computation, the circuits needs to be able to do emits computation measurements. So the way that error correction works is that you, you have an error correcting code, and then some error has occurred, and you do a partial measurement of your qubits, which tells you what error had has occurred. And then you can do with some feed forwards, while you do some classical computation to figure out what this error was. And then you can correct that error by some feed forward information into your quantum circuit. And then you can do another step of your quantum computation followed, again, by some measurement that measures the error that has occurred now, and so on and so forth. And if you do this right, then the measurements and the errors that occur along the way, don't grow, but they actually shrink, and they stay stay at bay. But we're not yet there. So we cannot use this paradigm yet. So we thought, can you use this maybe for something else for computation, and in particular, for generation of states. And it turns out that, and we're not the first ones, to see this, that indeed, having this mid measurement, mid computation measurements plus classical feed forwards, actually is very useful and can help you solve problems or generate states that if you don't have this, sort of impossible or are impossible, I would say to make. And we call this the luck model, local alternating quantum classical computation, now a cucc. And the paper that has appeared on archive for when this podcast has appeared. It, it actually studies this class, and also shows that there are certain interesting quantum states called the dicky states that they can be generated this way. And so it's a very interesting circuit, or a very interesting scenario, I think to work with. And many of the hardware firms and implementations allow for this mid mid computing,

Sebastian Hassinger 33:18
right? Mid circuit measurements are becoming more commonly implemented in the hardware. Now that's definitely true.

Harry Buhrman 33:26
Yes, and so in that paper, we, we show a couple of examples. And then we had also a paper that actually already appeared a little bit earlier, where we also show that you can do kind of an interesting computer science problem called the list decoding of the of Hadamard codes, which is not something I will do in practice. But I think it's in sort of an interesting problem, that that can be done also by these yellow circuits by these constant depth circuits.

Sebastian Hassinger 33:59
And so the idea basically, here is that you're you're using that mid circuit measurement and classical fan out to essentially extend the amount of computation time, right, you, you cut in before the noisy qubits fall over, grab the information, do something to them, and then feed them back into like, prepare a statement and then go back to the qubits to continue the calculation.

Harry Buhrman 34:25
Yes, exactly. And if you were in the regime where you can do error correction, then this would be doing error correction. But but but that that only works if the errors that you introduce and that the qubits incur, are not too bad, because otherwise you can imagine that this will only make it make things worse noise

Kevin Rowney 34:48
threshold theory,

Sebastian Hassinger 34:49
right and how just from a naive perspective, the first thing I think of is is VQE or QAOA -- existing sort of hybrid approaches. How is it does it differ from a variational approach,

Harry Buhrman 35:01
it differs from that because there you have a circuit that that runs for a short time, then you measure and then you get some you measure the whole thing, not mid-circuit measurement, but at the end. And then the result of that is sort of fed back into a next instantiation of the circuit. Whereas we do partial measurements. So we do a little bit of content. And we measure only, say, a fraction of the qubits, and then do some classical computation and then continue with the qubits that we have not measured. And so it's different in that sense. And that gives you really more power.

Sebastian Hassinger 35:40
That's interesting. And is there, is there a sort of a, I mean, in your mind implementation, would you be able to sort of parallelize it so that you're sort of doing mid circuit measurement from some continuing the computation on others, and then doing mid circuit measurement from those so that you're sort of alternating between sets of qubits on the system?

Harry Buhrman 35:59
Yes, exactly. Wherever also, it's in the alternating between a little bit of quantum computation, a measurement of some of the qubits, a fast classical computation, followed by me feedback of that classical computation into the quantum circuit, and the next step of quantum computation. But the scrambled computations are very, are very short. And also, we do only very few of these alternation so that the whole thing is very short.

Kevin Rowney 36:29
It's such a powerful framework, and it feels like that four layer sandwich that you described in the paper, it feels like that's going to become more already is really the standard architecture at the at the machine level, right for for quantum computation.

Harry Buhrman 36:42
It is because because the computers have to be ready for the for the error correction regime where they have to do exactly this.

Kevin Rowney 36:52
And so really be your result. I think it's got broad generality across the rest of the history of QC, it will help you guide people towards what are appropriate problem solutions for given specific use cases on these these same rigs.

Harry Buhrman 37:07
Yes, and I also hope that we can somehow uncover more tricks than then we and others, I mean, we're not the only ones to look into this at the moment that we have uncovered and that this actually can be useful, even in the regime where there is error correction and fault tolerance, because you can imagine that you could do both, you could use your mid circuit measurements, and so on, both for error correction, and also for some other tricks. As long as it makes things faster. It's good.

Sebastian Hassinger 37:38
Right, right. I mean, that's, that's what sort of the conjures in my mind is sort of the idea of a que que as an accelerator right in in a broader heterogeneous sort of classical and quantum system architecture, as it would be deployed sometime in the future.

Harry Buhrman 37:52
Yes, yeah. But this is sort of even more, sort of closer to the hardware interaction between between classical computation, probably some cooler compiler optimizations. Yes. This I mean, if this is part of the toolkit of quantum computers, then compilers have to can make use of it and optimize the their code. Yes, I haven't had I didn't even think about that. But yes, that's absolutely true that, that you could try to automate this and optimize.

Sebastian Hassinger 38:20
And in terms of the current paper, Did you are you sort of thinking through algorithms that you may be able to implement in at least in toy problems sort of scale to try this this theory out? And implementation?

Harry Buhrman 38:36
Yes, we want to try this out on indeed on, on actual hardware. But but the one of the problems is that you really need this fast classical computation in between. So you really need to talk to the to the real hardware,

Sebastian Hassinger 38:50
just just drop it drop a PC down into the dilution refrigerator and see how it.

Harry Buhrman 38:56
Yeah, so yeah, but yeah, but they need to have this anyhow, when when they do error correction. So that, and it is there actually also in many cases, I talked to a few people doing these experiments, and it's actually there. So yeah, I think that's interesting.

Sebastian Hassinger 39:12
I'm aware of one project. It's called QubiC. It's an open source project of the Lawrence Berkeley National Lab, funded by the DOD and it uses a Xilinx FPGA board for controlling superconducting qubits. And they've implemented mid circuit measurement and feed forward and so there's, there's at least a research platform that that sounds like it's it would be ready to go in terms of trying this out, which is,

Harry Buhrman 39:39
yeah, that's absolutely true. And I think also the IBM computers have IBM Quantum Computers have this as well as others? I think so.

Sebastian Hassinger 39:47
Yeah. And their their roadmap definitely combines classical and quantum in a really sort of intimate embrace. I think their their plan is that for that 100,000 qubit system is that they're calling us Have a classical or a hybrid supercomputer, I think is how they call it.

Harry Buhrman 40:03
Yeah. All right. Indeed. That's the roadmap. Right? For That's right. For the next 10 years or so. That's right. Yeah. Yeah, quite amazing.

Sebastian Hassinger 40:11
It is, it is. It's amazing to see, you know, back to, to reference to touring. I mean, it feels very much like the sort of mid 40s, where you've got the convergence of early stage theoretical, you know, jumps forward. And then these very early stage hardware implementations that start to prove out some of the ideas and then challenge and as you said, that co-design sort of lifecycle kicks in and you get accelerating sort of forward motion as a whole field, which is, I mean, it's amazing to feel like that's happening in real time around us. It's one of the most exciting things to me.

Harry Buhrman 40:47
Yeah, it is amazing. And I'm actually also very much amazed by the fact that when I started in this in this field in the sort of the mid late 90s, it was considered very esoteric and beautiful, but but esoteric, and probably wouldn't lead to anything practical fields. And actually, I also thought it was like that, I was just thinking, Okay, this is just beautiful, and we're just having some fun. And then in a few years, people will discover that it's not can't work possibly, or we will lose interest and we'll do something else.

Kevin Rowney 41:24
It'll it'll start it is life of the mind. And now it's Wow, so many applications

Harry Buhrman 41:29
it has the hasn't stopped and it has just increased and increased and, and now it's just, it's just mind boggling how big it is, and how much attention we get and how much funding goes goes into our field. It's really amazing. There still could

Sebastian Hassinger 41:42
be more though Harry, remember, there could be more funding.

Harry Buhrman 41:47
Probably there should be if you want to make it, make it really work. Yeah. And also, like, big, big companies are very interested in this not only for building computers, quantum computers, but also figuring out whether it is useful for from a software point of view, if bear based companies

Kevin Rowney 42:07
and entire nation states. I mean, it's it's a high profile of people.

Harry Buhrman 42:14
So it's very important, we do the right thing. And one, of course, point of worry is that it's extremely hyped. So you also read a lot of nonsense everywhere in the newspapers, and you see it on the internet. And it's very, very important that we keep telling the honest story. It's not the it's not a magic wand that solves every problem exponentially faster, which you sometimes see written. But it's also not something that has no potential, right. It's super interesting. And it has quite some potential, but it will not solve world world. World hunger problems.

Sebastian Hassinger 42:57
Right, right. Well, it's so challenging because it's in a way it's it's trying to describe, I mean, to try to describe what quantum may be helpful for requires explaining what classical computing is not good at, which is kind of invisible to the average user of computers. When we do all this stuff with with classical computing. That's sort of part of the fabric of everyday life, you have to sort of explain like, Yeah, but there's this other set of problems that we're not able to do with classical computers that may actually be tractable with quantum computers. And that's where the promise lies. And it's a challenging communication goal, I think.

Harry Buhrman 43:32
Yeah. Although it's most likely still the case that most of these intractable problems also remain intractable for quantum computers.

Sebastian Hassinger 43:42
You're not supposed to say that, Harry, that's deflating the bubble.

Harry Buhrman 43:48
We have I agree. Totally. On the on the story here.

Kevin Rowney 43:52
Yeah, we really like that sober view. I mean, there's there's so much potential, but also, there's just a lot of crazy hype, I think gateways to irrational speculation. So thank you for helping introduce some clarity.

Harry Buhrman 44:04
Yes. And it's indeed just a very special set of problems for which we expect some advantage. And it's this set of problems that we have to focus on.

Kevin Rowney 44:15
So I wonder, Harry, if could you give us some insight of what what's the next big frontier for you and your group? I mean, this is a great result. You just got out. There must be more down the same pathway. I mean, that this was such a rich, rich domain of investigation.

Harry Buhrman 44:30
Yeah, so I think actually, everywhere you look, it's interesting. So you can any it's like, like a kid in a candy store. Right? Every everywhere you go, it's fantastic. And you want to go there.

Sebastian Hassinger 44:43
That's the advantage of having a job where you're attracted to complexity, the more complex things get great.

Harry Buhrman 44:50
No, but it's really true. It's sort of so many so many directions that you can go to, that you can go into and that are interesting. That's yeah, so there's there's many, many, many ways to go. I particularly am very interested in Well, we talked about this, this, this very shallow circuits and what you can do with them. But another another project that I've been working on is trying to figure out which problems cannot have a quantum speed up or can hardly have a quantum speed up. And I think that's also important because we have to know where to look for problems that that do have a speed up. And in order to do that, you have to also know where not to look. And so this is also an area which is called Quantum fine grained complexity, where we're looking at the actual real complexity bounds for quantum algorithms compared to classical algorithms. And under a reasonable hypothesis, you can say quite a lot there. I think this is a very interesting a field that needs to be further developed. And always you have to look at a quantum algorithm and how fast it is you have to compare it to the best and maybe best known classical algorithm, which is also not not always the case. So this this sort of interaction between what do classical computer scientists have developed as best algorithm, compared to what we quantum computer scientists develop this, this dialogue has to be there, and it's super important. And you also have to, to be defeated at some point by by the classical guys, right? Because they, they're so clever. And they might, they might do something that the quantum computer cannot do better. So this is an area where I'm very interested in and I'm also pursuing at the moment. But then there's, there's this beautiful other areas like I'm working on on this thing called quantum cryptography, it's quantum position verification, where you want to prove that you are at a certain location on Earth, I saw those papers, it's just fascinating work and amazing stuff. And then they're they're really, that's really very interesting problem that maybe you could even could even have some practical value. But the beautiful thing is that this this, these questions that come out of those investigations, they tie in immediately to complexity theory again, and you can, for example, show that if you prove that a certain protocol is secure, then you actually solve some, some big open classical complexity problems.

Sebastian Hassinger 47:39
So generalizing from a specific essentially finding a specific solution. And then learning generally how to generalize out of that solution for class of problems,

Harry Buhrman 47:49
to sort of come up with a protocol and improving the protocol is secure in a quantum way, would would imply things for for classical complexity theory, or it implies things for classical cryptography. Also, they're sort of interesting ties. And the latest thing is that it somehow has connections with with this, this this theory called AdS/CFT correspondence which, which is something that that the string theorists developed and are thinking about, we've had

Kevin Rowney 48:25
some guests on that same topic, incredibly deep, powerful stuff. And this

Harry Buhrman 48:29
now somehow connects also to this this possessing verification tasks and quantum algorithms. And so yeah, it's just fantastic. Everywhere you look, there's there's something super interesting popping up. So

Sebastian Hassinger 48:43
position verification based on quantum computation, or quantum communication or quantum cryptography. I didn't read the paper, I apologize.

Harry Buhrman 48:55
The problem is that you want to prove that you were at this or that you are at a certain location, say on Earth. And you do this by interacting with some verified, verifiers, that trusted verifiers and you can show that if this communication is just classical, then you cannot be you cannot have secure protocols. But if this communication is quantum, then there are some some possibilities of having secure protocols under reasonable assumptions. Yeah, so the important thing is here that you you can communicate quantumly and, and the beautiful thing is that indeed, there are now experiments, right, or even quantum networks that can run this, these protocols.

Sebastian Hassinger 49:44
In fact, some in the Netherlands I think are particularly advanced

Harry Buhrman 49:48
by some in the Netherlands. Yes, absolutely. Which is also amazing that the protocols that were developed in the in the in the 90s and early 2000s Now can be actually run on actual hardware.

Sebastian Hassinger 50:00
Yeah, Ken Brown from Duke University said to us or to me once every year, people say we can't possibly make this stuff work. And the results improved by another order of magnitude is like, if it can't work I'd like to love. I'd love to know just right now so we can stop. But it keeps improving. So we keep working at it.

Harry Buhrman 50:20
Yeah, yeah. Yeah, that's, that's, it's really beautiful to to see that.

Sebastian Hassinger 50:25
It's terrific. So before we let you go, this has been super interesting. I just wanted to comment on one thing that I found really interesting. You got to extremely long research history. There's tons and tons of papers you've been part of, which is and we've talked about a bunch of, of areas you've been involved in. But I wanted to just point out, you also seem to have a knack for coming up with really funny and interesting titles for papers. And I just wanted to list off my three favorite and get your your view on so I'm sorry, Dave, I'm afraid I can't do that. That's a great. Yeah. Most recently, a qubit a coin and an advice string walk into a relational problem was Scott Aronson. I mean, admittedly, these are physicists and mathematicians jokes, but still good jokes.

Harry Buhrman 51:14
I think that one was mostly due to Scott.

Sebastian Hassinger 51:16
Scott. It does sound like Scott. Yeah. And my favorite, though, is the Pirandello reference six hypotheses in search of a theorem. Terrific. Really good.

Harry Buhrman 51:27
Yeah. So that last one actually got this. Other honor, honorable mention, in the Journal of Irreproducible Results

Sebastian Hassinger 51:36
oh nice! high honor.

Kevin Rowney 51:41
Maybe you could have scored an ignoble prize or something off.

Harry Buhrman 51:45
That didn't but it said the journal that comes in it with the ignoble prices. And but it's a real, it's a real paper. I mean, it's it's science and it's solid. Yes, it's about it's about six hypotheses. Indeed, one of them is P is equal to NP, which I mean, all the hypotheses we believe are false, but we wanted to combine them. And actually the theorem, we wanted this, that they're all equivalent, but we weren't able to prove that. So that's the sixth hypothesis that are in search of a theorem indeed, but Pirandello play.

Sebastian Hassinger 52:22
Yeah, it's a favorite of mine. So I quite enjoyed that. So that's terrific, Harry. That's it's been super, super interesting talking with you. We really appreciate your time. All very interesting work and fascinating topics. So thank you so much.

Kevin Rowney 52:38
Thank you so much for having me

Harry Buhrman 52:39
and keep up the good job of having a nice podcast and thank you. Very nice. Thanks. Take care.

Kevin Rowney 52:51
Thanks. Bye Bye.

Wow, Sebastian, that was so fun, really cool. Guest. Yeah. I wonder how do we come across

Sebastian Hassinger 53:45
the professor. I've crossed paths with him a couple of times professionally. And then I met him at an event in Delft when I was in the Netherlands in May. And he actually no, that's not true. I saw him in Paris first. He presented some of the or previewed some of the results that he was going to publish in that paper the LAQCC system and I got very excited and immediately started pursuing him as a podcast guest. It took us until now just with summer holidays and everything scheduling to make it happen. It stuff.

Kevin Rowney 54:18
Yeah, I guess that that paper now up an archive is called ultra fast quantum circuits for quantum state preparation. We'll put a link Yes, in the notes, right. That's very good. But you know, I wait, fun dialogue around that I what I really love is how he focused so powerfully on you know, basically trying to snuff out the unrealistic claims right about what QC can do. I mean, he's like embracing, like, we tried to do as much as possible, embracing the excitement of the potential of this, but still temperate. That excitement with sober expectations. Chris, the hype is kind of wild right now.

Sebastian Hassinger 54:53
Well, and in fact, he's even focusing now on fine grained quantum complexity, which is looking sort of for the next given space, right, the things that it will not help for, which I think is super helpful. Yeah, the progression of the field.

Kevin Rowney 55:05
Yeah, realistic upper bounds and lower bounds on what QC can do. It was kind of notable also, he went way out of his way to point out that, you know, really many of the NP complete problems out there that we know as valuable targets, and there's no efficient algorithm to do them. They'll still stand hard as difficult problems. These are the era of QC amulets, let's get let's get real here. I mean, in a sense, the saying that the time complexity hierarchy we've known in the past is going to be much, much more rich and complex than we've studied. But it's not going to just collapse. Right,

Sebastian Hassinger 55:37
right. Right. Yeah. No magic bullet. Yeah. Although it is also really, I thought was really fascinating thinking about or talking about how the tools from quantum information theory are sort of merging with complexity theory with classical information theory, and just making for a richer toolset for thinking about information science as a whole instead of distinction between quantum information and classical information.

Kevin Rowney 56:02
So agree, I mean, you could even imagine quantum information theory sometime in the near future, becoming into a core part of the canon, right of computer science, right? These tools are so valuable. That's right. It's not just for physicists anymore. Right.

Sebastian Hassinger 56:17
Right. And with anybody, like Harry, who's, you know, as he said, started in sort of the mid 90s. I think we both share that kind of wonder, a career where you start off with something that's, you know, so esoteric and so impossible, it's just sort of like, as you said, the sort of something that just lives in the in the mind, and then to actually be at this stage in his career, seeing real world implementations of the stuff mature and get closer and closer to real productive technologies. It's, it's an incredible time,

Kevin Rowney 56:52
really, is the arc of this of the subject of going from wildly esoteric, like just deep theory towards wow, I mean, forms of implications for nation states, large corporations, venture capital. That's right. It's a fascinating story,

Sebastian Hassinger 57:08
which feeds sometimes the the overhyping of the cycle of life. All right. Excellent. Well, thank you so much for joining us this episode. We'll be back soon with another exciting interview in the new quantum era. So fun. Thanks for your time.

Kevin Rowney 57:30
Okay, that's it for this episode of The New quantum era, a podcast by Sebastian Hassinger. And Kevin Roni, our cool theme music was composed and played by Omar Costa Homido. production work was done by our wonderful team over at Podfly. If you're at all like us and enjoy this rich, deep and interesting topic, please subscribe to our podcast on whichever platform you may stream from. And even consider, if you like what you've heard today, reviewing us on iTunes, and or mentioning us on your preferred social media platforms. We're just trying to get the word out on this fascinating topic and would really appreciate your help spreading the word and building community. Thank you so much for your time.