Solving MaxCut with QAOA: Quantum Tutorial for 100 Qubits

welcome back to Quantum Computing in practice I'm Olivia Lan and today's episode three is going to focus on a qaoa experiment at the utility scale if you have been with us since the beginning you have seen us walk through IBM Quantum Hardware the framework of Kiss kit patterns and the latest and greatest eror mitigation techniques that researchers and developers use to scale up Quantum circuits we felt like it was really important to give you all this context and show you the direction that we were headed but now there is no reason to wait any longer

to see all of this information in action now some things to keep in mind before we get started everything is going to follow the framework of Kiss kit patterns so we will go through these steps in order number one is mapping the problem two optimizing the circuit three executing with Primitives and four post-processing or analyzing the results we'll start with a fairly small example so you can all best get a handle of these steps and their purpose then we will discuss a very similar but much larger example to show you how one would scale up

the problem to the 100 Cubit level I'm going to give you all the tools to allow you to go forward after this lecture and run that problem independently last this is not going to be a code walkthr no matter how hard we try as we make progress code gets old and becomes deprecated so if you end up watching this video a year after it launches I don't want you to get hung up on the syntax that might slightly shift over time instead this will be a detailed discussion of the logic and the problem statement however

there is a notebook tutorial that pairs with this video that is attached in the description below following along with the code or referring to it after you watch this lesson and running it for yourself will give you the best possible learning experience so as a quick reminder not all computational problems are suitable for Quantum Computing easy problems and simple calculations don't need to take advantage of this technology because classical computers are perfectly good at solving them already as of 2024 the three domains we are most optimistic about exploring are these simulating nature processing data with

complex structure and lastly optimization optimization problems are some of the toughest computational problems to solve efficiently in an optimization problem you are looking for the largest or smallest possible value for a given cost function however for many problems of Interest finding this extremum becomes exponentially more difficult with the size of the problem that's why it becomes so hard to compute for an example you can imagine how difficult it can be to compute optimal flight paths or delivery routes across the country in this lesson we are going to explore a particular optimization problem called Max cut

cut which we are going to solve by using a Quantum algorithm called the quantum approximation optimization algorithm or qaoa so what is the max cut problem a maximum cut problem is a type of combinatorial optimization problem defined on a graph where the goal is to partition the vertices of the graph into two subsets such that the number of edges between the two subsets is maximized so for instance in this graph here each node is connected like so and the max cut is shown by this squiggly line which divides the nodes into the purple group and

the gray group the way to do this by crossing the largest number of edges possible is to cut through five edges for this graph here because the graph is so small it isn't hard to try a few possible cuts on paper or even in your head and figure out that five is the best possible option but imagine if the number of nodes doubled and then trip quickly this becomes impossible to do by hand and after a certain number it becomes so tricky that even supercomputers struggle to reliably return the best answer this is because the

max number of cuts scales exponentially with the number of nodes while this may seem a bit abstract there are many real world problems that can be cast into a Max cut problem such as fraud detection in finance graph clustering Network design and VLS CL I design also social media analysis the social media one is particularly easy to grasp say you want to find a group of individuals that have the most possible connections to other individuals on a social media platform in order to identify power users or people who have the most influence in a group

companies actually try to do this quite frequently one last Point here the max cut is often a sub routine of a bigger problem so it might not be defining the actual application but use under the hood it's much more common than you might naively think now it is time to get started the first step is to create our graph you can do this by importing a python package called rust Works Define how many nodes you are working with by specifying the number n then add your nodes to the graph G you will also have to

draw your edges we'll do this by hand here by just listing them out in an array like this where you show the last number which specifies the weight of the edge or how strongly the two nodes specified are connected here we're just going to stick to a weight of one for all but you might enjoy playing around with the weight later on and seeing how the solution changes to gain a sense of what weight means in this context let's go back to our social media example you can think of this weight as how influential one

person might be to another your connection to your spouse or relative for instance would probably be given a higher weight than someone who is just an acquaintance now draw your graph the tutorial attached will show you the proper syntax first before considering how to map this problem onto a Quantum circuit let's build some context on how the max cut problem becomes an optimization problem in the first place We Begin by first considering the minimization of a function f ofx where the put X is an n-dimensional Vector whose components correspond to each node of the graph

