Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
For complexity theorists, the paper claims to resolve long-standing open problems about the power of randomness and quantum computation, but the results are highly controversial and likely incorrect given the current understanding of complexity theory.
The paper claims to prove that BPP strictly contains P (P ⊊ BPP) by constructing a language L_d in BPP but not in P, which would imply quantum computers are strictly more powerful than classical ones (P ⊊ BQP) and disprove the Extended Church–Turing Thesis. It also claims to separate P from RP, co-RP, and ZPP, and to show that randomness cannot be reduced to O(log n) bits for L_d, implying no efficient pseudorandom generator exists.
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\in\mathbb{N}_1$ accepting a language $L_d$ that is different from any language in $\mathcal{P}$, and then further to prove that $L_d\in\mathcal{BPP}$, thus separating the complexity class $\mathcal{BPP}$ from the class $\mathcal{P}$ (i.e., $\mathcal{P}\subsetneqq\mathcal{BPP}$). Since the complexity class $\mathcal{BQP}$ of {\em bounded error quantum polynomial-time} contains the complexity class $\mathcal{BPP}$ (i.e., $\mathcal{BPP}\subseteq\mathcal{BQP}$), we thus confirm the widespread-belief conjecture that quantum computers are {\em rigorously more powerful} than traditional computers (i.e., $\mathcal{P}\subsetneqq\mathcal{BQP}$). As an important consequence of the above results, we disprove the {\bf Extended Church--Turing Thesis}. Furthermore, we also show that (1): $\mathcal{P}\subsetneqq\mathcal{RP}$; (2): $\mathcal{P}\subsetneqq{\rm co-}\mathcal{RP}$; (3): $\mathcal{P}\subsetneqq\mathcal{ZPP}$. Previously, whether the above relations hold or not were long-standing open questions in complexity theory. Meanwhile, the result of $\mathcal{P}\subsetneqq\mathcal{BPP}$ shows that {\em randomness} plays an essential role in probabilistic algorithm design. In particular, we go further to show that (1): The number of random bits used by any probabilistic algorithm that accepts the language $L_d$ can not be reduced to $O(\log n)$; (2): There exists no efficient (complexity-theoretic) {\em pseudorandom generator} (PRG). $$ G:\{0,1\}^{O(\log n)}\rightarrow \{0,1\}^n; $$ (3): There exists no quick HSG $H:k(n)\rightarrow n$ such that $k(n)=O(\log n)$.