Which Problems Are Quantum Computers Good For? Quantum Computing in Practice

welcome back to Quantum Computing in practice I'm your host Olivia Lanes last time we walked through an example of a Quantum Computing approach to an optimization problem known as Max cup using the Cubo formulation we went pretty far in depth but that was just one example of one approach today we are going to discuss near-term applications more broadly and develop our intuition for different types of problems we expect to find useful Quantum solutions for and see some recent examples of some important work done in our community at a utility scale previously we briefly discussed that

not all problems have the need for additional computational power specifically Quantum Computing in order to be solved efficiently these are the problems that you're already most familiar with arithmetic scrolling social media maybe playing Tetris Doom or other video games we broadly consider these easy problems on the other hand there are very hard problems such as finding prime factors of enormous integers and this is the basis of RSA encryption and what sh's algorithm was actually designed to solve another example is finding a solution in an unsorted data set this can theoretically be solved by the quantum

algorithm known as Grover's algorithm however most experts agree that these types of algorithms will necessitate the implementation of error correction and we're just not there yet technologically speaking so as we go forward in this lesson and in your Quantum educational Journey remember we are looking for this Sweet Spot somewhere here in the middle it's a hard problem to crack but that's also what makes it so fun one thing we've not yet discussed much is computational complexity Theory one of the reasons being is that it can be somewhat intimidating and yes complex computational complexity theory is

the field of computer science that aims to classify computational Problems by how difficult they are are a ton of different complexity classes in classical Computing but the most fundamental are these P problems these were problems that can be solved in polinomial time at the scale as the problem increase meaning that they are easy to solve the next more difficult type of problem is NP problems which stands for non-deterministic polinomial these are problems whose answers can be verified in polinomial time but not necessarily solved next is NP comp complete and now we're getting into the really

challenging problems with no known polinomial solution this is where famous problems like the traveling salesman problem and even the game Sudoku live now when Quantum Computing came to be at least in theory people spent a considerable effort trying to figure out what class of problems these new types of computers would be able to solve efficiently a new class of problems were invented called bounded error Quantum polinomial problems or bqp for short their strict definition is a little long but it is the class of decision Problem solvable by a quantum computer in polinomial time with a

small chance of error there's a chance of error because Quantum measurement is inherently random but the error probability can be arbitrarily small now all of these classes live in a larger class we call pspace and this is where we think bqp lives relative to all of the other types of problems but it's very hard to definitively prove this mathematically you'll notice that bqp Quantum problems do not necessarily overlap with NP complete problems however you might have still seen some Quantum Computing approaches that aim to solve NP complete problems why would this be one common misconception

is that there is no point in exploring solutions to problems like the traveling salesman and other NP complete problems for a quantum computer or any problem or a mathematical proof for a Quantum speed up has not been found however this doesn't necessarily have to be the case finding mathematical proof that a Quantum algorithm is faster than its classical counterpart is rare Shore and Grover are two of the only handful of examples where this has been done so far but that is okay in fact computer scientists still haven't even been able to prove that the classes

of p and NP are different even though all intuition tells us that they must be also comparing two algorithms and how they scale often looks at the worst case scenario for each it is quite possible that in practice the worst case scenario is not what we find in real life so we do not despair we introduce instead the idea of heuristic Solutions if you're an experimentalist you already know and love these types of solutions a heuristic is any approach to solving a problem that is pragmatic but not necessarily optimal and that's great because Solutions don't

necessarily have to be optimal in order to be very useful for instance think about a financial application we haven't yet found an exponential speed up for most Financial algorithms that Quantum could be used for yet but that doesn't necessarily matter we don't need an optimal solution in finance at least because a solution that is even just 1% more efficient could equate to billions of dollars worth of profit so how do we know what use cases and problems could be suitable for Quantum Computing right now and by that I mean there's significant reason to believe Quantum

