Margherita Zorzi (LIPN, Paris)

An introduction to quantum complexity and quantum ICC

One of the strong motivations behind quantum computing is computational complexity: quantum computers seem to be able to solve efficiently classical hard problems, thanks to the potential speed up in the execution time induced by superposition phenomena. Quantum complexity theory has been developed since the Nineties, after the definition of quantum computational models such as quantum Turing machines and quantum circuit families. A particular attention is devoted to the quantum polytime classes (EQP, BQP, ZQP). After a preliminarily discussion about quantum models and quantum complexity theory, we show an Implicit Computational Complexity approach in the quantum setting. The polytime quantum lambda calculus SQ is presented. SQ is a calculus with classical control inspired by Soft Linear Logic. SQ enjoys some good classical and quantum properties and captures implicitly the three classes of quantum polytime. Completeness result is given exploiting the Yao's encoding of the quantum Turing machine into the quantum circuits model.