Quantum implicit computational complexity

We introduce a quantum lambda calculus inspired by Lafont’s Soft Linear Logic and capturing the polynomial quantum complexity classes EQP, BQP and ZQP. The calculus is based on the “classical control and quantum data” paradigm. This is the first example of a formal system capturing quantum complexity classes in the spirit of implicit computational complexity — it is machine-free and no explicit bound (e.g., polynomials) appears in its syntax.