Episode Transcript
(Intro Music Starts)
SH: Hello it is your host Sam Hansen and I am excited to welcome you back to Carry the Two, the podcast about how math and statistics impact the world around us from the Institute for Mathematical and Statistical Innovation. While we’re in between our more in-depth seasons, we like to bring you something a little different in mini-season format. And for this mini season, we are going to highlight some of the amazing researchers who have presented at IMSI over the past year. Our fourth guest is
KM: My name is Kunal Marwaha. I'm a PhD student at the University of Chicago. I study quantum computing.
SH: Kunal joined us at IMSI for a workshop on The Power of Near-Term Quantum Experiments where he presented a talk titled On the promise of quantum advantage for classical optimization. So, without further ado let’s get into my conversation with Kunal Marwaha
(Intro music ends)
SH: Let's start talking about quantum computing, specifically quantum advantage for classical optimization. And so my first question here is what do you mean by optimization?
KM: Optimization to me is a very general idea. It gets used all over the place. Usually when people are trying to make something better with the same amount of resource or do the same thing with less amount of resource, I would consider that some kind of optimization.
I mean, this could be as something about where you put the subway stops or how can I invest in the right stocks to make me the most money or where do I put telephone poles to get an efficient communication. These are all optimization problems in my head.
SH: Yeah, that definitely makes sense. And then from the more sort of like mathematical computer science-y sort of thing when you're talking about optimization there, is there something specific you're generally trying to optimize?
KM: In computer science, we have this like language around optimization. It turns out a lot of optimization problems are related to each other. So you can write one optimization problem down and study it. And it's related to a whole bunch of other ones.
The one I study is called constraint satisfaction. So usually, you might have a bunch of different inputs, options, and they might be plus or minus one variabled options. And you have a bunch of constraints. And you want to find that the option that satisfies the most number of constraints is possible.
So it's called constraint satisfaction because you're trying to see if there's an input or an option that satisfies as many constraints as possible, or maybe even all of them.
SH: So now the really fun question, what is quantum computing?
KM: Yeah, that's a great question.
So quantum computers are a new type of machine. Really, we're trying to see if we can do computing using the atoms and the physics of the universe that atoms use. And this kind of stuff is not like zeros and ones. It's something to do with how atoms behave. And we have some evidence that using this kind of physics, we can solve problems that regular CPUs and GPUs can't. But it's not clear what the realm of their possibilities are.
And so what I do is to try to figure out what else can we do with these new types of machines that are using atoms and moving atoms around and using the quantum mechanical structure behind it to solve problems? And what kinds of problems can we solve?
SH: So it's that trying to figure out what problems you're trying to solve, that's why this sort of study is important beyond helping people write dissertations?
KM: (Laughs) Yeah, I think, I mean, to be honest, I think these new types of machines have one special cybersecurity application. And that is going to keep a lot of the money going for a long time until we have these machines.
I would say quantum computing is very much in its infancy. And we have these machines that are just out of the science project stage. But as we're going to build them, there's a lot of excitement about anything else we can use them for, including optimization.
SH: So what is that cybersecurity thing that's going to keep the money flowing?
KM: Sure. So there's one thing we've known for over 30 years. Quantum computing can do a special type of math problem better than any computer that we can write down.
And this math problem is sort of simple. It's take a big number and tell me what the prime factors are. So if I give you a number 10, you can say, well, it's two times five. This math problem turns out to be really hard for a computer. And we don't totally understand why, but we've tried really hard. And we've designed some of our crypto systems, some of our security systems, based on this question, is a number, if it's a big number, tell me it's prime factors.
We just assume that it's a hard problem.
It turns out that quantum computers can solve that problem when they're big enough, not today, but they can solve that problem. And so as a result, we got to we have to change a lot of our crypto systems to be quantum proof, so to speak.
SH: I mean, that sounds like a fascinating topic, but we are here to talk about optimization today. So what what is what is the term quantum advantage mean? And in particular, what does it mean in the optimization context?
KM: To me, I try to think about like, people use optimization to solve their problem as best they can. They might have some some resource like or like some money or some options they can choose. And they're trying to make the best choice that gets them the best return.
And to me, quantum advantage is, is there a way that using a quantum computer, some algorithm that runs on a quantum computer can help you get a better return than any type of classical machine. And so there are different ways you can specify this, you could say, in this constraint satisfaction example, I gave you, it could be that maybe it satisfies more constraints than any regular classical algorithm could. Or maybe it can get there faster.
But for me, in particular, I've been trying to create this kind of theory test bed to say, well, okay, let's let's set up a contest for these kinds of optimization problems. Will a classical algorithm do better? Or will a quantum algorithm do better?
If a quantum algorithm does better, I would call that advantage.
SH: That leads right to the next question I have for you, which is, what were you testing? Like what was this test bed that you were you were working with?
KM: One thing that hangs up computer science researchers a lot is, what does it mean for a optimization problem to be hard? And what you might have heard of these terms like P and NP. And we know that problems like optimization or these constraint satisfaction, are NP hard. What that means is in the worst case, there's at least one setup that is super duper hard to solve.
For me, I always found that a little unsatisfying, because in practice, you don't care that, you know, in the worst case that it's hard to solve, you care about your use case. Is optimization hard for me and my problem. For example, training in neural net is NP hard. So that doesn't stop a lot of companies from doing that today.
So for me, I study random optimization problems. So I might take a constraint satisfaction problem, and I might randomize a bunch of things in it. So one example I'll give you is, let's say I have a big network, we call the computer science, we call them graphs. And I want to see, is there a way to move the nodes on the on the network to two sides, such that the number of edges that cross the two the two different parts is as big as possible. So I'll call this the maximum cut problem.
And this is a kind of optimization, because depending on which side each node is on, I might be able to cut more or less edges. But instead of trying to come up with the worst, the hardest possible problem for this, I'll just say, pick a random network. Just give me all possible networks and pick one at random. And can a classical algorithm or quantum algorithm solve this problem? How well can it do.
SH: With that problem with this max cut problem? How well can the classical algorithms, the ones that we've known about for a while, and we can run on our existing machines? How well do they do?
KM: So this is actually, I thought that's what I found about this research was very exciting is, it turns out that we didn't know before I started this research what the best algorithm was. Because this is a super hard problem. We had some ideas that classical algorithms could get to a certain number.
And there was a paper that I was a part of, where we showed that a quantum algorithm could do better than that number. And so it looked like maybe there was a source of advantage that these quantum computers had somehow, were able to solve these random optimization problems better. How it wasn't super clear, but we could at least write down that they were.
But what happened was, these random optimization problems, even if finding the best possible solution is really hard, there are new techniques coming out of statistics that use classical algorithms to find nearly optimal solutions. So maybe I can't find the best one, but I can find something super duper close. And we were able to come up with some classical algorithms that got all the way almost to optimal.
It turns out that even though in the worst case, optimization is really hard to solve, for this max cut, for random max cut, at least over the instances I was looking at, there are actually classical algorithms that get super close to the optimum. And so there really isn't a source of quantum advantage here.
(Ad music starts)
If you're getting a lot out of the research that we discuss on this show, there's another University of Chicago podcast network show that you should check out. It's called Capital-isn't. This podcast uses the latest economic thinking to zero in on the ways that capitalism is, and more often isn't, working today. From the morality of a wealth tax, to how to reboot healthcare, to who really benefits from ESG, capital-isn't clearly explains how capitalism can go wrong and what we can do about it. Listen to Capitalisn’t, part of the University of Chicago Podcast Network.
(Ad music ends)
SH: Even though there is not a source of quantum advantage for random maxcut, could you tell me a little bit about what these quantum algorithms sort of look like, at least as far as we can actually understand what's going on?
KM: So there's a couple approaches to using quantum computers to solve optimization.
The way a quantum computer will work, it needs to put in a system, like a physical system, and it needs to turn the optimization problem into a physical system, and then move somehow along this physical system. Why I'm calling it physical is because that quantum computers are built out of atoms, or light beams, or something where you're using the quantum mechanics inside.
So we might take this maximum cut problem, and we might make each network a single Qbit, like a single bit on the computer, the quantum computer, and then we'll use some physical process to move around the state space to try to solve the problem.
So some of the earliest quantum computers made by D-Wave and others use this idea of quantum annealing. It's as if you had a real material, and you would heat it up, cool it down, heat it up, cool it down, and maybe you would get to the perfect solution at the end of the day.
And so we use some techniques, one very popular technique is called the QAOA, or the quantum approximate optimization algorithm. And this is built off some of the same ideas as annealing, but instead of heating it up and cooling it down, it's using some more step this way, step this way, step this way, but still using the physical system as its base.
SH: And so you were able to show that at least before you and your team did your research, that there was a version of this QAOA that did do better than the sort of dominant max-cut algorithm of the time. One thing that really came up in my head was a different type of optimization problem. And that is, what about the things like compute time and cost? With quantum, like even if you can get slightly some percentage better in the optimization of the constraints, are you really not optimizing for time?
KM: So all we were able to show is that at least for, you know, in research there is all these sorts of caveats, but at least in our theoretical test bed, the quantum algorithms are not going to get more constraints. They're not going to get a higher value on this problem. But it doesn't mean they won't get to the same place faster.
And so some new researchers trying to poke at this, maybe a quantum computer can solve your problem as good as the classical algorithm, but twice as fast or quadratically fast or something like that. And then it will depend. You know, maybe that speedup is actually good enough that a company would want to use this quantum computer instead of a regular computer.
The downside though is that's going to really depend on how expensive and how big the computers get. And it can be very hard to probe these kinds of questions before the computers are built. And so one thing that's challenging about our work is trying to stay close to reality, saying this is what we think a quantum computer is going to be good for.
But we don't have them. You know, we don't have them in a big enough way where they're going to be very useful. So we have to actually make a lot of guesses. Like hopefully it'll be useful.
I chose a version of randomness, like a random optimization problem. But there might be specialized types of optimization problems where they're still useful. And some of the recent work coming out in conferences is that maybe certain types of optimization problems, the quantum computer can take advantage of certain symmetries in the optimization problem. And those might have a super fast speedup. Might have a lot more advantage.
But it's still kind of, it's an open question.
SH: When I was watching your talk, something came up that I've never heard of before. So I really need to ask, what does it mean to obstruct an algorithm?
KM: Oh, yeah.
So obstructing an algorithm is kind of a funny word, right? So it's not like there's a some person there saying, Hey, you can't go this way. What we were trying to show is in these general optimization problems, some algorithms will succeed and some will fail. And when I say obstruct, I'm trying to look for some reason why algorithms fail.
So not in MaxCut, but in certain other kinds of constraint satisfaction problems, there are structures in the problem itself. For example, one thing that happens in these other constraint satisfaction problems is that the right answer, even these, you know, near optimal answers are hiding in like needles in a haystack. And if you change the problem a little bit, the needles completely move. They're really devious.
And it's not anything like I would say the problem isn't mischievous. I, I don't consider it animate. But it's like a curious fact about that the real answer we're looking for is needles in a haystack, and they're moving around randomly really sensitive to the initial conditions. And if you have a problem that has this behavior, some algorithms that might just say, Okay, look on the left side, look on the right side, zoom in, look on the left side, look on the right side, they're going to take a long time.
And so we were using techniques that if the problem had this property, then certain algorithms would get stuck. And there's this really nice idea that said, even for random optimization problems, with a certain needle in a haystack property, both classical algorithms and quantum algorithms are going to get stuck. So sometimes classical algorithms can't solve optimization exactly, but in those same cases, some of our quantum algorithms also get stuck. And so in these contests we were setting up, we finally had a region where, okay, classical algorithms can't get to the optimum.
But then it was like, Oh, no, quantum QAOA can't get to the optimum either. It's telling you something about, you know, I was calling that obstructing the algorithms, it's some natural property of the problem. That's saying, Hey, you know, I'm actually really sneaky or you know, you can't find the answer now.
SH: So essentially, problems that fit that traditional mathematical sensitivity to initial conditions definition of chaotic.
KM: That's a great way to put it. Yeah, there's some chaos. I don't know a lot of the formal language here, but the chaotic property of the, where the solutions are is exactly the right metaphor you should have in your head.
SH: I have a couple last questions for you. The first one I'm going, I’m going to ask you to take out your crystal ball. I would love to know where you sort of think the whole general quantum computing space is going to go. Like clearly there's money, clearly there's a taste for it. But, do you think that we're going to start to really see this technology take off, that companies start to make into things that people can touch and use soon? Or do you think we still have a lot more theoretical work ahead ?
KM: Yeah, that's a good question.
I would say right now, the distance between us and a real life quantum computer that we can use every day is limited by a lot of engineering challenges. Right now we have problems of making them big enough that the computation doesn't get destroyed just by being in air, being, being outside, you know, there's so many quantum phenomena happening all the time that sometimes our computations get messed up. And solving these problems is a, is a huge engineering challenge. And I would say that there's still a lot of work to be done.
There's been significant milestones that have been happening over the past several years. But I would argue it's still going to be a while before we see any big use case, like even the cybersecurity use case is a long way out. Now, on the other hand, we're not totally sure what else we can use the quantum computer for. And that is, I think, a big challenge that as a theorist, we should pay attention to.
There are signals of quantum advantage in these various places, like in optimization. But right now, we don't totally know what else they'll be good for that has a lot of economic relevance that will hopefully help people's lives. And I would say we still have quite a bit of time, I would say at least 10 years to really figure out what's going on.
SH: Thank you for being willing to prognosticate there. And, and my other question is, what did it sort of mean to have this, this workshop at IMSI? Like, was it useful? Have you seen, have you, did you like meet people that was great to meet? Do you have future collaborations maybe coming out of it? Just just a little bit of a taste of what sort of impact it was to be able to come to IMSI and take part?
KM: Yeah, IMSI is, it was a really cool opportunity. Just everyone there was interested in roughly the same kinds of questions. I would say very theoretical people, but they're interested in what a quantum computer could do. Where is advantage? What is special about the quantum computer that makes it powerful or more powerful than a regular machine? And the people there I've met, I like had some new ideas and I'm still talking to them now. And we'll see where it goes. But there's a lot to explore.
SH: Well, thank you so much for your time and coming to talk to me about all of this.
KM: Thank you.
(Outro music starts)
SH: As always, don’t forget to check out our show notes in the podcast description for more about Kunal’s research and to watch his talk.
And if you like the podcast, please make sure to follow, subscribe, or like the show in your podcast app of choice
It is the best way to make sure you hear all of the episodes of Carry the Two
For more on the math research being shared at IMSI, be sure to check us out online at our homepage: IMSI dot institute. That is I M S I dot institute. We’re also on Blueskey at imsi.institute, twitter at IMSI underscore institute, as well as instagram at IMSI dot institute!
Do you have any mathematical or statistical questions? Maybe you have an idea for a story on how mathematics and statistics connects with the world around us.
Send us an email with your idea!
You can send these ideas, your feedback, and more to sam AT IMSI dot institute. That’s S A M at I M S I dot institute.
We also like to thank Blue Dot Sessions for our Music.
Lastly, Carry the Two is made possible by the Institute for Mathematical and Statistical Innovation, located on the gorgeous campus of the University of Chicago. We are supported by the National Science Foundation and the University of Chicago.
