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 la...
详细信息
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].
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...
详细信息
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 zeroerror 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 zeroerror 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.
暂无评论