On the complexity of simulating space-bounded quantum computations (Q1889853)

It is well known that quantum computations enable us to compute some functions much faster than deterministic or non-quantum probabilistic ones. For some problems, like factoring large integers, known quantum algorithms are exponentially faster than the best known deterministic ones. As a result, while it is possible to simulate a quantum computer on a non-quantum one, all known simulations require, in the worst case, an exponential increase in time. A natural question is: what about space? The author proves, for space, no large increase is needed for simulations: namely, we can simulate quantum computations that require space \(s\) by a probabilistic non-quantum computer with space \(O(s)\). Thus, we can simulate it on a deterministic non-quantum computer in space \(O(s^2)\). This result is similar to the known relation between non-deterministic and deterministic computations: if we simulate non-deterministic computations on a deterministic machine, time may grow exponentially but space only grows as \(O(s^2)\).