utility or even Advantage could be found either now or in the somewhat near future maybe it's easier to first name things that the problem should certainly not have it can't require a huge number of cubits we don't have processors yet that have thousands to millions of cubits available that's one of the main reasons Shores algorithm and the like are so far off the circuits also can't be incredibly deep it's really hard for me to tell you exactly what circuit depth won't work because it depends on so many factors but in general if your experiment requires

a depth that you haven't seen achieved in the literature yet you might be in for a rough time and lastly any type of algorithm that we know will require error correction cannot be done yet what we should look for however are experiments that make use of most of the cubits available on any given qpu we have also emphasize the importance of error mitigation and suppression and lastly there should be an obvious extension to Future applications that would be important for society and that we could see eventually leading to Quantum Advantage now let's talk about some

examples of use cases which fall into three main categories that we have identified as most likely to see favorable outcomes in the near to Middle term the first area is the simulation of nature we've spoken about this previously there are so many opportunities for quantum computers to improve the research being done on the molecular and atomic level and the reason for this is because current classical methods are limited by fundamentally inefficient mathematical descriptions of atomic structures storing and manipulating a Quantum State takes an exponential amount of resources on a classical computer but can be done

efficiently on a quantum computer and that's what makes material simulation and chemical modeling some of the most promising application areas more specifically this could lead to developments in carbon dioxide sequestration alternative batteries or the invention of new drugs some algorithms that are especially relevant in this area are the variational quantum igen solver vqe which is used to estimate certain properties of a material such as equilibrium or minimum energy states another example is the time Dynamic simulation TDS that algorithm is used to estimate response functions or spectral properties of materials and I also wanted to mention

a newcomer sample based Quantum diagonalization which we think will we will hearing a lot more about in the near future the next application area is optimization now optimization is pretty ubiquitous in Computing as you can imagine so the use cases are quite numerous and varied however some examples that we hear about a lot are portfolio optimization in finance industrial design and also distribution and supply chain the most common algorithm you will probably hear related to optimization is the one we have already covered in some depth the quantum approximate optimization algorithm or qaoa lastly one area

that there has been a lot of excitement for in the past few years is quantum machine learning now I think it's fair to say that it looks like qml isn't going going to happen as soon as simulation will in all likelihood but nevertheless there are some impressive algorithms people are working on consistently corresponding to some very important use cases some of these possible use cases are natural language processing Network traffic analysis and even fraud detection in financial transactions relevant algorithms in this area are the quantum support Vector machine Quantum neural networks andant Quantum generative adversarial

networks now to clarify those three groups that we just described are broad application areas it is also worth noting that in the community there is also benefit to groups working together who are focused on a specific topic IBM spearheaded an initiative not too long ago called The Working groups to try to help collaborators meet and create productive Synergy in four specific areas Healthcare and life science materials and HPC high energy physics and optimization here are our current groups and the entities involved in those efforts if you want to hear more about what the working groups

are doing we have attached four of their white papers in the description below now like I said I think the best thing to do at this point in the course is to spend some time exploring which sorts of problems people are working on on The Cutting Edge of this technology and developing our intuition for knowing what types of algorith iths are going to work and how to apply them and before we begin I just want to make it very clear that the main goal here is not to understand every detail of the experiments this type

of analysis can be very intimidating for even experts if the paper is slightly out of your area of expertise the goal is simply to help develop an intuition for the types of problems quantum computers are good for and how to handle them and if you're interested in the finer details and this has sparked some ideas of your own I definitely encourage you to go and read the full papers themselves the specific use cases and papers that we are going to be taking an in-depth look at are these first we will explore a paper that discusses

simulation of hadron Dynamics This falls into the high energy physics category next we will look at an optimization problem specifically bias field counter adiabatic Quantum optimization and lastly we will look at yet another simulation problem but this time focusing on mRNA a crucial molecule for drug and therapeutic development if you're familiar or not with these papers that's no problem we are going to walk through them all three are important papers that tackle problems of substantial size and show how quantum computers are beginning to be used as another method of scientific inquiry first up is simulating

