Quantum implicit computational complexity

作     者：Dal Lago, Ugo Masini, Andrea Zorzi, Margherita 

作者机构：Univ Bologna Dipartimento Sci Informaz I-40126 Bologna Italy Univ Verona Dipartimento Informat I-37100 Verona Italy 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2010年第411卷第2期

页      面：377-409页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：FIRB  (RBIN04M8S8) 

主　　题：Quantum computation Implicit computational complexity Lambda calculus 

摘      要：We introduce a quantum lambda calculus inspired by Lafont s Soft Linear Logic and capturing the polynomial quantum complexity classes EQP, EQP 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. (C) 2009 Elsevier B.V. All rights reserved.