检索结果-内蒙古大学图书馆

The 1-Versus-2 Queries Problem Revisited

THEORY OF COMPUTING SYSTEMS 2010年第2期46卷 193-221页

作者： Tripathi, Rahul Univ S Florida Dept Comp Sci & Engn Tampa FL 33620 USA

The 1-versus-2 queries problem, which has been extensively studied in computational complexity theory, asks in its generality whether every efficient algorithm that makes at most 2 queries to a Sigma(p)(k)-complete language L-k has an efficient simulation that makes at most 1 query to L-k. We obtain solutions to this problem for hypotheses weaker than previously considered. We prove that: (I) For each k >= 2, P-tt(Sigma kp[2]) subset of ZPP(Sigma kp[1]) double right arrow PH = Sigma(p)(k), and (II) P-tt(NP[2]) subset of ZPP(NP[1]) double right arrow PH = S-2(p). Here, for any complexity class C and integer j >= 1, we define ZPP(C[j]) to be the class of problems solvable by zero- error randomized algorithms that run in polynomial time, make at most j queries to C, and succeed with probability at least 1/2 + 1/poly(.). This same definition of ZPP(C[j]), also considered in Cai and Chakaravarthy ( J. Comb. Optim. 11( 2): 189- 202, 2006), subsumes the class of problems solvable by randomized algorithms that always answer correctly in expected polynomial time and make at most j queries to C. Hemaspaandra, Hemaspaandra, and Hempel (SIAM J. Comput. 28(2): 383-393, 1998), for k > 2, and Buhrman and Fortnow (J. Comput. Syst. Sci. 59(2): 182-194, 1999), for k = 2, had obtained the same consequence as ours in (I) using the stronger hypothesis P-tt(Sigma kp[2]) subset of P-Sigma kp[1]. Fortnow, Pavan, and Sengupta (J. Comput. Syst. Sci. 74(3): 358-363, 2008) had obtained the same consequence as ours in (II) using the stronger hypothesis P-tt(NP[2]) subset of PNP[1]. Our results may also be viewed as steps towards obtaining solutions to arguably the most general form of the 1-versus-2 queries problem: For any k >= 1, whether P-tt(Sigma kp[2]) can be simulated in BPP Sigma kp[1].

关键词： Computational complexity Complexity classes Bounded queries zero-error algorithms

来源：评论

学校读者我要写书评

暂无评论

Uniformity of quantum circuit families for error-free algorithms

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期332卷 487-496页

作者： Nishimura, H Ozawa, M Japan Sci & Technol Agcy ERATO Quantum Comp & Informat Project Kamigyo Ku Kyoto 6020873 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

In order to establish the computational equivalence between quantum Turing machines (QTMs') and quantum circuit families (QCFs) using Yao's quantum circuit simulation of QTMs, we have previously introduced the class of uniform QCFs based on an infinite set of elementary gates, which has been shown to be computationally equivalent to polynomial-time QTMs up to bounded error simulation. However, the complexity classes ZQP and EQP introduced by Bernstein and Vazirani for QTMs do not appear to equal their counterparts for uniform QCFs. Recently, we have introduced a subclass of uniform QCFs, the class of finitely generated uniform QCFs, and showed that they are perfectly equivalent to the class of polynomial-time QTMs in the sense that both classes can be exactly simulated with each other. Here, we further investigate the power of uniform QCFs comparing with that of finitely generated uniform QCFs in detail. We obtain the following results: (i) If a permutation M-f : vertical bar x > -> vertical bar f (x)> can be implemented with zero error by a uniform QCF, then both f and f(-1) can be exactly computed by uniform QCFs. (ii) The quantum Fourier transform (QFT) of any order cannot be implemented with zero error by any finitely generated uniform QCF, while it has been shown, in contrast, by Mosca and Zalka that the QFT of any order can be exactly implemented by a uniform QCE. (c) 2005 Elsevier B.V. All rights reserved.

关键词： quantum computation complexity theory uniform circuit families zero-error algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：