23 November 2026, 13:00
Vilnius, Akademijos St. 4, Room 203
Online via MS Teams (https://bit.ly/DMSTI_2026-11-23)
Dr. Andreea-lulia Lefterovici
(Blockchain and Quantum Technologies Group)
„How do we quantify the resources a quantum computer needs to solve a problem?“
Abstract: Combinatorial optimisation is a main topic for real-world applications, where fast solutions are required. Optimisation algorithms are incredibly powerful, but still face bottlenecks for certain problems. In recent years, quantum algorithms have been proposed as a potential candidate for solving such problems. The question that naturally arises is whether they could provide meaningful speed-ups over classical approaches. The study of asymptotic complexity has become central in the development of quantum algorithms. Nevertheless, having a promising asymptotic improvement does not directly translate into good practical performance. This is already well known for classical algorithms, which can be executed and evaluated directly. When it comes to quantum algorithms, the situation is more nuanced, as solving practically relevant instances would require a fully fault-tolerant quantum computer. In this presentation, I will present how we address the challenge of assessing the practical performance of a quantum algorithm without access to quantum hardware. Our strategy is to evaluate how these algorithms would perform under idealised fault-tolerant assumptions and to identify parameter regimes in which quantum approaches could potentially become useful. Our goal is to guide algorithmic development long before implementation becomes possible.