we will refer to this function from now on as our cost function then we need to constrain each of these components to be either zero or one here meaning on one side of the cut or the other we can write a function as a pair of nodes x i and XJ which tells us whether the corresponding Edge is in the cut thus plus the quantity x i + XJ minus x i XJ identifies whether the edge is in the cut if this quantity is equal to one this implies that the edge is in the cut

otherwise it is zero and the edge is not the problem of finding the max number of edges in the cut can then be formulated as maximizing this function next we're actually going to add a global minus sign to this function making the new problem equivalent to finding the minimum of this function instead and so the minimum of f ofx in this case will be when the number of edges traversed by the cut is maximal we choose to frame this problem as a minimization problem because this allows us to later map it onto an energy minimization

problem AKA finding the ground state which is what quantum computers are naturally really good at but remember there is nothing related to Quantum Computing here yet we still need to reformulate this problem into something that a quantum computer can understand we're now ready to syn our teeth in and begin the work and the first step is to map the problem onto a Quantum circuit it may not seem obvious how we are going to go from a graph like the one we just drew to a Quantum circuit but let's take this slow remember we are going

to try to solve this Max cut problem using qaoa in the qaoa algorithm we ultimately want to have an operator the hamiltonian which will be used to represent the cost function of our problem as well as a parameterized circuit the onot or the trial state that we will use to represent Quantum states that are educated guesses or candidates for the solution to the problem we can sample from these candidate States and then evaluate them using the cost function in this case the cost function is f ofx but we need to express it in a way

that feels native to the quantum computer for this we'll take advantage of a series of mathematical transformations to express f ofx as an energy function the hamiltonian the first step of the process is to express the problem of minimizing f ofx as a quadratic unconstrained binary optimization problem or Cubo for short Cubo is a general way to formulate these combinatorial optimization problems here Q is an N byn Matrix of real numbers n corresponds to the number of nodes in our graph five for this example and X is the same Vector of binary variables from the

initial formulation to effectively run the qaoa algorithm we need to express our optimization problem in terms of a hamiltonian which is a mathematical operator that represents the total energy of a system specifically we want to create a cost function hamiltonian that has the property that its ground state energy or minimum igen value corresponds to the minimum of the function which encodes the maximum number of cuts on the graph g once we have this hamiltonian all we need to do to solve our optimization problem is to prepare the ground state of the hamiltonian on the quantum

computer then sampling from this state will with a high probability yield the solution to the minimization of f of X as it turns out we are in luck because the Cubo problem is very closely related to and actually computationally equivalent to one of the most famous and ubiquitous hamiltonians in physics the eing hamiltonian in order to write the Cubo problem as this eising hamiltonian all we actually need to do is a simple variable change in order to go from Boolean variables 0 and 1 to spin variables minus one and one this step is straightforward it

is shown in more detail in the appendix of the attached notebook for those interested but in the end the minimization of this Cubo expression is the same as the minimization of this expression rewriting again slightly and we have our cost function hamiltonian where the minimum of the expression represents the ground state and Z becomes the poz operator while B is a real scalar coefficient now that we have our hand malonian it's straightforward to rewrite it in terms of two local ZZ poly operators that will convert easily into two cubic gates in our Quantum circuit please

refer to the associated notebook to see how this is done but the output is given by this line here note that in our example there are six objects or po strings because each represents an edge in the graph the length of the string matches the number of nodes so i i i ZZ is five nodes and the string will be composed of identities in all positions except for the indices of the nodes involved in an edge which will have Z terms in Kiss kit bit strings representing cubits are indexed backwards for example an edge between

nodes 0 and 1 will be encoded as I I I ZZ with the hamiltonian written in terms of Poes we are ready to construct our Quantum circuit this Quantum circuit will help us sample good solutions from the quantum computer the qaoa algorithm is inspired from the adiabatic theorem which states that if we start in the ground state of the time dependent hamiltonian and if the hamiltonian evolves slowly enough and given enough time the final state will be the ground state of the final hamiltonian qaoa can be thought of as the discret trotz version of the

