2023
,
Palackal, Lilly
,
Poggel, Benedikt
,
Wulff, Matthias
,
Ehm, Hans
,
Lorenz, Jeanette Miriam
,
Mendl, Christian B.
Many relevant problems in industrial settings result in NP-hard optimization problems, such as the Capacitated Vehicle Routing Problem (CVRP) or its reduced variant, the Travelling Salesperson Problem (TSP). Even with today's most powerful classical algorithms, the CVRP is challenging to solve classically. Quantum computing may offer a way to improve the time to solution, although the question remains open as to whether Noisy Intermediate-Scale Quantum (NISQ) devices can achieve a practical advantage compared to classical heuristics. The most prominent algorithms proposed to solve combinatorial optimization problems in the NISQ era are the Quantum Approximate Optimization Algorithm (QAOA) and the more general Variational Quantum Eigensolver (VQE). However, implementing them in a way that reliably provides high-quality solutions is challenging, even for toy examples. In this work, we discuss decomposition and formulation aspects of the CVRP and propose an application-driven way to measure solution quality. Considering current hardware constraints, we reduce the CVRP to a clustering phase and a set of TSPs. For the TSP, we extensively test both QAOA and VQE and investigate the influence of various hyperparameters, such as the classical optimizer choice and strength of constraint penalization. Results of QAOA are generally of limited quality because the algorithm does not reach the energy threshold for feasible TSP solutions, even when considering various extensions such as recursive and constraint-preserving mixer QAOA. On the other hand, the VQE reaches the energy threshold and shows a better performance. Our work outlines the obstacles to quantum-assisted solutions for real-world optimization problems and proposes perspectives on how to overcome them.
2022
,
Lorenz, Jeanette Miriam
,
Ehm, Hans
In this talk, we showcase how tools developed within the QuaST project (Quantum-enabling Services and Tools for industrial applications) will aid users in solving computationally hard industry applications using quantum computers. Today’s coding environment for quantum computers often only enables experts to develop and run quantum algorithms. QuaST aims to build a bridge from industrial challenges to quantum solutions. Together with the Fraunhofer Institutes AISEC, IKS, IIS and IISB, the Technical University of Munich, the Leibniz Supercomputing Centre, IQM, ParityQC, Infineon Technologies and DATEV, we co-design a software stack covering tools for hybrid HPC/QC algorithms for complex optimization problems, addressing topics from splitting large problems to high level mappings onto quantum hardware. By this, we target a wide range of different complex combinatorial problems such as network optimization or economical analyses. As a result of our developments, quantum computers will become more accessible such that their real advantage can be unveiled and utilized. Within this talk, we demonstrate our solutions using a representative example from the semiconductor industry. The semiconductor industry has inherently long lead times and is difficult to forecast, leading to a need in flexibility for its increasingly complex supply chain processes. Therefore, optimization is crucial to reach a competitive advantage in operational excellence. Plans and commitments for millions of external and internal orders need to be scheduled on a daily basis, resulting in huge optimization problems. By utilizing the power of quantum computers, we aim at getting results which are better optimized and more stable than those generated by current heuristics and classical solvers thus far.
