2023/08/18 by Tianrong Lin, Lin, Tianrong
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2308.09549
In this paper, we extend the techniques developed in our previous work to construct a probabilistic Turing machine that runs within time O(nk) for every k∈ℕ1 and accepts a language Ld\notinP. We further show that Ld\inBPP, thereby separating BPP from P (i.e., P\subsetneqqBPP). Since the complexity class BQP of \em bounded error quantum polynomial-time computation contains BPP (i.e., BPP\subseteqBQP), our result confirms the long-standing conjecture that quantum computers are \em rigorously more powerful than classical deterministic computers (i.e., P\subsetneqqBQP). As an important consequence of the above results, we disprove the \bf Extended Church-Turing Thesis. Furthermore, we establish the following separations: (1) P\subsetneqqRP; (2) P\subsetneqq\rm coRP; (3) P\subsetneqqZPP. These relationships were long-standing open questions in complexity theory. In addition, the separation P\subsetneqqBPP demonstrates that \em randomness plays an essential role in probabilistic computation. In particular, we prove the following: (4) The number of random bits used by any probabilistic algorithm accepting Ld cannot be reduced to O(log n); (5) There exists no efficient (complexity-theoretic) \em pseudorandom generator (PRG): G:\0,1\O(log n)→ \0,1\n; (6) There exists no quick HSG H:k(n)→ n with k(n)=O(log n).