quantum adiabatic algorithm where each trot step represents a layer which we'll call P so instead of evolving from one state to the other in each layer of P we will switch back and forth between our cost function hamiltonian and something called our mixer hamiltonian which we'll hear more about in just a moment but the point that I want to make is that qaoa has the advantage of being faster than the quantum adiabatic algorithm but it returns approximate Solutions rather than the optimal in the limit where the number of layers goes to Infinity qaoa converges to

the adiabatic case but of course this is very computationally expensive to create our Quantum circuit we'll apply alternating operators here parameterize by gamma and beta which will represent the discretization of the time Evolution so again the three main parts of the qaoa circuit are one the initial trial state in Gray which is the ground state of the mixer from the adiabatic state of ution created by applying a hadamard gate applied to every Cubit two the cost function Evolution which we already have in dark purple and three the evolution under the mixer hamiltonian which we have

not yet discussed in light purple now our starting hamiltonian is called the mixer because its ground state is the superposition of all possible bit strings of Interest hence enforcing a mixture of all possible solutions at the start the mixer hamiltonian is the simple sum of Po X operations on each node of the graph kiss kit allows you to use a different custom mixer operator if you wish but for this case we are just going to use the standard one so again you can see that with kiss kit a lot of the work is removed for

us making coming up with the mixer hamiltonian and the starting State trivial the only work we had to do was to find the cost function each iteration of these operators is called a layer these layers can be seen as discretizations of the time evolution of the system as previously described the alternating pattern comes from the Trotter decomposition and approximates the exponential functions of non-commuting matrices in general the more layers or steps we include the closer we will be to continuous time Evolution so in theory the more accurate the result will be but for this example

we'll Begin by just sampling with two layers remember both the cost function hamiltonian and the mixer are parameterized we still need to come up with Optimum values for gamma and beta now I recognized that was a lot of information and if you're seeing this type of math for the first time it can be tricky luckily one of the awesome things about kiss kit is that a lot of what we just went over can be done automatically without a huge lift from the user it's good to understand what's going on under the hood especially as we

scale up to bigger experiments but you won't have to do all of this work by hand every single time we have now mapped our problem onto a Quantum circuit it was a bit of work but don't worry it becomes easier and more intuitive the more you do it now we're ready to move on to step two optimizing our circuit for Hardware so while the circuit we just created look looks pretty simple and is useful to build up an intuitive understanding remember the quantum chip doesn't understand what this abstracted block is we need to turn it

into a series of one and two Cupid Gates that are native to the hardware and when I say native I mean it will be refactored into what's able to be performed directly on the cubits such circuits are said to be written in the back ends instruction set architecture which you might see abbreviated as Isa circuits the kcit SDK transpiler module offers a series of transpilation passes that can perform a wide range of circuit Transformations we want to make sure that our circuit is optimized for our purpose recall from our previous lesson that the transpilation and

process involves several steps mapping the cubits in the circuit or the decision variables to physical cubits on the device unrolling of the instructions in the quantum circuit to the hardware native instructions that the back end actually understands routing of any cubits in the circuit that directly interact to physical cubits that are adjacent with one another and as always more details about this can be found on the documentation site now comes an exciting step where we'll choose which backend to run our circuit on we actually have to do this before the transpilation step because the transpiler

optimizes differently for different processor this is yet another reason why it's important that kkit can automate so much of this stage away you wouldn't want to have to optimize your circuit by hand which can be done but sometimes It's Tricky and very timec consuming only to realize that you actually want to run your circuit on a different processor with different properties and then you have to do all of that work again pass your back end of choice through the transpiler function and don't forget to specify your optimization level this time I've selected optimization level three

which is the highest and most exhaustive omanization level and that's actually it for step two my circuit was transpiled automatically and I drew it here so that you can see how it was translated into one and two Cubit Gates now it is time for step three running the circuit with kcit Primitives so far we transpiled the circuit leaving the parameters gamma and beta alone but we can't actually run the circuit without specifying the value of the these parameters in the qaoa workflow the optimal qaoa parameters are found in an iterative optimization Loop where we run

a series of circuit evaluations and use a classical Optimizer to find the optimal beta and gamma parameters however we need to start somewhere so I have implemented some initial guesses for Gamma 1 gamma 2 and beta 1 beta 2 of Pi / 2 and Pi respectively I also want you to note that we will be using an optimizer to find better solutions for gamma and Beta And since I'm only calculating two layers for now that's all I need but if you make a more accurate qaoa circuit you would include more layers and thus need an

