3 ms·
>The answer in the comic is only: "Well, we only know how to do that for a few special problems." We know that for generic search problems (most everyday compu
by nabla9 10y ago
>The answer in the comic is only: "Well, we only know how to do that for a few special problems."
We know that for generic search problems (most everyday computation can be formulated as search problems) quantum computers can provide quadratic speedup. For some special problems it can provide exponential speedup.
- weinzierl 10y agoDepends upon against what you measure the speedup. If you mean against the best known classical algorithm then I agree. The point of the quantum computing skeptics seems to be that there exits no quantum algorithm where we can prove that any classical algorithm must be slower. At least that is my limited understanding.