Quantum optimization
In a world of complex, multi-faceted problems, quantum computing offers a way to find the best path forward.
What is optimization?
Optimization is the art of finding the single best or optimal solution to a problem. In practice this consists of two steps: first find a rule or function for the problem that tells how good a solution is, and then search for the solution with the highest score. The first step is performed by experienced modelers, who are specialized in translating everyday problems into mathematics. They feed these functions into a computer, which then performs the second step for them.
As an example, let’s say we want to find the route from Delft to Amsterdam. Our route planner may find the shortest route, or the fastest one. We can make this problem more difficult by imposing additional restraints, such as avoiding highways, stopping at a friend’s house along the road who lives in Utrecht and minimizing the number of left turns we take. The more we demand, the more difficult both step 1 and step 2 become.
In the very complex problems that we may encounter in practice, step 2 can take longer than practically feasible on a classical computer. Moreover, although classical computers are good at finding solutions, finding really good solutions is very difficult: how can you be sure that the solution you found cannot be improved anymore? Quantum computers are hoped to improve performance both regarding the speed at which solutions are found, and the quality of the solutions. A specific type of quantum computer tailored to these problems, quantum annealers, are already available for purchase.
Quantum Annealing
The idea behind quantum annealing (also called adiabatic quantum computation) is a bit different from the “normal” quantum computer, in which gates are applied to the qubits. Instead, imagine it like rolling a ball in a landscape, which will naturally always roll to the lowest point. We start off with a simple landscape, with just one dip. If we drop a ball in here and wait long enough, we’ll know for sure it will end up in this trough. Now, the annealing computer will slowly transform this simple landscape into the system that we’d like to optimize. If we do this slowly enough, the ball will always remain at the lowest point, no matter where this point goes. When the transformation is completed, we only need to look at where the ball is to find the true optimum of the system – the solution of the problem we wanted to solve.
There is skepticism amongst scientists about quantum annealing, as there is no provable quantum speedup in general. Still, there are considerable efforts in this research direction: can quantum annealing beat existing optimization techniques in practice for a specific application?
Traffic Control
Improving traffic flow is one application for optimization. Traffic jams are not only a nuisance for drivers, they also cost time and money and have a negative impact on the environment. It is easy for a traditional computer to find the optimal route for a single car – any navigation system does this routinely. However, improving the overall traffic flow is a much harder problem: we need to be able to find an optimal route for a myriad of cars driving around simultaneously, or turn traffic lights green at appropriate times – and all of this in real time! This optimization problem has also been proposed to be solved by quantum methods.
In fact, a quantum annealer has already been used to improve traffic flow (albeit only for a few vehicles) in the context of a conference (the WebSummit) in Lisbon in 2019. The increase of visitors to a city during such a conference can cause traffic and public transport congestion. Volkswagen tried to use a quantum computer to optimize the bus service during this conference for nine municipal buses called Quantum Shuttles. The two ingredients to be optimized were the route (by avoiding congested places) and the number of passengers on board of the buses, using a prediction algorithm that predicts the most crowded bus stops. Each bus driver was connected to a quantum computer via an app, which recommended an optimal route to the drivers in near real-time. These drivers could then redirect their buses, picking up passengers at the most crowded stops along the way. Clearly, those nine buses could also have been optimized with a traditional computer. Still, it was the application of a quantum computer to a real-life problem.
Industrial Interest
Optimization problems are ubiquitous in industry: finding the most effective way to produce, optimize supply chains, or load cargo. Even small improvements can lead to significant profit enhancement. It is thus not surprising that industry is interested in exploring quantum optimization techniques.
For example, in 2020 aircraft manufacturer Airbus launched the Airbus Quantum Computing Challenge, in which people were challenged to come up with ways for quantum computers to impact the aviation industry. The winning entry used quantum annealing to optimize cargo loading. Ideally, aircraft operators would like to haul as much load as possible, stacking cargo like a giant game of Tetris. This reduces the number of cargo flights, benefiting both profits and the environment. However, you cannot arbitrarily stack all goods in the most tight way. Doing so may result in an off-centered weight distribution, making the aircraft too unstable to fly. There is an optimum for a maximum load with a minimal weight shift, enhancing the fuel efficiency of airplanes and reducing the number of cargo flights. Again, whether a quantum approach outperforms previous methods still needs to be seen also for this problem.
Optimization problems are ubiquitous in industry... even small improvements in the optimization can lead to significant profit enhancement.
Competition with traditional computers
Optimization problems are typically hard in that there is no feasible procedure that guarantees to find the best solution. Instead, traditional computers usually rely on algorithms that find a “good enough” result. Quantum computing is attractive in that it is a new approach that may find even better solutions. At the same time, this competition has also inspired traditional computer scientists to find improved algorithms. Even better, the understanding why a quantum approach runs faster can sometimes also be used to design better, quantum-inspired algorithms running on traditional computers. For example, recent research has made progress in modeling fluid turbulence using a quantum-inspired approach. In addition, the combination of concepts from quantum computing and traditional computer science has given rise to new research directions, such as quantum machine learning.
Quantum computing has thus already indirectly benefited optimization problems, inspiring and enabling new research directions. The constant competition between traditional computers and quantum computers in this field, however, makes it difficult to say when (or if) quantum computers will be of practical use.
The Fine Print
The limiting factor of quantum annealing is the “gap” – which can be considered the difference between the best and the second-best solution. This gap typically becomes smaller when the problem size becomes bigger. The gap size determines how fast the quantum annealer can run: the smaller the gap, the slower the annealer needs to transform the landscape and the longer the computation takes. If the annealer runs too fast, it will inevitably end up in a non-optimal solution, as the system will “jump” across the gap from the best solution to worse ones. In other words, the more complicated the problem gets and the more qubits we need to add, the longer we must wait. For this reason, it is believed that quantum annealing offers no quantum speedup in general. There could be specific problems though that can benefit.