Łukasz Pawela (IITiS PAS): Quantum runtime (dis)advantage

Łukasz Pawela (IITiS PAS): Quantum runtime (dis)advantage. Claims of quantum advantage increasingly depend not only on asymptotic scaling, but also on how runtime is defined and which classical baselines are used. In this talk, I will discuss two recent works that revisit these issues from complementary perspectives. First, we reconsider reported scaling advantages in approximate QUBO optimization and show that replacing PT-ICM with a stronger classical reference based on simulated bifurcation largely closes the previously reported quantum-classical gap, while also illustrating how conclusions drawn from small problem sizes can be misleading. Second, we introduce experimentally grounded, end-to-end runtime definitions for digital and analogue quantum computing and use them to reassess recent advantage claims under more realistic benchmarking assumptions. The main message is that credible quantum-classical comparisons must be full-stack. Runtime estimates should include relevant system-level overheads, performance should be measured with operationally meaningful metrics, and quantum methods should be compared against strong classical implementations rather than weak reference points. Center for Quantum-Enhanced Computing CTP PAS Seminar 2026-17-06