News for hackers. Stuff that matters.

A comment on A Deepness In The Sky. Parent comment

Re:A Deepness In The Sky by endtime on Wednesday February 02, 2011 @05:48PM (#2172587)
I'm no expert on the field, but I believe the optimality of Grover's algorithm strongly suggests that the upper bound on the speedup from quantum computing is quadratic (and I apologize if I'm fudging something here). I have no idea about non-linear QM - really over my head - so I suppose I'll have to concede that point.

I agree with you that having conscious carbon but not conscious silicon is arbitrary and silly. Once we understand the brain better we'll surely be able to build one. Again, not something that should depend on location, nanomachines or not.

[ Parent | on HN ]
Re:A Deepness In The Sky by michael_nielsen on Wednesday February 02, 2011 @06:11PM (#2172686)
The optimality of Grover's algorithm doesn't in any way suggest that the upper bound on speedup is quadratic. That result only applies to one very particular class of problems: unstructured (oracle) search problems. There are other oracle problems for which the speedup is known to be exponential. For non-oracle problems the situation isn't yet clear, although many people believe the speedup will be exponential. That will be true if factoring isn't in BPP, for instance.
[ Parent | on HN ]