Quantum Optimization: Lessons from Airbus x BMW Quantum Computing Challenge

Key Takeaways 

• Classical optimization remains powerful. Traditional methods still efficiently solve complex industrial problems today.
• Quantum offers future potential. Quantum optimization may eventually solve larger problems and more complex models than are possible today, but it needs innovation now.
• Hybrid solutions are the future. Combining classical and quantum methods will deliver the best results, not by replacing one with the other but by leveraging the strengths of both.
• Skepticism is essential. Many quantum claims are exaggerated; rigorous benchmarking against classical methods is crucial.

Introduction

Building optimal supply chains that balance complex business constraints is an algorithmically challenging task, but one that is critical for industry. Our team recently won the optimization track of the Quantum Mobility Quest, organized by Airbus and BMW, for work in supply chain design. In this article, I’ll share what we learned, what quantum optimization can do today and the potential it holds for the future.

Quantum Optimization Challenge

Last year, we had the opportunity to participate, together with Konstantin Kutzkov, in the Quantum Mobility Quest, a quantum optimization challenge organized by Airbus and BMW, with support from Amazon Web Services and The Quantum Insider. Our task was to solve a real-world supply chain design problem faced by automotive and aerospace companies assembling complex systems from numerous sourced parts and processing them in a global network of facilities.

Optimizing such large-scale, interconnected supply chains – balancing cost, emissions and resilience – quickly becomes too complex for even the most powerful classical computers. Yet even small improvements to these solutions can lead to significant financial savings and environmental benefits. The goal of the Quantum Mobility Quest was to explore whether quantum computing can deliver better solutions in the future.

Our team from 4colors Research won the challenge! This article will share what we learned about quantum optimization, its current capabilities and future potential.

The Quantum Mobility Quest consisted of five independent tracks, each exploring a different potential application of quantum computing in the automotive and aerospace industries. The competition attracted more than 400 registered teams and 100 submissions. In phase 1 of the competition, from January to April 2024, teams submitted their initial solutions, and in phase 2, from June to August 2024, three finalists per track refined and benchmarked their solutions in collaboration with experts from Airbus and BMW and received feedback. After several months of competition, judged by a panel of industry and academic experts, the winners were announced in December 2024 at Q2B 2024 Silicon Valley, with an award ceremony held at the Computer History Museum in Mountain View, California.

Quantum Logistics

Our team participated in the Quantum-Powered Logistics track, which focused on integrated production and transportation planning. The task was to optimize the assignment of parts to assembly sites to minimize both direct costs (production and transportation) and indirect costs (such as CO2 emissions). This challenge was rooted in the complexity of manufacturing products like aircraft and automobiles, which are assembled from thousands or even millions of parts globally sourced – often with multiple sourcing options per part.

Each assembly site receives components, builds subassemblies and ships them to the next stage, creating a highly interconnected production network. Decisions around sourcing, transport mode (air, sea or land) and facility choice must be made simultaneously. Each of these choices affects the overall efficiency, cost, emissions and lead times across the supply chain. The core challenge was to make these interdependent decisions in a way that achieves the best global configuration, balancing financial, environmental and operational constraints.

Quantum Optimization Today

Quantum optimization is a field focused on leveraging quantum computers to accelerate solving complex optimization problems. Although today’s classical solvers can handle many large-scale optimization challenges, there is always a need to address larger and more integrated problems – instances that, for computational reasons, we currently need to break down into smaller stages or simplify. Quantum optimization offers the potential to solve larger, more complex models, which could bring significant benefits to industries managing large-scale operations.

There are two main approaches to quantum optimization commonly discussed today. One approach involves mapping problems into QUBO (Quadratic Unconstrained Binary Optimization) form. This formalism has gained popularity because several vendors produce quantum machines based on quantum annealing or quantum-inspired hardware accelerators that use QUBO. There is also an approximation technique known as the Quantum Approximate Optimization Algorithm (QAOA), which runs on gate-based quantum computers. From an optimization perspective, both of these techniques can be viewed as (hardware-based) QUBO heuristics.

However, a key challenge is that many real-world optimization problems, such as mixed-integer programming (MIP), scheduling or routing problems, do not naturally fit into the QUBO format. Transforming these problems into QUBO often causes the problem size to grow substantially, making them harder to solve.

The other key quantum optimization method is amplitude amplification, which is used in Grover’s algorithm. This technique can, for example, be used to find the minimal element in a set of N elements, with the search complexity proportional to the square root of N. This represents a significant improvement over classical methods, which require examining all elements to find the minimum. These two techniques, QUBO-based methods and amplitude amplification, seem to cover much of the literature and commercial efforts in quantum optimization.

Quantum optimization holds great promise, but no exponential speedup for an optimization problem has yet to be demonstrated – and it might never. For quantum computers to achieve substantial gains in optimization, based on what we know today, they would need to be much larger and more reliable than those currently available. At present, the industry is in the NISQ (Noisy Intermediate-Scale Quantum) era, in which devices remain limited by constraints in scale, noise and fidelity.

Our Approach: Optimizing Complex Supply Chains

