Probabilistic Computers (and Hence Quantum Computers) Are Rigorously More Powerful Than Classical Deterministic Computers, and Derandomization

Abstract

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\notin \mathcal{P}$. We further show that $L_d\in \mathcal{B}\mathcal{PP}$, thereby separating $\mathcal{B}\mathcal{PP}$ from $\mathcal{P}$ (i.e., $\mathcal{P}⫋\mathcal{B}\mathcal{PP}$). Since the complexity class $\mathcal{B}\mathcal{Q}\mathcal{P}$ of {\em bounded error quantum polynomial-time computation} contains $\mathcal{B}\mathcal{PP}$ (i.e., $\mathcal{B}\mathcal{PP}\subseteq \mathcal{B}\mathcal{Q}\mathcal{P}$), our result confirms the long-standing conjecture that quantum computers are {\em rigorously more powerful} than classical deterministic computers (i.e., $\mathcal{P}⫋\mathcal{B}\mathcal{Q}\mathcal{P}$). 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}⫋\mathcal{RP}$; (2) $\mathcal{P}⫋\mathrm{co}\mathcal{RP}$; (3) $\mathcal{P}⫋\mathcal{Z}\mathcal{PP}$. These relationships were long-standing open questions in complexity theory. In addition, the separation $\mathcal{P}⫋\mathcal{B}\mathcal{PP}$ 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)}\to \{0,1{\}}^n;$$ (6) There exists no quick HSG $H:k(n)\to n$ with $k(n)=O(\log n)$.

[v9] grammatical mistakes corrected and polished