Quoting here from Quantum Computation by Nielsen and Chuang :

(Gottesman–Knill theorem) Suppose a quantum computation is performed which involves only the following elements: state preparations in the computational basis, Hadamard gates, phase gates, controlled-NOT gates, Pauli gates, and measurements of observables in the Pauli group (which includes measurement in the computational basis as a special case), together with the possibility of classical control conditioned on the outcome of such measurements. Such a computation may be efficiently simulated on classical computer.

A few lines further:

Consider that interesting quantum information processing tasks like quantum teleportation (Section 1.3.7) and superdense coding can be performed using only the Hadamard gate, controlled-NOT gate, and measurements in the computational basis, and can therefore be efficiently simulated on a classical computer, by the Gottesman–Knill theorem.

Does this mean that quantum teleportation can be efficiently simulated on a classical computer? What does that mean?


1 Answer 1


I don't really know what answer you expect here.

As you have found out yourself, the Gottesman-Knill theorem tells you that stabilizer circuits can be efficiently simulated by a classical computer. Teleportation can be implemented that way, hence you can efficiently simulate it on a classical computer.

What does that mean? Well, give the computer a random state, it can perform the teleportation protocol and the simulation time will be polynomial in the dimension of the state. This also means that using teleportation alone can't give you any exponential speedups.

Note however that there is a very small caveat: You cannot prepare all states with stabilizer circuits, i.e. if you want to first create a special state and then teleport it, the time of the simulation doing both might increase more than polynomially in the dimension of the state!

  • 1
    $\begingroup$ Not that the teleportation is simply the identity operation (same input as output), so it is no surprise it can be simulated on a classical computer... $\endgroup$ Dec 21, 2015 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.