Le 24 octobre 2011, à 14h en salle B311, le séminaire LCR accueille Margherita Zorzi (LIPN, post-doc ANR Complice).

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, the polytime quantum lambda calculus SQ (inspired by soft linear logic) is presented, showing an Implicit Computational Complexity approach in the quantum setting.