文章基本信息

标题：NQP = co-C_{=}P
本地全文：下载
作者：Tomoyuki Yamakami ; Andrew Chi-Chih Yao
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Adleman, DeMarrais, and Huang introduced the nondeterministic quantum polynomial-time complexity class NQP as an analogue of NP. Fortnow and Rogers showed that, when the amplitudes are rational numbers, NQP is contained in the complement of C_{=}P. Fenner, Green, Homer, and Pruim improved this result by showing that, when the amplitudes are arbitrary algebraic numbers, NQP coincides with co-C_{=}P. In this paper we prove that, even when the amplitudes are arbitrary complex numbers, NQP still remains identical to co-C_{=}P. As an immediate corollary, BQP differs from NQP when the amplitudes are unrestricted.