Hacker News Reader

They can be simulated on classical computers, but in exponential time. In general, you need 2^n bits to represent n qubits.

You can see this in the case of a basic quantum gate, the hadamard gate:

H(a) produces a qubit with equal probably of being 1 or 0 if observed; H(H(a)) will always return the original value of A. Doing this to an entangled vector of qubits, performing another transform, then hadamard again produces a quantum circuit that takes an impractical number of classical bits to simulate.

> Can't quantum computers be simulated on classical computers?

The simulation gets exponentially slow, to the point that the fastest classical computers we have are not practical for simulating even modestly sized quantum systems.

Regarding (a), the approximation can be made as good as you want. However you are right on (b) it gets exponentially slow.

Yes; the title should probably include the word "efficiently."