4 ms·

> The "trying all possible solutions simultaneously" explanation of qc. This is a very common explanation, and from what I gather from Scott's comments is that

by rspeer 9y ago

> The "trying all possible solutions simultaneously" explanation of qc. This is a very common explanation, and from what I gather from Scott's comments is that it's inaccurate for TSP, but possibly right for problems that are better structured to use the technology(?) From what I gather from Scott's comments (and the tagline of his entire blog), this common explanation is basically always incorrect. Quantum algorithms do not try all solutions simultaneously. That's a description of the theoretical model of nondeterministic computing (like where "NP" comes from), not of quantum computing.

kgwgk 9y ago
Always, except when you are confronted with a “problem having a structure that lets you set up a pattern of constructive and destructive interference, so that different contributions to each wrong answer cancel each other out while the different contributions to the right answer(s) reinforce.” In particular “factoring and other problems important for public-key cryptography,” which is the subject of the article.
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 ago
    My 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 ago
      I thought that something extra was part of “running a quantum computer”.

by rspeer 9y ago

kgwgk 9y ago

Always, except when you are confronted with a “problem having a structure that lets you set up a pattern of constructive and destructive interference, so that different contributions to each wrong answer cancel each other out while the different contributions to the right answer(s) reinforce.” In particular “factoring and other problems important for public-key cryptography,” which is the subject of the article.

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 ago
  My 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 ago
    I thought that something extra was part of “running a quantum computer”.