optimized gamma and beta for each sequential layer now let's just take a minute here to pause and remember our options for The Primitives we have the estimator and the sampler which one do you think that we are going to be using for this type of job well no matter which one you guessed you're actually correct we are going to use both the estimator and the sampler for the initial optimization Loop we will need the estimator but we'll use the sampler later on for reading out the final solution now we are almost ready to run our

algorithm I promise but very quickly it is important to note that you can send your job a variety of different ways which are called execution modes first we have job mode a single primitive request of the Ator or sampler made without a context manager circuits and inputs are packaged as primitive unified blocks pubs and submitted as an execution task on the quantum computer batch mode is a multi-job manager for efficiently running an experiment that is comprised of a bunch of independent jobs use batch mode to submit multiple primitive jobs simultaneously session mode a dedicated window

for running a multi job workload this allows premium users to experiment with variational algorithms in a more predictable way and even run multiple experiments simultaneously taking advantage of the parallelism of the stack use sessions for iterative workflows and experiments that require dedicated access for a qaa experiment a session would be a good choice to proceed with if you have access to it since you'll need to try multiple circuits for different values of beta and gamma okay now let's go back to our optimization problem we have already defined the cost function hamiltonian HC and the full

workflow is this the qaoa algorithm starts by initializing the cubits in the superposition State and then applies the onot with P layers it initializes gamma and beta parameters and then run the circuit using the estimator primitive once we calculate the expectation values we will then use a scipi Optimizer called Coba Coba optimizes the cost function classically outside of the qpu once those values of gamma and beta have been updated we repeat we will do this until the value of the overall cost function has converged and reached the lowest value then we will select the values

of gamma and beta that correspond to this low cost value and run the circuit one last time now using the sampler this is the result of me running the cobal Optimizer with my initial guesses here you can see that the value of the cost function over the iterations performed starts off a little wonky and it goes up and down but then it settles to a low value we will use these last gamma and beta values that correspond to the minimum cost function evaluation to run the circuit one last time and Sample the bit string that

will give us the max cut now using our optimized values for the gamas and betas we will run the circuit one last time to find the best possible bit string using sampler I listed the specific values that I am using here but remember when you try your hand at this or even just rerun the same tutorial notebook these values might change slightly now we will run our optimized circuit with these values and find our candidate solution to our Max cut problem if you were using sessions that is no longer necessary since we are just running

one last job now we we will finally look at the postprocessing stage and finding our final solution first let's plot all of the possible combinations of nodes which we have converted into bit strings as a histogram you can see right away that when I ran it I found four Solutions and highlighted those in purple that are more probable than any other solution the highest and thus most probable bit string solution is 0 1 01 please note the order of the cubits is reversed in the plot looking at the most probable solution we note that the

nodes 0 and three are grouped together and similarly for nodes 1 2 and four we can finally plot the most likely bit string back as a graph and remember the bit string simply corresponds to the node numbers and if they are included marked with a one or not included marked with a zero in our grouping when we draw the cut now we can see with our eyes the approximate line for the best cut which just represents the ideal grouping of all five nodes which I've drawn here one thing I want to spend some time discussing

here however is the fact that the correct solution is not unique because of the symmetry of this graph there are multiple correct Solutions instead of having nodes 0 and three be inside the cut we could have nodes 2 and four be included and you can see that all I had to do was rotate my cut to include these new points this solution of five Remains the Same let's take another look at the histogram and the four most likely solutions for a minute the last two solutions are the ones that we just plotted and they are

equally correct but that's not all we could also reverse the coloring for all of the correct Solutions and this time we just think of the nodes as being inside versus outside the cut on the previous slide we identified two unique correct Solutions but there are actually two more solutions one corresponding to the opposite of each of those see how here where I drew the remaining two solutions all I did was reverse the colors now the only problem is that the algorithm actually didn't find or identify this fourth last solution as being one of the top

four most probable answers it was the fifth the fourth solution that the algorithm identified is actually Incorrect and if you were to draw it you would see that that solution only has four cuts and since the others have five and four is clearly less than five this is obviously wrong the point here is that this is an approximate algorithm it is not infallible and it is not correct 100% of the time you do have to employ some of your own knowledge and understanding to sanity check the solutions it is worth highlighting that this error can

