Quantum algorithms for optimization (QOPT)

The Quantum Algorithms for Optimization (QOPT) is a part of QuantERA ERA-NET Cofund in Quantum Technologies. The project is aimed at developing new quantum techniques for solving optimisation problems and applying them to real-life applications. This includes both continuous and discrete time optimisation. The project connects general optimisation problems with various techniques like smart search and quantum walks, and considers wide ranges of applications: machine learning, logistics, big data, and physics.

Optimisation is a major application for conventional computing and better optimisation algorithms would be of enormous practical importance. The range of applications in the project also has a significant impact. Machine learning and artificial intelligence is now widely used for many purposes, as exemplified by ChatGPT and similar advancements. Transportation and scheduling problems have a very significant practical importance. Better solutions to real-world logistics problems will be of a major economic value. Big data is also among the most important challenges in information processing, with larger and larger volumes of data being accumulated. The resource of interest is the amount of memory required to perform the desired computation, as it would not be realistic to store the entire data stream, especially on a quantum computer with limited memory. Last but not least, quantum physics also contains important optimisation problems whose solutions will contribute to progress in understanding nature.

Discrete optimisation problems are at the core of algorithm design, providing beautiful algorithmic techniques like dynamic programming, divide-and-conquer, flow algorithms. They are also important for hardness, many of them being NP-hard. In the project, related quantum primitives are designed: quantum dynamic programming, quantum divide-and-conquer, quantum graph algorithms. New variants of quantum walks are developed. Problems of finding the shortest path, solving edge connectivity and st-connectivity in graphs, and finding collisions in data are approached from the point of memory consumption.