Can quantum technology assist in the next COVID crisis? Part 2
Blog: Capgemini CTO Blog
In a series of three articles we will zoom in on three potential applications of quantum computing in light of the COVID-19 pandemic. This second article will focus on the optimization challenges.
Effective pandemic response requires optimization models for planning of ICU beds, ventilators and other medical equipment. Besides direct impact on public health, the coronavirus has a large indirect impact on supply chain operations. Take for example the worldwide run on toilet paper when lockdowns first started. The fast increase in demand triggered a bullwhip response through the supply chain, leading to procures hastily trying to match demand. However, demand dried up before they were able to catch up, resulting in costly overproduction. Although the run on toilet paper is a recognizable case, it was not alone in suffering the bullwhip effect. Virtually every supply chain has been subjected to the effects of the corona crisis in one way or another. Supply chains are governed by optimization problems in the best of times. Now, in times of dramatic shift, fast rebalancing of resource allocation and scheduling, optimizations models seem ever more important.
Even under normal circumstances it is difficult to address optimization problems. Every day, large computer systems are used to optimize almost every aspect of the value chain. Mathematically speaking, this is because many optimization problems are NP-Hard. This means that an efficient algorithm for classical computers to get the optimal solution does not exist. Very common problems, like the traveling salesman (that can be used for efficiently delivering resources) or the satisfiability problem (that can be used for efficiently scheduling resources such as ventilators), scale exponentially. Even for small problem instances, classical computers aren’t able to solve the problem exactly.
Take for example the traveling salesman problem, which describes the problem of determining the quickest route through a number of cities. Even for just a few cities, the number of paths get so large that classical computers take an inordinately long time to calculate the best route. In practice however, classical computers do not solve these problems exactly. Instead, they address the problem heuristically, meaning that shortcuts and tricks are used to find a faster solution. This also means that instead of finding the best solution, these algorithms look for a sub-optimal solution. In some cases, this might be good enough. For many other problems, improving the accuracy by just a few percent can be a game changer, as is the case with the bullwhip due to the coronavirus. In this case, besides having a heavy optimization problem, it also happened suddenly and unexpectedly, urging for fast rebalancing of supply chain optimization.
It is unlikely that quantum computers will solve the above mentioned optimization problems. However, even a slightly better or slightly faster solution can have an enormous impact.
There are two types of quantum algorithms that may be used for such optimization problems, heuristic algorithms and algorithms based on quantum random walks.
Heuristic algorithms do not have an analytical proven speed-up. For every case, actual experimentation for real use cases on real hardware has to be performed to evaluate a potential speed-up. A quantum algorithm that seems promising is the quantum approximate optimization algorithm (QAOA). QAOA is also a hybrid quantum algorithm, meaning that the algorithm is suitable for near-term quantum computers.
Algorithms in the second category, those based on quantum random walks, have a proven quadratic speed-up over classical algorithms. Algorithms in this category include Grover’s algorithm (for unstructured searches) or amplitude amplification. Contrary to QAOA, these are pure quantum algorithms, leading to larger circuit depths. Also, a quadratic speed-up is less spectacular than the exponential speed-up in quantum chemistry. However, given the wide use of such optimization problems, algorithms such as Grover’s are highly anticipated.
Ultimately, quantum computers may be able to improve the solutions of optimization problems by providing nearer-optimal solutions for larger problem spaces in less time. For resource allocation problems, such as ventilator distribution, this means materials are used more efficiently, and the equations can be quickly recalculated when needed.
Even though the added value of quantum computing is still a couple of years down the line, we should prepare for it. Without dismissing the great technological developments that have been made before and during the current pandemic, different skillsets will likely be required in applying quantum computing versus using classical computing. This stems from the fact that the very foundation of quantum computing is different and therefore the layers building on that foundation, such as programming languages, will be different too. If quantum computers are to become mainstream in ten years, students should enroll today.
Download TechnoVision and get a handy guide to pivot in these challenging times.
This article is the second out of a series of three, co-authored by Renate Wolters and Julian van Velzen. Read Part 1 here. Stay tuned for part 3 – the coronavirus evolution as a machine learning application. We will also zoom in on the overall conclusion of the potential of quantum computing in complex situations like COVID-19.
Leave a Comment
You must be logged in to post a comment.