hadron Dynamics and we're going to delve into a paper by Martin Savage's group at the University of Washington called Quantum simulations of hadron Dynamics in the schwinger model using 112 cubits if you're not a high energy physicist you might still be familiar with the term hadron such as in the Large Hadron Collider or the LHC which is the giant particle accelerator 27 kilometers in circumference that made it possible to finally observe the higs Bon now I had is a subatomic composite particle made up of other small particles called quarks some examples would be neutrons and

protons for a little bit of context the LHC was built to allow for the study of fundamental physics and what happens to particles when they Collide at super high energies in this circular tube by doing this scientists hope to learn more about how the early Universe came into existence and like I previously said it was also used to find the Bon which is an elusive particle responsible for mass of fundamental particles now in principle the interactions of these particles could be simulated from start to finish with a sufficiently powerful quantum computer we're not quite there

yet but progress is being made now the Sher model is a simple model used to simulate some of these Dynamics and has emerged as one of the most popular models of choice the details of the model are not super super important for right now but for those curious it is a model that describes the behavior of electrons and positrons interacting via photons in 1 + 1 D Dimensions meaning that there's one spatial Dimension and time the model has a lot of similarities to Quantum chromodynamics which describes how quarks and hadrons interact now that's extremely hard

to simulate so the schwinger model is often used as a toy model to invest some phenomena that are actually common to both now the way we are going to proceed with this example and the rest of the examples I have selected here as well is by asking ourselves a series of questions the first is why did we have reason to believe that simulating this on a quantum computer would work at all in this case the electrons and positrons in the schwinger model have a screening effect causing correlations between distant Fons to Decay exponentially with separation

and this means that there aren't as many long range interactions from a cubit on one side of the chip to another on the other side of the chip which we know is very error prone so this is really good for the hardware that we have available today next is this topic even of Interest well I hop I have already sort of convinced you that yes high energy physics is of great interest people were willing to spend billions of dollars to build the LHC and thousands of scientists and and technicians across the globe have dedicated their

lives to this field that's how important it is but the shringer model is simplistic and isn't designed to cover three spatial Dimensions nevertheless it is an important model as it still provides currently testable slices and useful simplification of a full Theory last how was this work done or what approach would they use if they were looking to continue the work in simulation type experiments vqe is one of the most common approaches and is the first step is almost always the same prepare the ground state in this case it is a vacuum State and in this

experiment they use a new version a vqe called SC adapt vqe to prepare both the ground state and the hron wave packet on top of the vacuum the next step is to then allow the hadrons to evolve or propagate in time lastly we need to identify the observables that we want to detect now if those steps sounded kind of familiar to you minus the Hadron wave packet part that's because these steps are very similar to what we covered in the qaoa example in the previous episode hopefully you're starting to see some patterns emerging here the

components needed for vqe are very similar to qaoa we start in a familiar State here the vacuum State and then we let it evolve in time with a series of exponentiated hamiltonians divided into manageable chunks where n is the number of Divisions the only big difference here is we create the wave packet of hadron centered within our circuit before we start letting it evolve so how is this done well the vacuum state is the ground state and we've already sort of covered how to map this now preparing the Hadron wave packet is a bit different

on this vacuum a hadron can be exciting by creating a firon anti- fermon pair on adjacent sites by preparing a superposition of such hadrons at different locations an arbitrary wave packet can be prepared the authors centered their wave packet in the middle of the circuit to observe the evolution without exceeding a boundary but remember the name of the game when working with noisy qpu is to keep the circuit depth manageable to do this the SC adapt vqe protocol uses symmetry and hierarchies in length scales to determine low depth Quantum circuits for State preparation the idea

is that this will create an onzo with a smaller number of parameters equating to a shallower depth more details can of course be found in the paper than we have time to cover here so make sure to check it out now let's take a look at the results this experiment was run on an IBM Quantum Heron device and implemented a few different types of airor mitigation and supression including a more recent technique called operator decoherence renormalization as well as dynamical de coupling zero noise extrapolation and poly twirling now let's try to interpret the data the

