Quantum and Probabilistic Computers Rigorously Powerful than Traditional Computers, and Derandomization
share
In this paper, we extend the techniques used in our previous work to show that there exists a probabilistic Turing machine running within time O(n^k) for all k∈ℕ_1 accepting a language L_d which is different from any language in 𝒫, and then to show that L_d∈ℬ𝒫𝒫, thus separating the complexity classes 𝒫 and ℬ𝒫𝒫 (i.e., 𝒫⊊ℬ𝒫𝒫). Since the complexity class of bounded error quantum polynomial-time ℬ𝒬𝒫 contains the complexity class ℬ𝒫𝒫, i.e., ℬ𝒫𝒫⊆ℬ𝒬𝒫, we thus obtain the result that quantum computers are rigorously powerful than traditional computers. Namely, 𝒫⊊ℬ𝒬𝒫. We further show that (1). 𝒫⊊ℛ𝒫; (2). 𝒫⊊co-ℛ𝒫; (3). 𝒫⊊𝒵𝒫𝒫. The result of 𝒫⊊ℬ𝒫𝒫 shows that randomness plays an essential role in probabilistic algorithm design. Specifically, we show that: (1). The number of random bits used by any probabilistic algorithm which accepts the language L_d can not be reduced to O(log n); (2). There exits no efficient (complexity-theoretic) pseudorandom generator (PRG) G:{0,1}^O(log n)→{0,1}^n; (3). There exists no quick HSG H:k(n)→ n such that k(n)=O(log n).
READ FULL TEXT