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∈N1 and accepts a language
Ld∈/P. We further show that
Ld∈BPP, thereby separating
BPP from
P (i.e.,
P⫋BPP). Since the complexity class
BQP of {\em bounded error quantum polynomial-time computation} contains
BPP (i.e.,
BPP⊆BQP), our result confirms the long-standing conjecture that quantum computers are {\em rigorously more powerful} than classical deterministic computers (i.e.,
P⫋BQP). As an important consequence of the above results, we disprove the {\bf Extended Church-Turing Thesis}. Furthermore, we establish the following separations: (1)
P⫋RP; (2)
P⫋coRP; (3)
P⫋ZPP. These relationships were long-standing open questions in complexity theory. In addition, the separation
P⫋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
Ld cannot be reduced to
O(logn); (5) There exists no efficient (complexity-theoretic) {\em pseudorandom generator} (PRG):
G:{0,1}O(logn)→{0,1}n; (6) There exists no quick HSG
H:k(n)→n with
k(n)=O(logn).
This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection (
PostBQP=PostBPP), (ii) any one of several quantum sampling experiments (
BosonSampling,
IQP,
DQC1) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot (
FBQP=FBPP) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to
ZPPNP.