arise from several places it could be the approximate nature of the algorithm itself and the small number of layers that I chose to employ it could be a finite sampling error and this could be reduced if I increase the number of shots in my experiment or it could be a readout error since the fourth Real solution is only off by one bit the reason I'm pointing out all of these possibilities is because this is what it takes to fully become a practitioner of quantum Computing you need to understand the performance of the hardware and how

this can contribute to certain types of errors and how to correct for them however let's not forget that there were 32 possible Brit bit string Solutions and that the four real solutions were included in the top five best candidates and I only use two layers to find this in general if I want to increase my chances of finding the best Max cut every time I would increase the layer depth there are some subtleties to this but that's for a later episode now I'm going to let you try your hand at this yourself but this time

you're going to use 100 cubits so if we start by drawing our 100 Cubit graph you can see that it is no longer straightforward or even possible to eyeball where the max cut would occur there are simply too many possibilities to be able to pick it out by hand but solving this problem using qoa is still totally doable and you can follow the exact same workflow that we used for 5 cubits I'm about to send you off on your own and charge you with trying to do this experiment but before I do let's summarize recall

that the six steps of any qaoa job are as follows one defining a cost hamiltonian such that its ground state encodes the solution to the optimization problem two defining a mixer hamiltonian three constructing the operator's corresponding to the exponentiated hamiltonians four building the circuit it will consist of the initial ground state of the mixer and alternating repeated layers of the cost function and the evolution under the mixer Hamilton iians five prepare an initial State and use classical Computing techniques to optimize the parameters six run the circuit measure output bit strings looking for the most probable

solution now some things to note here I used optimization level three for my 5 Cubit example but that maybe wasn't necessary and the right answer could still be returned most of the time at a lower level of optimization because the circuit depth was fairly low for the 5 Cubit case but for the 100 cubits and a large circuit depth you almost certainly will need the highest level of optimization to find the right answer also keep in mind that one of the most challenging parts of a typical utility scale workflow is the mapping stage and finding

a graph that corresponds well to IBM's heavy hex topology if you were doing this work from scratch that's undoubtedly where you would devote much of your time for now this part has been done for you because that's not the main point of this exercise but bear in mind that it is something that we will require practicing and running a large scale job isn't always the straightforward we will delve into this further in episode 4 your final circuit is going to obviously look a lot messier than the circuit that ran on 5 cubits but on the

other hand I feel like looking at this circuit and seeing how many gates it has and knowing that you have the capability to actually run this on real Quantum processors is pretty impressive and this was my final solution you can see that the algorithm is certainly capable of grouping these nodes into two groups allegedly identifying the best Max cut that divides them as going from the two sets to the max cut line itself is Trivial anywhere the color changes along the lines that connect the nodes designates where the max cut line should be drawn when

I ran it the max cut value I was able to achieve is 84 so try it for yourself and let me know if you get something similar in the comments try three layers maybe four try changing the weights between the nodes and see how that changes the outcome there's a lot of interesting experiments that we can run with qaa now remember it is not guaranteed that I just found the best possible solution we know it's a good solution but for fun I challenge you to try to beat me see if you can get something that's

better than 84 in conclusion qaoa is a very Dynamic algorithm and there are a lot of heuristics and much to still be explored it gives a lot of room for learning new things about the field of optimization in general there has been a lot of work recently in the optimization space as evidenced by all of the archive papers that have recently been published online on qaoa or optimization and what is really cool is that finally not all of the these papers are Theory papers theorists have been working in studying qaoa for years but now the

experimentalists are getting involved because we finally have the hardware like IBM's processors that are capable of running many of these experiments we're moving from the imaginative space to the real world and that's very exciting yes there is still a lot of work to be done and there are still plenty of errors that we need to figure out how to deal with but we're making quick progress and you watching this video if you've made it this far are capable of running these experiments yourself please go try running your own 100 Cubit experiment and let us know

how it went follow along with the tutorial and you'll be in good hands and if you have any questions or get stuck don't worry we all felt that way or had those same questions when we first started learning this do your best let us know what questions you come across and we'll see you next time [Music]