Transcription
Seminar series, just depending on where you are tuning in from. My name is Olivia Lanes from IBM Quantum. I am going to be hosting today's seminar. We have a great speaker lined up for you, and I'm really excited to introduce her here today. Uh, her name is Priya. She is a post-doctoral researcher in computer science at the University of Victoria, where she completed her PhD in 2025. Priya's research focuses on hybrid quantum-classical algorithms for constrained combinatorial optimization, quantum software development, and the design of quantum education resources for high school and university students. She has worked as a staff engineer at Oracle and completed internships at the British Columbia Public Service, Xanadu Quantum Technologies, and Institute Quantique at the University of Sherbrooke, where she completed with the Bank of Canada on projects in financial optimization. Beyond research, Priya enjoys sharing her passion for quantum computing through teaching and outreach initiatives. So, it is my pleasure to introduce and bring up Priya to the stage right here. She's going to give a wonderful talk on optimization. And just remember that if you are interested in any of the other talks and any of these topics, we do these seminars on the last Friday of every month right here on the Kisskit YouTube channel at 12 Eastern. So without further ado, let me bring Priya to the stage.
>> Hi Priya. Thank you so much for being here with us today.
>> Hi. Uh, I'm excited to give this presentation. Um, and just before that, uh, it says here that my recording has stopped and I need to refresh. So, uh, maybe I'm just going to click that because it's going to refresh the page again. Okay.
>> Okay. Yeah.
>> Okay. So, yeah, for real this time.
>> Okay. Um, do I start sharing my screen now?
>> Yep. Take it away. Stage is yours. I'm just going to mute myself in the background here, but I'll be here. And, um, please feel free to ask questions throughout in the chat, although we will address them and wait until the end. All right. Take it away, Priya.
>> Yep. All right. Uh, hello everyone. Um, today I will be talking about uh, some of the research work that we've been doing over the past um, couple of years, uh, which is about um, constrained combinatorial optimization problems and um, a path towards quantum advantage for such kind of problems. Um, and so in this talk um, we're going to be starting with some motivation on why it's useful to solve these problems. Um, and then go into uh, a running example um, which is vertex cover. Um, for this problem, we are going to show uh, an end-to-end classical quantum pipeline that we use to solve, and within this pipeline, one of the more um, the core components is our um, scoop framework, which um, which converts constrained combinatorial problems into unconstrained ones, um, which means that they are quantum ready now. Um, and then once we have all of that um, I'm going to show some uh, results on uh, the IBM quantum hardware, IBM Qubec, and these would be from the quantum optimization benchmarking library, as well as some uh, real-world instances. Um, all right, so let's get started.
>> Uh, quantum processing units have um, the potential to accelerate tasks in um, optimization, simulation, uh, machine learning, beyond what is possible with classical computers. Um, and because of its probabilistic nature, um, quantum algorithms can explore a wide range of possibilities, um, including optimal solutions as well as uh, near-optimal high-quality solutions. And in certain real-world optimization and um, even multi-objective problems, finding an exact optimal might be too costly or might be not possible. And um, so there's a possibility for quantum to provide um, us with high-quality near-optimal solutions that are often good enough. And so um, we we know that our current quantum hardware has a few limitations in terms of um, noise and decoherence. Um, and then given that we have these limitations, but given that we have this very powerful uh, framework with a probabilistic nature, we know that quantum computing serves as a valuable testbed for scientific discovery. And so it offers capabilities that go beyond classical approximation methods um, which only provide uh, limited guarantees. And so within this uh, framework of combinatorial optimization problems um, if you see on um, the picture on the top there, which is having the unconstrained cop or combinatorial optimization problem and a constrained combinatorial optimization problem. Um, essentially in an unconstrained one, you're just choosing an optimal item from a finite set of items. Whereas in a constrained problem, uh, you're still choosing an optimal item, but um, you have to um, obey some constraints um, for feasibility, and so it it um, adds a layer of complexity uh, to a problem.
>> So um, the sort of uh, state-of-the-art practical algorithm that we use for solving combinatorial problems is QAOA or the quantum approximate optimization algorithm, which we will also be using in um, our talk today. Um, although this can be swapped out with something else if there's a better technique, then you can in our classical quantum classical pipeline have this other um, um, other technique also. But we're going to be using QAOA, and essentially what QAOA has is a cost operator which encodes our problem um, and the optimal basically is encoded by um, the state with the lowest eigenvalue. Um, and this is um, mixed up with the mixer operator which explores the solution space. And so you have these alternating layers um, where the deeper the circuit is or the more the number of layers are, the better chance you get to an optimal um, and and the the goal is that we would like to minimize the expectation value of this cost operator here. So this is quantum classical in nature. Uh, there is a quantum circuit and there is a classical optimizer that um, tunes parameters. Um, and so one of the things with QAOA is that it's it's widely studied, but it is widely studied for u-Max cut, which is an unconstrained problem. Um, and the cost Hamiltonian for this Max cut is encoded using a QUBO or a quadratic unconstrained binary optimization problem. However, when we look at constrained combinatorial problems, not all subsets of solutions are feasible, which means that constraints also need to be encoded in our cost Hamiltonian or into our cost function. Um, and the challenge we have is that QAOA produces infeasible solutions also with a non-zero probability. So based on how we encode our constraints, there is a chance, um, there's a quite u, good likelihood that we end up with an infeasible solution, which is not good. And so how do we tackle this challenge?
>> Um, and we know that uh, uh, combinatorial optimization problems are hard. Um, it's even worse including constraints, and so practical quantum advantage is difficult to demonstrate in these um, problems in end-to-end settings, for example, in real-world scenarios where you require model pro, uh, modeling the problem and modeling the constraints, orchestration, working within the hardware that we have, and some pro, post-processing if we need that. Um, and and in all of these optimization tasks um, we also require high-quality candidate solutions, not just the optimal. Um, and and we know so far that uh, quantum execution naturally produces um, uh, distributions over candidate solutions. So um, in this distribution, you would want that most of your solutions are good, if not optimal. Um, and and and that's what um, this talk is mostly going to be about: how do we get to those very good solutions?
>> And so thinking about um, intractable problems in practice, um, we know that many combinatorial problems are NP-hard or they're classically intractable. Um, however, uh, NP-hardness, uh, what it establishes is is only worst-case intractability. So, this doesn't mean that every instance of a problem that you have is going to be hard to solve. For example, there are small instances um, or instances with certain favorable structure um, that we know can be solved exactly using classical methods, either by brute force or um, by some um, some other algorithm. It may be uh, solved exactly based on the structure that we have. Uh, but there are some large instances or structurally unfavorable instances that remain resistant to classical methods. Um, and by classical methods, I mean classical brute-force exact methods. Uh, we may have classical approximation algorithms, but again, those are not going to give us um, um, they are only going to have an approximation guarantee, and it might not result in an optimal. Um, and so given that we have this variance of um, different kinds of instances, um, one practical consequence for us to use quantum is to not actually um, um, give every instance to quantum, but basically exhaust what classical methods can solve quickly and exactly, and then offload the remaining difficulty to quantum hardware. And then if there is any uh, feasibility requirements to be met, then that can be post-processed classically. So um, basically instead of uh, if I have a problem with 500 nodes, but maybe the harder part of this is only about 30 or 40 nodes um, and so I exhaust as much as I can classically and then offload the remaining to quantum hardware.
>> And so given this um, this practical consequence, uh, we know that um, it's likely that quantum advantage is likely to emerge from uh, tightly integrated hybrid workflows, and this would include both classical resources as well as quantum resources. Um, and so in our work, we have this uh, broad experimental workflow that partitions the workload um, with classical pre-processing, followed by quantum optimization, followed by classical post-processing. Um, but it's not just taking um, a problem and then um, running it through, but also thinking about um, how can we encode these problems better. So in this talk, we have this classical quantum pipeline, but we also have um, the scoop framework, which uh, encodes the problems better, and then also our results and interpretation um, for the case studies that we ran through.
>> So, coming to our example um, which we'll be uh, using throughout this presentation, it's vertex cover. Um, it's a famous constrained combinatorial optimization problem. Um, in classical computing, there's been a lot of research. Um, and so this um, was naturally the example that um, I went with uh, here. So, a vertex cover is a subset of vertices such that every edge shares at least one vertex um, with this subset. Okay. And uh, the minimum vertex cover problem is an NP-hard problem. Um, and it can be encoded as a quadratically unconstrained binary optimization problem. Um, so here, unlike an unconstrained, like a truly unconstrained problem, you do have constraints, and the constraint here is that um, the subset of vertices that you choose must actually cover all of the edges. And so if you're not covering an edge, then that's an infeasible solution, which you would want to penalize. Um, and so if you look at um, this Hamiltonian over here, um, the red term um, penalizes any edge that is left uncovered, and the second term counts the number of vertices that are included in the cover. Um, and the goal is basically to minimize the sum of both of these. Um, and so obviously, if there is an edge that is left uncovered, then um, you have a large red term coming up, which um, which your classical optimizer might want to avoid. Uh, but given that we have two to the N different bit strings, it's not the case that you avoid these infeasible solutions every time. Um, and so we'll see that here where um, we're choosing A and B. A and B can be um, any two different values. Usually A is greater than B because you want to penalize the um, um, infeasible solutions. Um, and so here we have um, in the in the chart, we have penalty weights where we have started with A=3 and B=2, and also A=4 and B=2. And then the row, you can see is um, the first two solutions are um, with the the nodes colored in red are the nodes chosen for the vertex cover, and we know that these two are feasible, the first two, because um, they have um, they've covered all of the edges. Um, and the next two, the last two over here are infeasible because um, uh, 01 or 01 and 45 have not been covered in these two cases. If you look at the cost um, of these solutions, we can see um, when A=3 and B=2, an infeasible solution actually has a better cost than a feasible solution. Right? So we do need to bump up A, for example, A=4 and B=2 to make sure that um, an infeasible solution costs more than a feasible solution. However, that is still not the case because uh, if we see here um, the feasible and the infeasible solution both have a cost of 10. So it's likely that either of these come up, right? Um, and so um, one takeaway here is that um, well, a penalty function that I have, it's great um, to to encode an optimal solution, but it's not really good to to encode a near-optimal, a near-optimal feasible solution, right? Because some of these infeasible solutions keep getting mixed in, and and there's no value of A and B that ensures this hierarchy of um, optimality and feasibility, and then at the end, having some infeasible solutions. And then a second takeaway here also is that um, well, this infeasible solution that we have here, it's not too bad. Um, so even though it's infeasible, it has three nodes, but as soon as you add one more node, um, it actually becomes a feasible solution and um, u, it it actually becomes a feasible and an optimal solution, right? Um, and so these are the considerations that we took and uh, tried to answer this question about how do we reduce or eliminate penalty coefficient dependencies um, while maintaining the solution quality. And so in in this case again um, once we add a node to this third solution, it's not that we are um, making the solution quality worse. In fact, you're making the solution quality better, right? And so can we develop a framework that actually does um, um, makes it better to encode these near-optimal solutions?
>> And so in that um, with that in mind, we introduce what is called the scoop framework. And um, we essentially have two problems here. One is our constrained problem, we call that PC, and then we also have an unconstrained problem called PU. And we call both PC and PU scoop twins if they satisfy a few conditions. The first condition is that they must have identical input domains. Sorry. Um, which means that they take the same kind of input. And then the second condition is that every feasible solution to the constrained problem is also a solution to the unconstrained one. The third one, third condition is objective function compatibility, which means that solutions from one problem can be translated to the other problem in polynomial time. And the fourth condition is of solution enhancability, which means that um, you can either have a a bit string that satisfies the constraints of our PC constraint problem, or um, a solution can be effectively corrected to a feasible solution with an equivalent or better objective value. So there is a way to make sure that our infeasible solution becomes a feasible solution without losing quality. So if we have all of these four conditions met, we can say that this one problem PC and this other problem PU are scoop twins. And um, then the objective now is um, can we find uh, our scoop twins for the constraint problems that we have? Uh, maybe not all, but maybe we can find some scoop twins um, for some problems. And so the way we go about this is to um, have a set of guidelines, which is first to identify what kind of constraints we have. The second is to quantify the feasibility of an infeasible solution. The third is to develop an unconstrained objective function which is compatible with the constrained objective. And then the fourth is to develop this classical um, solution enhancibility routine. Uh, it's not that easy. And if it were, then we could have found scoop twins for every problem. But um, yeah, it it takes time to think about these. And so once we have a scoop twin, our workflow now becomes um, that you have this constraint problem, you've transformed the constraint problem to an unconstrained one, and then used QAOA to solve it, and then offloaded all of the feasibility requirements to um, the classical post-processing. And so based on this workflow um, we actually came up with um, about 12 scoop twins. Some of these actually share um, share the twins. For example, 7, 8, and 9 have uh, the same scoop twin, which means you can convert solutions from one to another in polynomial time based on the constraints that you have. Another thing to note here is some of these are quadratic, 1 to 5 for example, but um, 6 to 12 are um, HUBO or higher-order unconstrained binary problems, um, which is still fine because we can tackle higher-order terms with QAOA. And then the third thing to note is that most of these are NP-hard problems, but we also found a couple of them that are polynomial time. But you can encode them as a HUBO, and um, these these two problems, minimum edge cover and maximum matching, these um, have a scoop twin, which is which is this one, maximum profitable edge coverage. Um, and so you can read more about it in my thesis. Um, all the problems have been listed there. But we'll continue with um, minimum vertex cover here.
>> All right. So we have vertex cover. It is a constraint problem. We now want to build a scoop twin of vertex cover. So the scoop twin of vertex cover is called profit cover. And we'll get to the meaning of that. Um, and so in our guidelines, the first thing is to identify constraints. So um, we we have um, one constraint here. The one constraint is that um, every edge must be covered. Even if one edge is uncovered, it would mean that the solution is infeasible. Uh, the second is to quantify feasibility. Um, and this is more of a thought process. For example, um, if I look at the first graph over here, um, I'm using two vertices, but I'm covering seven edges, right? Um, and in in the second graph below, I'm still using two vertices, but I've only covered four edges. Um, and so what this means is that um, certain vertices seem to have more power over other vertices. Um, and I would want to make sure that um, I make use of these powerful vertices in my vertex cover because um, well, if I try to make the first one here, the first graph better by adding a couple of other um, vertices, I've actually achieved a vertex cover. But in the second case, um, I can still do that. Uh, I might be left with some redundant vertices. So um, I may get a feasible solution, but um, it might not be optimal. So in a way, this top solution or this top set of vertices is better than this bottom set of two vertices. Um, and so um, we're looking at the power of vertices and we're saying, okay, um, I'm going to relax the requirement of edge coverage. I don't require that every edge must be covered. Instead, I'm going to compute um, something called a profit. And the profit is calculated as the number of edges covered minus the number of vertices used to cover it. Um, and so profit cover is a new problem where um, instead of um, covering edges, we are just looking at we're quantifying how much we are covering, and we're saying every subset of vertices has a profit where you can calculate that as the number of edges covered minus the number of vertices used. Um, and so this can also be made into our um, cost function or our cost Hamiltonian, where this term in green is counting um, edges that have been covered. So um, basically, if both Xu and Xv are zero, then the edge is not covered, but if either of Xu or Xv is one, then this whole green term becomes one. So you've added one to the edge coverage, and then the second term here is counting um, the number of vertices you're choosing, right? And so the profit, for example, for this first graph here would be um, total number of uh, covered edges, which is 7, minus 2, and so the profit is five here, whereas the profit here is 4 minus 2, which is two. Um, and so why is this um, important? It's because this problem, profit cover, actually has a direct relationship uh, to vertex cover, um, in that um, it it can be proven that a vertex cover of size K can be obtained from a profit cover of profit P equals um, total number of edges minus K in a polynomial time, which is order of um, worst-case order of number of edges. And so um, why is this why is this good? It's because it is a polynomial time routine. Um, what we are doing here is proving that this profit cover is related to vertex cover, and when I actually solve um, my Hamiltonian, which is the hard part of my problem um, I'm actually not using any penalty. So you can see here that there are no A and B. Um, we're just getting a profit out, and then it either might be a vertex cover, or I can have a classical post-processing routine to to get to a vertex cover. And so you can look at the proof of this relationship in in two star and three. Both these papers have that. Um, and so um, going back to our example um, if we look at the problem profit cover, or the optimization version of it, which is maximum profit cover, we can see that um, well, there are no infeasible solutions because they're all feasible solutions. But some of these are optimal, and the other ones are just feasible. So this is exactly like uh, if you've seen Max Cut, Max Cut is completely unconstrained. It is similar to that in the sense that every subset of solution is a solution to profit cover, some of which might be optimal. And so if you compare these solutions with actually our vertex cover Hamiltonian um, in vertex cover, we said that um, this third and the fourth graph both were infeasible. But in the case of maximum profit cover, they are both feasible and optimal. What that means for us with the relationship that we have with um, um, with uh, the the relationship between vertex cover and profit cover is that these two solutions, which are infeasible in vertex cover, can actually be made into optimal feasible solutions to vertex cover using classical post-processing. Okay. Um, and so this is great because um, in in the first case, in the vertex cover case, where we were penalizing, certain solutions are actually now optimal solutions in our profit cover case, which means we are increasing the solution space of optimal solutions, which means um, when we have our probability distribution, there is a higher likelihood that you fall into one of these categories, and if it's not optimal, it's still feasible. But then there is a defined hierarchy of um, optimality and feasibility, right? So so so that is what is um, maximum profit cover, and this is how we've converted um, a minimum vertex cover problem to a maximum profit cover problem and solved this instead on our uh, using QAOA. Um, and vertex cover um, it's it's it's a well-known problem. It's also related to two other um, pretty well-known problems, which are independent set and clique. And these problems also have unconstrained variants, which is um, we call them profit independence and profit clique. And um, and so yeah, you can you can use vertex cover, or you can use profit cover um, to solve vertex cover, or you could use profit cover to solve independent set. But you could also use profit independence to solve independent set. All of these three um, um, problems on the right here are are are unconstrained problems, and all the ones on the left here are the constraint problems that um, we are interested in solving.
>> And um, so I just wanted to also speak a little bit about higher-order encodings, because some of those problems also have that. Again, these would be available to read in my thesis. I wouldn't go too much into it, but um, HUBOs are more expressive than QUBOs. So instead of having XuXv, you may have XuXvXw, or if you're looking at it in terms of our polyZ, then um, the third one here, C, is a higher-order problem. The second one is a quadratic problem. You can go even higher than that. It's just that the um, the gates that encode that particular term in our Hamiltonian would look something like this with multiple qubits. So that gets a little trickier, but it is it's doable, and it's increasingly feasible with advances in fidelity and connectivity of gate-based computers. Um, and so minimum dominating set, minimum maximum matching, minimum set cover. These are problems that have um, sort of nasty quadratic formulations, but as a HUBO, they as a HUBO and as a scoop HUBO, they're actually very concise.
>> All right. Um, so coming back to our intractable problems in practice. Now, instead of having this practical consequence of doing uh, these three steps, we'll actually add a couple of things here where um, well, first, exhaust what you can classically to solve quickly and exactly, then convert the problem into an unconstrained scoop twin, um, and then solve this problem, this unconstrained problem, directly on quantum hardware, and then um, do the classical post-processing to obtain feasible solutions. While you could have done this with um, a constrained Hamiltonian as well, this is a much more instance-aware method because um, you're basically taking all of the infeasible solutions that might result in an optimal solution. Also, you're elevating them up. So um, you you can transfer all of that feasibility into post-processing. Um, and so so in our end-to-end pipeline um, that we show in our paper here, which we just um, uh, published on arXiv, the experimental workflows for combinatorial optimization um, we show this sort of pipeline for vertex cover as well as its related problems um, where we have um, sort of modular sandboxes um, with classical pre-processing, the QAOA solver, as well as classical post-processing. Um, and so the nice thing here is that you have an exchangeable set of algorithmic components. You you can choose to use a few of these, you can choose to ignore a few of these, up to um, up to you. But then um, basically you could um, test a particular or or benchmark a data set um, holding some of the variables um, constant and varying some of the others. Um, and so um, I didn't talk a lot about classical pre-processing, but um, how are we shrinking problem sizes? Well, we know vertex cover is very well studied, and these would be techniques from um, parameterized complexity and fixed-parameter tractability, um, where we um, uh, where there are certain rules that that make sure that, oh, this in this particular graph, this particular vertex should be in the vertex cover or should not be in the vertex cover. Um, and so based on that, you can reduce your problem sizes. Again, it you can read more about this in our paper here.
>> So so in our experiments that we did in our end-to-end experiments, we did this classical pre-processing if we could do it. Some of these graphs are not reducible. And then um, we trained the the circuit either using a matrix product state simulator or a tensor network simulator called QTensor, or even the IBM quantum hardware. But mostly these first two, which are classical techniques, and then um, for sampling, we would either use the simulator or the IBM quantum hardware. If we did use the hardware, then we um, had some suppression techniques that um, handled some errors. So um, running this QAOA would give us high-quality profit cover solutions, which we would then take to classical post-processing, and then we would um, do a solution transformation where um, if we already have a solution, then we don't have to do anything for the constraint problem. But if it is, if the profit cover solution is infeasible for vertex cover, then we do um, a few polynomial time post-processing routines to make the solution feasible. And then if we are solving independent set or clique, there's a little bit of extra pre-post post-processing to do. Um, and so in in this paper, we've only used our uh, vertex cover profit cover um, scoop twin and then gotten our results.
>> All right. Um, so now I'll talk a little bit about the results that we obtained. Um, so the first part is full state vector simulation. And because this is simulating all two to the N different states, it would mean that we cannot go to very um, large circuits. But it still shows a little bit of um, a trend on what um, vertex cover versus profit cover formulations would look like. So because scoop formulations have more optimal solutions than their constraint problems, it is natural that you do get um, a higher probability of obtaining these um, obtaining these optimal solutions. And so the graphs here um, the the x-axis is the number of layers, the y-axis is um, the summed probability of an optimal solution. So um, for example, within the two to the N bit strings, if I have, I don't know, five solutions that have the best, best cost, then what is the probability of achieving those five solutions? That's what we are showing here, and these would be with a small graph with eight nodes, um, but varying densities. So the leftmost one is with um, an edge probability actually of 0.1, the second one is has an edge probability of 0.3, and then the last one here is edge probability 0.8, um, which means that the last ones here are um, are dense graphs, and so obviously the probabilities are also much lower. Um, and so because of the higher density of optimal solutions, you do get uh, a slightly higher probability of uh, QAOA getting to an optimal, but they are uh, a little on par with each other, both um, minimum vertex cover as well as maximum profit cover. And these are um, these are not solutions that have been um, post-processed. Okay. Um, it's just a raw comparison. Um, but then if we look at the near-optimal probabilities, um, we can see that um, when you're looking at not just the top solution, but let's say the top um, top three solutions. So the left two graphs here are the optimals, but uh, the middle is um, optimal plus the second best solution. And this one, the last one here, is optimal plus second best plus third best. And then you can see like um, the the gap keeps increasing, and you get better and better solutions with um, uh, with profit cover or profit independence. Actually, we also have profit independence results here. So even higher density of near-optimal solutions increases the likelihood that QAOA samples uh, those solutions as well. And then for these, again, these are all on our simulator, which we actually did using PennyLane. The approximation ratio for um, profit cover um, actually with one, two, and three layers is quite high. It's about um, 0.8 on an average, which is which is pretty good for uh, a constrained problem. Okay. Um, and you might ask why there is no approximation ratio for the vertex cover here. Um, is because um, I we think that approximation ratios um, work best for unconstrained problems with natural QUBO encodings um, where the cost functions or the cost values reflect solution quality. But it fails for penalty-based encodings because the near-optimal solutions uh, may have inflated or misleading costs. Sometimes the infeasible solutions have a better cost, and um, um, you might get an inflated um, approximation ratio based on that. Um, and so one of the advantages of using a scoop uh, twin is that you can actually truly make um, some kind of conclusions based on the approximation ratio that we achieve. And so even though this is for profit cover, because of the solution guarantee we have from the um, from the relationship um, between these two problems, we know that when we convert the problems of uh, or the solutions of uh, profit cover into vertex cover, the solutions are only going to are guaranteed to either be at least of the same quality or better. Right? So this um, is great, and and these would be um, some of these uh, I guess uh, I think 8 to 14 nodes are full state vector simulation, whereas 20 to 70 nodes were tensor network simulation, where we um, looked at the expectation value at the end.
>> All right. Um, and so the second part of evaluation is on the IBM quantum hardware. In this case, we pre-trained QAOA parameters with QTensor or the MPS simulation, and it was a sequential training. And the hardware that we used was um, the IBM Qubec um, hardware, which has 156 qubits. It's a Heron R2 or a heavy hex architecture. We used fractional gate decomposition, which means that um, uh, we had native uh, ZZ gates and RX gates, which means it did not have to get um, blown up into a very big circuit for decomposition. And then we did um, informed error suppression on these um, circuits. Um, and so if you look at some of the smaller graphs, just for u, looking at the results, the first one here is the profit that we obtained on a single instance. Um, and so this orange uh, that you see here is the expectation uh, value or the profit value that we obtain using profit cover. The the red one here is the profit of the most likely bit string. Okay. And then the green is uh, the post-processed profit. So what does this mean? So even though um, we got a profit of eight, we could um, for example, on this data point, we could post-process it to a profit um, of I guess profit nine. And and the blue, which you can't see here, but that is the optimal solution. And so even though the most likely bit string would have had a slightly lower profit, we were almost always able to convert it into an optimal solution or a near-optimal solution in this case. And these are with eight layers, right? That's quite deep. The second one here is um, an aggregate performance over 10 graphs of um, the approximation ratio that we achieved. It does sort of plateau because um, as our circuit depth increases, um, you you have a higher likelihood of qubits decohering, and so um, you would want the number of layers to be as less as possible, because a deeper circuit would result in more complications and more errors, and that's what we found with um, these aggregate results of approximation ratio, as well as the aggregate results of the summed optimal and near-optimal probabilities. So you can see that between layers 1, 2, and almost 3, we are increasing in uh, probability for for the best solutions or the near-optimal solutions, but um, as we as the circuits get deeper, it sort of plateaus or almost goes down. Um, and so in this third graph um, the blue ones um, are optimal. The orange one is near-optimal, and um, or the top 10% of solutions, and the the purple one here is the top 20% of solutions. All right. So that would be with N equals 10. Um, and then um, we also performed experiments on on much larger graphs than N equals 10, which um, as you would see in this table um, um, the graphs have names, and then the number of vertices here are either um, starting at 17, but going up to around 128. Um, and so this is from the quantum optimization benchmarking library, which describes 10 intractable problems and also has datasets for these. And one of those intractable problems was the maximum profit um, or sorry, maximum independent set, for which we used um, the scoop twin, maximum profit independence, to solve um, the problem. And um, it is a table. You can read the table, but um, um, maybe one thing to note here is this alpha best, which is the approximation ratio that we achieved for a particular graph. And so this would be single instances of these graphs. And you can see for some of these instances which have um, for example, 52 nodes, all of these have an approximation ratio of 1. And some of the larger graphs, for example, with the 128 nodes and 1120 edges, which is quite a dense graph, you have um, an approximation ratio of 0.94 as the uh, for the solution. Um, which is great. These are quite um, large problems that we were solving. Yeah, so that would be the quantum optimization benchmarking.
>> And um, a second sort of big end-to-end um, experiment that we did was on graph instances on real-world graph instances, and these are obtained from the Network Repository. Um, they um, a lot of them have hundreds of nodes, but we are limited with 156 nodes right for IBM hardware, and so um, we only chose the instances that could be reducible to um, 156 or below. And so depending on the selected instance, we either solved vertex cover, independent set, or clique. So for example, this this dataset called insecta ant colony day 38, we tried to solve the clique for it. It has 56 vertices and 1134 edges, again a very dense graph, which when we ran through um, our entire pipeline, classical and then QAOA, and then classical post-processing, produced a clique of size 24, which was actually interesting because um, on the repository, they had reported 22 as the clique size, and it's maximum clique. So um, we sort of got a better solution than what they have, but um, it is reported out there that 24 is the optimal, but it's really good that we got an optimal solution from an IBM hardware run. Um, and so again, all of the datasets there are about, I don't know, 30 or so, 30 or 40 of those graphs, which um, we've reported results on. So if you're interested, you can take a look here. Um, all right.
>> So um, I'm going to conclude now. Um, so basically, this talk was about solving constraint combinatorial optimization problems. Why it is a major challenge that um, many real-world applications do require solutions to problems that have constraints. Um, and quantum computing offers a potential acceleration for these computationally intensive problems. But effective encoding of constraints is critical to obtain feasible solutions. And so our impact um, is that we develop this scoop methodology, a framework that um, enables the elimination of penalty parameters. Um, and so then we also introduce um, novel unconstrained twins for um, for these problems, either uh, quadratic ones or higher-order ones. Um, and then a central focus for us was to maintain solution feasibility while improving the probability of finding high-quality optimal and near-optimal solutions. And then with our end-to-end pipeline, because we are combining classical and quantum resources in a in a much more smarter way, um, we believe that this work demonstrates a pathway towards quantum advantage for um, constrained combinatorial optimization problems that is scalable. Awesome. Uh, that is my talk. Thank you very much. Uh, these are the four papers that I have based my talk on, and these would be all of the problems again listed here. Thank you.
>> Thank you so much for that excellent talk, Priya. Um, we do have some questions. Um, so I think we can cover those with about the next 10 minutes we have left here. So um, first question was I think it was on slide, let me check, 37. Um, there was a question about some clarity between um, the number of vertices and alpha best. I I think maybe the the question is what was the correlation between the two, the two numbers again?
>> Or how are they sort of related?
>> Um, the co, well, it's just different graphs that have different, result in different approximation ratios. Um, with an approximation ratio essentially, if you're reaching one, it means that um, you you found the best solution. And um, the takeaway here is that um, for example, for these graphs which have um, let's say 52 nodes, or um, 17, which is a smaller one, or 34, or again 52 here, um, oh, it's been repeated twice actually, um, you have achieved um, the best solution out of um, our hardware run um, with the other ones also pretty close by. Um, and I think one thing to note here is that it's not that the number of vertices um, are related to the um, approximation ratio that you get. It's rather the density of graphs. Um, sparser graphs, it's easier to get to an approximation ratio of one. But the denser graphs, for example, if if you think about this last one here, the Sloan graph, >> 128 nodes with 1120 edges is quite dense, and getting the vertex cover out of it >> um, um, it will have a lot of >> two-qubit gates, it's a very deep circuit, and you can see that here, right? Uh, the two-qubit depth is uh, 1816, and the number of two-qubit gates are 11,6659. And so with that kind of um, large circuit, we have a 0.94 as the the best um, approximation ratio that we got. Um, which is which is quite good, >> right? That seems pretty high to me. But then maybe I'm missing something. Um, but then the one right above that has much fewer gates and has an alpha best of eight. How do I think about that?
>> That is a great question. Um, and it's again, this is sampling, right? And sometimes you do sample a good solution, sometimes you don't sample a good solution. So it's also the sample size that you chose, um, which was a million samples, by the way, in both both of these cases. Um, and then it's also about um, as you can see here, there is uh, a best that you get. So in these million samples, what was the best sample that we got, and then what was the most likely sample that we got, and what was the optimal? And it is just that in the experimental run that we had um, um, comparing the bests that we got. Um, the the best one in the 64 one was eight. But maybe if we tuned some parameters um, um, or changed the optimizer, this would result in something different. Um, but yeah, there there is a um, there is a part of it which is a lot about trial and error about these parameters. Um, and sometimes it works, sometimes uh, it doesn't. But yeah, these are these are the results that I got. That's that's a great observation here. Um, with the Yeah, this this is a much it's a less dense graph. Um, ideally you would have want to got a better solution with this one.
>> Sure. I mean, ideally >> ideal is not the world we live in.
>> Yeah, exactly.
>> This question, just to I guess clarify things and and confirm for the audience, when you say a real-world problem, is the algorithm tested on real quantum hardware?
>> Yes.
>> Yes.
>> Yep.
>> Um, but it is an end-to-end result, which means that we did some classical pre-processing, then we solved the the hard part on the quantum computer, and then we did classical post-processing. Although for this particular one, if I remember it correctly, um, we could not reduce it by a lot. It was probably three by three nodes that we reduced it um, from 56 to 53 um, that ran then on a quantum machine. So, uh, it's not like the almost the entire thing got solved classically and then maybe five nodes got onto the quantum computer. So, yeah, but yeah, these are um, both of these are um, um, on real quantum hardware, on IBM Qubec quantum hardware.
>> Yep. All right. Let me just check the chat and see if I missed anything else. I don't think so. But I do have one question that I always like to ask people, you know, at the very end, which is like what's next essentially? Like this is great work. I totally see the applicability and how this is so important, but what is your plan to um, take this further?
>> There is a plan.
>> Yeah, there is. Uh, and we are working on it. Um, so basically, this work, we we limited ourselves to graphs that uh, could have been at least reduced to 156 nodes or lesser. But then what do we do with larger problems? Because all of these problems, by the way, they you you can classically with some techniques kind of get an an optimal solution out of them. Um, and you you can see the results um, again on this paper that some of these or well, at least in this uh, optimization library, all of these problems have been solved classically um, either with Gurobi or any one of these techniques um, um, and so it's it's easy to compare that, oh um, we we have the optimal, right? This is classically computed optimal, and then what the quantum computer gets us is uh, is is the solution that we have. Uh, but there are graphs where um, we don't know what the best solution is, and these are quite large. Um, and that's the challenge with combinatorial optimization is that many of these sort of large graphs with 100, 120 nodes, you can solve classically, but the ones that you can't solve are 400, 500, 1000 million nodes. Um, and so there are different ideas on what you can do to them. You can either um, I know, maybe divide up the graph or um, you do some kind of pre-processing such that you you work with sections of the graph, but they all result in um, in some loss of solution quality. Um, and so for us, our big next work is to tackle these larger instances and see what we can do classically. Um, because there there's a lot of knowledge classically on what to how to how to deal with intractability. Uh, but can we use it effectively such that um, given the current quantum hardware we have, we are able to get um, get to a point for these larger problems such that we can we can show um, the results on a quantum machine or show quantum advantage? That's a big one. But um, yeah, that would be >> the end goal.
>> Yeah.
>> Um, while we you were answering that question, we did get one more question, which I think is good that um, hopefully we can try to answer in the next few minutes. Um,
>> Yeah.
>> Essentially, how do you go about classifying the cost of the pre-processing versus the the post-processing? How do I classify the cost of pre-processing versus post-processing?
>> Um, I am not sure I understand that question, but let me go. Maybe it's just in terms of like how do we think about making sure that the post-processing isn't um, >> going to explode in in its time so that it still becomes useful.
>> Oh, right. Okay. That cost. Yes. So, um, the classical pre-processing and the classical post-processing routines that we have, these are um, these are polynomial time algorithms. So for you're never going to have uh, a combinatorial explosion here because we are doing none of those. Usually, when there is a combinatorial explosion, it's usually some kind of um, brute-force search that you're doing. But uh, yeah, most of these run in order of total number of edges. So um, it's it's never going to be um, the timing. These are very, very easy, fast algorithms. And so it's just it the way to think about it is you have these tools in your chest. You have to use them. Uh, there's no point not using them because they're just so effective to use them. Um, and so it's sort of um, not taking the quantum hammer and putting it on everything, but just you're you're being careful about what you want to throw at quantum. And so the cost of these two, classical pre-processing and classical post-processing, is polynomial. There's no exponential time algorithms involved at all in any of these rules or any of these transformations.
>> And that's I think what the really the important point to emphasize is that we're talking about polynomial, not exponential, with that.
>> Yeah. The exponential part is all in the middle. That's what the quantum is for.
>> Absolutely.
>> Okay. Um, thanks so much. Uh, we're right on time. You answered all of those questions beautifully. It was a great talk. Thank you again for being here for doing this with us. I learned a lot.
>> Definitely. Personally, I did as well. So thank you again, Priya, and good luck with your future work on this. And to the chat, to everybody watching live or >> not live at a later date. Um, we do these talks, like I said, at the end of every month, the last Friday at 12 Eastern, right here on the YouTube channel. So make sure you like and subscribe so you don't miss any more in the future. And with that, I'll sign off. Have a great weekend, everybody. And thank you again so much to our speaker.