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.
Quantum Implicit computational complexity
MASINI, Andrea;ZORZI, Margherita
2010-01-01
Abstract
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
