Title: Programming Languages for Quantum Polynomial Time
Speakers: Mário Silva (Université de Lorraine)
Invited by: Alcides Fonseca and Vasco Vasconcelos
When: Friday, September 20, 14h
Where: FCUL, 6.3.27

Abstract: In this talk, Mário Silva will present his PhD work, which focuses on developing static-analysis techniques for quantum programming languages that ensure polynomial-time termination and correct handling of qubit variables (e.g. no cloning, no deletion). We will also see that finding efficient (i.e. polysized) circuit implementations of quantum polytime programs is not trivial, due to problems such as “branch sequentialization”, and we will explore techniques that ensure correct asymptotic size bounds for a language that is sound and complete for quantum polynomial time. If time allows, we will look at the same ideas in the context of quantum polylogarithmic time.

Bio: Mário Silva is in the final year of his PhD in computer science at the Université de Lorraine, in Nancy, France, under the supervision of Romain Péchoux and Emmanuel Hainry. He did his Licenciatura in Physics at Universidade do Porto, and his Master’s in Mathematics at Instituto Superior Técnico, with a thesis on device-independent quantum cryptograhpy.
His current work falls mostly within the field of implicit computational complexity, which studies characterizations of complexity classes via purely syntactical means, either using function algebras, lambda calculi, or restricted programming languages. Mário’s work focuses on implicit characterizations of quantum complexity classes, with applications to efficient compilation techniques.