Our approach was grounded in mathematical optimization. We initially approached the problem purely from a classical computing perspective without considering quantum computing. We developed an integrated model that simultaneously captured both production and transportation decisions, resulting in a large-scale and computationally complex MIP problem. In fact, even after preprocessing, our instances were larger than 90% of the problems in the MIPLIB 2017 benchmark.

Such problems are notoriously difficult for standard MIP solvers – not only are they unlikely to be solved to optimality, but often, no feasible solution is found within a reasonable time frame. However, the problem structure exhibited useful properties that allowed us to design a matheuristic – a heuristic algorithm built around and informed by the underlying MIP formulation.

We leveraged these properties to develop a hybrid method that incorporated multiple components, such as linear programming relaxation, rounding, feasibility pumps, local search and path relinking. This matheuristic proved capable of efficiently finding feasible and high-quality solutions to the original problem. Now it was time to consider whether quantum computing could provide a speedup.

To explore this, we analyzed our algorithm to identify opportunities for quantum acceleration. We focused on enhancing specific components – particularly, local search and path relinking – and developed their quantum variants. These quantum routines were designed to exploit the properties of quantum computing to offer a speedup over their classical counterparts.

Behind all our quantum versions of classical methods lies a quantum routine that approximately solves small MIP subproblems. We implemented this routine using two different quantum optimization approaches: one based on amplitude amplification (inspired by Grover’s algorithm) and the other using QAOA.

Another key component of our algorithm is a machine learning model trained using reinforcement learning. This model makes real-time decisions during the algorithm’s execution, particularly in determining how to create instances that will be sent to the quantum computer, ensuring optimal overall progress of the algorithm.

Although today’s quantum hardware is still constrained by scale and noise, we provided a working proof of concept and demonstrated that our algorithm produces the expected results even on the small and noisy devices available. We also showed that as quantum hardware matures, our algorithms are positioned to deliver substantial speedups. In fact, some parts of our approach are provably faster when run on a quantum machine, but achieving these gains in practice will require significantly larger quantum computers. Our solution is hybrid by design: It runs efficiently on classical hardware, performs reliably on current NISQ devices, and is ready to incorporate quantum acceleration as the quantum technology evolves and begins to offer real speedups.

Lessons Learned

1. Classical optimization remains extremely powerful. Many businesses exploring quantum technologies realize that their core challenges are, fundamentally, optimization problems. This rediscovery highlights the value of mathematical optimization, a field that consistently delivers strong business results. Classical optimization is highly effective, even if compromises are sometimes necessary because of computational limits.
2. Quantum optimization offers future potential but requires innovation today. Although classical methods are currently capable of solving real-world problems, quantum technologies hold the promise of addressing even larger and more integrated problems. This is especially important as businesses aim to model increasingly complex systems. Preparing for quantum advances will require not just better hardware but also continued innovation in optimization algorithms, mirroring the significant progress achieved in classical solvers over the past decades.
3. Quantum optimization demands new algorithmic thinking. Quantum computing is not just a different kind of hardware; it also requires a fundamentally new approach to software and algorithms. Future optimization solvers will likely be hybrid, using quantum processing units (QPUs) to accelerate specific computational bottlenecks. Embracing this shift demands entirely new approaches and new algorithmic thinking.
4. Skepticism is necessary in today’s quantum landscape. The quantum computing space is filled with bold but often unsubstantiated claims. Many supposed breakthroughs in quantum optimization have not been rigorously benchmarked against strong classical baselines. Commercial claims of “quantum advantage” in tasks like scheduling or routing, for example, should be treated with healthy skepticism. Transparent and rigorous evaluation is essential for genuine progress.
5. The future is hybrid: combining classical and quantum optimization. Classical optimization is a mature and powerful field that quantum methods should build upon, not replace. Quantum computing is most relevant today for large companies focused on long-term gains and cutting-edge research. For many businesses, especially in simpler applications, the quantum advantage remains distant. Ultimately, new quantum discoveries often lead to advancements in classical methods, benefiting the broader optimization community.

Quantum optimization is an additional tool in the optimization toolbox. It may prove effective for all types of problems. Whereas exponential speedups remain elusive for many real-world challenges, some quadratic speedups have been demonstrated, showing practical significance in certain cases. If quantum optimization fulfills its promise, the future will likely be hybrid. There will be no need to choose between classical and quantum methods; instead, these approaches will most likely complement each other and work together seamlessly.

Now is the time for organizations with the resources and vision to invest in long-term projects to use quantum optimization because it requires sustained commitment to reach its full potential. It is important, however, not to overlook the problems that businesses can solve using classical methods without quantum computing. Such opportunities will naturally emerge during work on quantum methods; delivering classical solutions can produce value for businesses right now.

Classical optimization has already proven to be highly effective and will continue to provide excellent results for many problems. At the same time, as quantum computing technology matures, it holds great potential to become a valuable tool in our optimization toolbox. Quantum computing is not in competition with classical methods. Ultimately, any progress in this area will benefit the end users of optimization technologies by enabling faster problem solving and higher-quality solutions.