Simulate a quantum computer on a normal one

Question

Would it be possible to simulate a quantum computer on a normal computer. I was thinking something like have a bunch of GPU's running a set of entangled quantum particles and then produce the results. Would this be feasible or one of those take the lifetime of the universe to run problems?

Answer 1

It is definitely possible to simulate a quantum computer on a classical one, but as you point out the real question is whether it can be done efficiently.

The calculations a quantum computer is doing are not fancy mathematics: it is all linear algebra in terms of unitary evolution and projective measurement of a finite-dimensional quantum system. However, if you have $n$ qubits the dimension of the state space rises as $2^n$ so that you very soon have unmanageably large matrices, and even efficient linear algebraic algorithms (in terms of matrix size) become exponentially-scaling ones.

There are a number of known quantum-computational algorithms that can be efficiently simulated with a classical computer (take for example the Gottesman-Knill theorem) and it is an ongoing research area as to which calculations can and cannot be thus simulated. If (as appears to be the case) factoring cannot be efficiently done on a classical computer, then Shor's algorithm is an example of the latter.