Traq - Estimating the Quantum Cost of Classical Programs

Learn about Traq, a principled approach for automatically estimating quantum speedups of classical programs with provable guarantees in this 19-minute conference presentation from PLanQC 2026. Discover how this innovative framework addresses the challenge of predicting practical speedups offered by future quantum computers, moving beyond traditional manual analyses and numerical simulations that focus on single applications. Explore Traq's three core components: a classical language featuring high-level primitives amenable to quantum speedups, a sophisticated cost analysis system, and compilation to low-level quantum programs. Understand how the cost analysis provides fine-grained upper bounds on quantum program complexity, capturing non-asymptotic information while remaining sensitive to program inputs rather than providing worst-case scenarios. Gain insights into this automated approach that could revolutionize how the quantum computing community evaluates potential quantum advantages across diverse applications, presented by researchers from Ruhr University Bochum, Standard Chartered Bank, Max Planck Institute for Security and Privacy, and IMDEA Software Institute.