Production & Logistics: Quantum algorithms for multi-knapsack optimization problems



Optimizing modern supply chains pushes classical computers to their limits

Many products today are manufactured not in a single factory, but in entire networks of production facilities. Optimizing such modern supply chains is often a special challenge for companies. It exists in global production processes across a wide range of industries, from automotive and semiconductors to chemicals, and requires continuous planning and communication across all production sites involved. In addition, optimizing supply chains is important to make them more cost-effective, sustainable, as well as resilient to disruptions, such as through more efficient use of storage capacity, improved logistics, optimized work schedules, and reduction of CO2 emissions.

Mathematically, many of these optimization challenges can be described as belonging to the class of multi-knapsack problems. Classical computers can hardly solve such complex problems. Quantum computers, on the other hand, promise much better and faster solutions.


Comparison of different quantum algorithms for multi-knapsack problems © QUTAC


New QUTAC study: possibilities of quantum computing in supply chain optimization

Recently, the field has seen the development of various different types of quantum algorithms for optimization problems, as well as numerous variants thereof. In our current study, which we will present at the Computing Conference 2023 in London, we compare and extend different gate-based variational quantum algorithms and quantum annealing for multi-knapsack optimization problems from an application perspective. In doing so, we show that the use of these modified algorithms leads to improved solution quality. Furthermore, we discuss the execution of these quantum algorithms on existing quantum computers, as well as the limitations involved.

A major challenge is that both current and near-term quantum computers have a limited number of qubits and are prone to errors. To solve real application problems with these devices, it is necessary to modify existing quantum algorithms as well as problem formulations accordingly and adapt them to the architecture of the underlying quantum hardware.

The results of our study may also be useful for other users of quantum computers dealing with optimization problems, helping them to get a better overview of the multitude of quantum algorithms.


The paper can be accessed at the following link on Arxiv: