3 ms·
In fact both quantum computers and nondeterministic computers can perform a computation on all possible inputs simultaneously. The difference is in what happens
by OscarCunningham 9y ago
In fact both quantum computers and nondeterministic computers can perform a computation on all possible inputs simultaneously. The difference is in what happens afterwards.
A nondeterministic computer halts in the "success" state if any of the individual threads halted succesfully. This turns out to be tremendously useful.
A quantum computer run on a quantum superposition of all possible inputs gives you a superposition of the outputs. If you we're to measure it directly you would just get one of the outputs chosen at random. This not useful. But sometimes (on particular problems with a suitable structure) further work can be done on the superposed state before measuring it, in such a way that the results of the measurement are useful.
- kgwgk 9y ago> If you we're to measure it directly you would just get one of the outputs chosen at random. The point is that not all the outputs are equally probable and (in the interesing cases) you will get the “right” answer with high probability.
- OscarCunningham 9y agoMy point is that if you do it the naive way then they are all equally likely. You need to do something extra to make the ones you want more likely. And this only works in some cases. (I guess Grover's algorithm works in all cases, but it's not a exponential speedup.)
- kgwgk 9y agoI thought that something extra was part of “running a quantum computer”.