On Classical Simulation of Quantum Machines

摘要

We present a classical probabilistic simulation technique of quantum Turing machines. As a corollary of this technique we obtain several results on relationship among classical and quantum complexity classes such as: PrQP = PP, BQP is contained in PP and PrQSPACE(S(n)) = PrPSPACE(S(n)).