Tuesday, June 21, 2005
New Paper With Huge Claims (Debunked?)
On 16 June 2005, Andreas de Vries released the paper: Fast quantum search algorithms by qubit comparisons exploiting global phase interference. The paper requires only basic understanding of quantum algorithms to follow. Assuming there's no fatal flaw somewhere, the results will have huge ramifications for quantum computation: The algorithm is able to find an item in an unsorted databse in O(log n) time, and implies that NP is in BQP. In other words, NP complete problems will be solvable in polynomial time on a quantum computer.
[Update 2005-06-23] According to the Quantum Pontiff himself, this paper is merely the latest in a long tradition to erroneously make these same grandiose claims. His post points out where he thinks the fatal flaw is, but adds more here.