3 ms·
No, they can run on quantum computers, but to properly simulate a quantum computer, you may need exponential space/time. Googling for supporting data brought up
by devinj 16y ago
No, they can run on quantum computers, but to properly simulate a quantum computer, you may need exponential space/time. Googling for supporting data brought up http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html which discusses simulating Shor's algorithm on a classical computer.
The reason for the exponential is that the bits are all in a superposition of all possible states (so for a 14-bit register, that's a superposition of 2 to the 14 states), which operations all act on. Or something like that. I'm not really that clear on the details. :(
- bdhe 16y ago> Or something like that. I'm not really that clear on the details. :( Your intuition is correct. Quantum algorithms seem to perform better than classic algorithms because there are certain operations (like fourier transforms) that can be performed exponentially faster (as of today) than classic algorithms. It is still unknown however whether or not we can simulate quantum computations classically without exponential blowup otherwise it would resolve major open questions in complexity theory.