You’re right, but exponential slowdown eats a lot of gains in processor speed and memory. This could be a problem toward arguments of substrate independence.
Straight forward simulation is exponentially slower—n qubits require simulating amplitudes of 2^n basis states. We haven’t actually been able to prove that that’s the best possible we can do, however. BQP certainly isn’t expected to be able to solve NP-complete problems efficiently, for instance. We’ve only really been able to get exponential speedups on very carefully structured problems with high degrees of symmetry. (Lesser speedups have also been found on less structured problems, it’s true).
A classical computer can simulate a quantum one—just slowly.
You’re right, but exponential slowdown eats a lot of gains in processor speed and memory. This could be a problem toward arguments of substrate independence.
Straight forward simulation is exponentially slower—n qubits require simulating amplitudes of 2^n basis states. We haven’t actually been able to prove that that’s the best possible we can do, however. BQP certainly isn’t expected to be able to solve NP-complete problems efficiently, for instance. We’ve only really been able to get exponential speedups on very carefully structured problems with high degrees of symmetry. (Lesser speedups have also been found on less structured problems, it’s true).