observable that we're actually going to be measuring to observe how the wave packet propagates is something called the chyal condensate which is a bit abstract but it's basically a superf fluid phase of the hadrons now we can see the wave packet centered here on the sites that have been designated to run this experiment where the color corresponds to the chyro condensate the left side shows the airfree results from the simulator while the right side shows the results from the IBM quantum computer Torino ideally these would be mirror images of one another due to symmetry so

you can see that there are some imperfections now this vertical y AIS corresponds to the chunks of time I measured earlier so why don't we take some horizontal cuts through the first and last time steps of the data to see what happens to the wave packet at Time tals 1 here in Orange corresponding to this cut you can see that the caral condensate is narrow and localized it it also corresponds really well to the simulation that was done for comparison at tal 14 however though it is much more spread out and is less localized maybe

the comparison to the simulator isn't quite as perfect now but you can still obviously see very good agreement between Theory and the data which is encouraging in conclusion this is a very cool example of the type of simulation work you might not initially think about applying quantum computers to however in fact you can and it works it's not perfect but you don't have to be a particle physics expert to see that the quantum computer accuracy predicts the outward propagation of the wave packet which is exactly what we would expect to find hopefully future work in

this area will continue and high energy physicists will continue to find ways to incorporate Quantum Computing into their work streams the aim is to solve theoretical problems more precisely and those which can't be done classically and use experiments to accept or reject theories in hopes of discovering new physics building improved detectors and leading to a better understanding of nature at its most fundamental level our next example focuses on optimization and will be a deep dive into a paper called biased field digitized counter adiabatic Quantum optimization which was done by members of the kipu quantum team

in the University of the bass country in Spain we'll begin like we did before with a series of definitions the first is counter adiabatic which is a type of evolution that suppresses non-adiabatic effects experienced by a system regardless of how fast those processes occur recall the adiabatic theorem from the last episode you usually need to let a system evolve very slowly if you wish for it to remain in the ground state this is a big problem because the slower we have to let things evolve the more time we have for errors to occur counter adiabatic

driving often abbreviated as CD aims to combat this by adding terms that counteract these unwanted excitations the main idea here is to speed up the whole experiment and reduce edce Quantum circuit depth by suppressing excitations that could lead to spous Transitions now let's talk about what a bias field is other iterative algorithms like vqe take classical parameters into these states and use classical optimizers to search the many dimensional parameter space for that set that yields a minimum expectation value for a fixed hamiltonian in this case they instead vary the hamiltonian each time moving adiabatically from

a known case to the case of interest but since there are no classical parameters being passed and no variational wave function how do you update your state from one pass at the hamiltonian to the next well they add a bias feel to the hamiltonian whatever the lowest energy state from the previous run they add a term in the hamiltonian to the bias the state in favor of that so why is this experiment of Interest well first of all this is a new approach that could be applied more generally to other optimization problems but in this

case they applied it to an ising spin glass problem as we discussed previously many combinatorial optimization problems can be reformulated as solving for low energy states of ising hamiltonians the ising model is a series of microscopic spins distributed on an array the model can be used to describe a spin glass in which the magnetization is disordered basically the little magnetic moments are oriented randomly in the array and why did we think this would work well we already sort of covered how we are combating two typical issues found in variational algorithms when we covered the definitions

of the paper but to summarize the algorithm they are proposing speeds up the evolution to reduce the circuit depth while also suppressing non-adiabatic transitions furthermore it does not rely on any classical optimization routine which can be an issue leading to Barren plateaus and getting stuck at local Minima lastly the authors also make sure to align the interactions in the problem hamiltonian with the hardware connectivity in the real qpu which is always very important lastly how does this work so like I said there are no classical optimizers being used here like there often is in iterative

