Approximating Combinatorial Optimization Problems ongoing

This project will explore to what extent near-term quantum computing may potentially provide better approximations to combinatorial optimization problems, bringing together expertise from quantum computing and applied mathematics. It is a collaborative effort within the Einstein Research Unit on Quantum Devices, involving the Freie Universität Berlin (FU Berlin), the Weierstrass Institute for Applied Analysis and Stochastics (WIAS), and the Zuse Institute Berlin (ZIB).

🧑‍🎓 Project Members

Jens Eisert
Principal Investigator
jense (at) zedat.fu-berlin.de
Michael Hintermüller
Principal Investigator
hint (at) mathematik.hu-berlin.de
Sebastian Pokutta
Principal Investigator
pokutta (at) zib.de

🪙 Funding

This project is being funded by the eru from January 2022 to December 2024.

🔬 Project Description

This project focuses on utilizing quantum computing to enhance the solutions of combinatorial optimization problems, which are crucial in various fields such as industrial resource management, logistics, and modeling natural phenomena. This collaboration between leading Berlin research institutions is funded by the Einstein Foundation. Quantum computing has emerged as a transformative paradigm with potential advantages over classical computing for certain problems. Combinatorial optimization, involving the assignment of discrete values to variables to minimize a cost function under constraints, is a prominent area where quantum computing might offer substantial benefits. Examples include the traveling salesperson problem, job scheduling, and protein folding. The project aims to establish a constructive proof that quantum computers can outperform classical ones in approximating combinatorial optimization problems. It involves developing quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), and evaluating their performance on near-term quantum devices. The research will compare these quantum algorithms against classical heuristic and approximation methods, identifying instances where quantum approaches excel. Additionally, the project will assess the impact of noise and other real-world conditions on quantum algorithms and propose strategies to mitigate these effects. Combinatorial optimization problems are often NP-hard, meaning no polynomial-time algorithm can efficiently solve all instances. However, practical instances can be managed with heuristics and approximation algorithms. This project seeks to advance the field by combining quantum and classical computational paradigms. Demonstrating a quantum advantage in optimization could revolutionize industries by providing faster and more accurate solutions, leading to more efficient supply chains, optimized resource allocation, and better modeling of natural processes.