Probabilistic Computers (and Hence Quantum Computers) Are Rigorously More Powerful Than Classical Deterministic Computers, and Derandomization
Tianrong Lin · arXiv (Cornell University) · 2023
In this paper, we extend the techniques developed in our previous work to construct a probabilistic Turing machine that runs within time $O(n^k)$ for every $k\in\mathbb{N}_1$ and accepts a language $L_d otin\mathcal{P}$. We further show that $L_d\in\mathcal{BPP}$, thereby separating $\mathcal{BPP}$ from $\mathcal{P}$ (i.e., $\mathcal{P}\subsetneqq\mathcal{BPP}$). Since the complexity class $\mathcal{BQP}$ of {\em bounded error quantum polynomial-time computation} contains $\mathcal{BPP}$ (i.e., $\mathcal{BPP}\subseteq\mathcal{BQP}$), our result confirms the long-standing conjecture that quantum computers are {\em rigorously more powerful} than classical deterministic 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 establish the following separations: (1) $\mathcal{P}\subsetneqq\mathcal{RP}$; (2) $\mathcal{P}\subsetneqq{\rm co}\mathcal{RP}$; (3) $\mathcal{P}\subsetneqq\mathcal{ZPP}$. These relationships were long-standing open questions in complexity theory. In addition, the separation $\mathcal{P}\subsetneqq\mathcal{BPP}$ 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 $L_d$ cannot be reduced to $O(\log n)$; (5) There exists no efficient (complexity-theoretic) {\em pseudorandom generator} (PRG): $$ G:\{0,1\}^{O(\log n)}\rightarrow \{0,1\}^n;$$ (6) There exists no quick HSG $H:k(n)\rightarrow n$ with $k(n)=O(\log n)$.