Quantum algorithms instead by feeding the solution from each iteration into to the input for the next one the bias field digitized Quantum optimization algorithm incrementally refines the ground state bringing it closer and closer to the final evolved State and combined with counter adiabatic protocols we can do this even with short depth Quantum circuits that should run smoothly on noisy Hardware so when the experiment was performed the authors chose to run the algorithm on the 127 Cubit IBM quantum computer Brisbane here the author showed the eth ization of the optimization algorithm for a nearest neighbor randomly

generated spin glass instance over 100 cubits they compare ideal simulation results from dcq and bf dcq as well as the experimental result and they also show a result from a classical solver called goobi as a reference now with just 10 iterations BF dcq provides a drastic enhancement compared to dcq although the experimental result is a bit different than the ideal result due to noise the performance is still better than the ideal dcq this shows that there's still a lot of excellent progress being made with regards to Quantum optimization and good results are being reported on

over 100 cubits for one of the first times last but not least is a very interesting paper exploring mRNA structure prediction from our friends at madna Pharmaceuticals and it's called mRNA secondary structure prediction using utility scale quantum computers to begin if you like me still haven't taken a biology course in a few years you can refresh yourself on what mRNA is messenger RNA is a type of RNA involved in protein synthesis it basically reads instructions given by DNA the secondary structure of mRNA is more or less how the chain is folded and the RNA secondary

structure prediction proc problem is the problem of finding the most stable folding of the sequence of bases of nucleotides that make up DNA and RNA that would be c g u and a this image here shows some of the common folding structures found in mRNA each color highlighting here shows a different secondary structure but the exact characteristics for what makes one of these structures more favorable over another isn't well understood all we can do is figure out which which one has the lowest free energy compared to the unfolded state and that's where quantum computers step

in so why are mRNA secondary structures important well accurate prediction of them is actually crucial and not only understanding DNA and our genes but also for Designing RNA based Therapeutics like the covid-19 vaccine there is reason to believe that the approach in this paper would work because this has long been known to be a formidable optimiz ation problem for classical computers due to the vast number of possible configurations and for some configurations it's actually known to be an NP complete problem however on a quantum computer we can formulate the secondary structure prediction as a binary

optimization problem something we know how to handle furthermore there has been evidence in the literature already of accurate RNA prediction on small scale Quantum devices and Quantum simulators so the obvious question is would this work on larger Hardware the experiment is done by using something called the conditional value at risk variational Quantum igen solver which is a modification to the traditional vqe algorithm and is expected to achieve better convergence this plot shows the distribution of measurement probabilities of the sample bit strings with the corresponding energies for 42 nucleotide 80 Cubit instance here the bit strings

symbolize pairings of the nucleotides it illustrates that the lowest energy bit string has an energy value ofus 140 which matches the lowest energy bit strength found by the comparative classical solver so that's great and this is the optimal folded structure of that nucleotide chain based on the lowest energy bit string the hardware has found and with that we have reached the conclusion of this episode now my aim here was not to overwhelm you with details from different research papers like I said I simply wanted to give you an all enough context understand what Cutting Edge

work in the field looks like right now the hope is that this will get some gears turning in everybody's head and that by seeing how others are approaching problems you will be able to make connections and have the confidence to attempt new Quantum experiments that you might not have before and hey maybe some of those won't pan out and that's fine that's why this is research going forward remember that the types of problems that we are interested in can be grouped by either methodology or by subject and we have laid out the ones that we

believe to be the most promising in the short term remember Quantum Computing isn't good for everything and really this is just a testament to how good we've gotten at classical Computing just because you think you could apply Quantum Computing to a problem doesn't mean it's going to yield interesting results unfortunately you have to consider the scaling circuit depth is a double-edged sword we need it to be considerably large to do interesting work that classical computers can't but right now because of the hardware noise we can't push it to huge sizes because the Fidelity will diminish

it's all about finding that sweet spot and knowing that it is a moving Target so take some time in between now and the next episode to really think about some problems that you have come across and how you might want to approach them with what we have learned up and to this point be creative and don't limit yourself and if you have any ideas even if you think they're a little bit crazy let me know in the comments below thanks for watching and I'll see you next time