News for hackers. Stuff that matters.
Re:Performance of quantum computer no better than ordinary P... by michael_nielsen on Thursday June 19, 2014 @07:27PM (#7918834)
That's right. The search result, however, assumes the only way of accessing the database is through a black box oracle. That's why I wrote "non-oracle" in my previous comment. It's called an oracle because the internals of the black box are assumed to be unknown. That assumption is necessary in order to prove that classical computers need ~ N operations. If you know something about the internals of the oracle, then it may well be possible to exploit what you know to search faster.

The quantum search algorithm is very interesting. However, most people in the field would, I think, agree that a non-oracle separation between quantum and classical would be vastly more interesting. Oracle results feel a little too close to cheating.

There is, incidentally, a nice paper showing that for computing total Boolean functions the quantum oracle model can be no more than polynomially faster than a classical model. This means there can be no exponential speedup for such functions, which is a real pity.

http://arxiv.org/abs/quant-ph/9802049

There are no comments on this comment yet.