|
Author
|
Topic: A piece of NFL trivia
|
Erik
Member
Member # 160
|
posted 21. February 2004 18:30
Consider the problem of searching for a particular record in a disorganized database. If the database is organized according to some convenient rule it will be possible find the record very quickly, but we must on average look through half the records before we find the right one in a disorganized database. Such a search problem is equivalent to finding the maximum value of a needle-in-a-haystack function (i.e. a function that assigns the value 1 to one of the elements and 0 to all others). The class of all needle-in-a-haystack functions is closed under permutation, and therefore Igel & Toussaint's generalized NFL result applies. This means that all search strategies (that do not revisit records) all have the same probability of achieving a given level of performance.
In quantum computation, however, things happen partially and in parallel in a way that is difficult to describe. This makes the setting of the NFL theorem rather meaningless, because it is about how many points for which we need to evaluate the objective function (or about how many records we must check, in the specific example above) before finding what we're looking for. As far as I know, there is in general no way to count the number of function evaluations performed by a quantum algorithm. The NFL theorem therefore does not impose limits on quantum algorithms. Indeed, there is an algorithm for searching disorganized databases called Grover's algorithm which is much faster than any classical algorithm. For a database with N records, the classical algorithms require a time that is proportional to N in order to find the desired database record. Grover's algorithm requires a time that is proportional to the square root of N. The difference is substantial for a large N.
It must be emphasized that this nice property of quantum algorithms does nothing to defend evolutionary biology against the parts of Dembski's attack that are specifically aimed for evolutionary biology. But it does provide an example where a non-intelligent process not only circumvents the NFL theorems, but also achieves a performance that is superior to that of any intelligent agent. The limitations imposed by the NFL theorem apply in full force to intelligent agents and no intelligent agent can search a disorganized database of N records in O(N^(1/2)) steps.
Erik
[ 21. February 2004, 18:32: Message edited by: Erik ]
IP: Logged
|
|
William A. Dembski
Member
Member # 7
|
posted 23. February 2004 14:07
Let's cut through the hype. I'd be impressed if in optimizing a needle-in-the-haystack function the numbers came down by the log or by the loglog. But the square root is hardly impressive. Take an average protein of 300 amino acids. That's 20^300 possibilities. The square root of that is 20^150 (contrast the log, which would be more like 1000). Good luck searching a large space if all you can do is cut down the search by the square root.
Also, let's not forget that these quantum algorithms are being designed by programmers -- we have no evidence of randomly generated quantum algorithms giving rise to specified complexity.
IP: Logged
|
|
Erik
Member
Member # 160
|
posted 23. February 2004 16:22
Dr. Dembski, you missed the point. The point is not that the absolute performance of Grover's algorithms (or other QM algorithms) is good. Rather, the point is that the performance of Grover's algorithm relative to the performance of any intelligent agent is superior. An intelligent agent trying to optimize an unknown, randomly chosen needle-in-a-haystack function will require O(N) steps. Grover's algorithm will require O(N^(1/2)) steps. In the case of a search space consisting of all sequences of 300 amino acids, Grover's algorithm would be faster than any intelligent agent by a factor of 20^150 ~ 10^195 (after correcting for the fact that quantum systems operate on much faster time scales than intelligent agents, of course).
Grover's algorithm circumvents the limitations of the NFL theorem for optimization, intelligent agents are as bounded by those limitations as anything else. Grover's algorithm can find the optimum of a random needle-in-a-haystack function much faster than any intelligent agent can. These two facts seriously undermines the ID advocates' mystification of intelligent agents and the privileged place they give the notion of intelligence.
You also wrote that "let's not forget that these quantum algorithms are being designed by programmers". The are numerous quantum algorithms running in the universe. These quantum algorithm typically compute things that are of little direct interest to engineers on Earth and the results of the computations are often not displayed in a manner suitable for humans. Except for an infinitesimally small fraction, all quantum algorithms were not designed by physicists and computer scientists. What typically does require a human programmer is the task of making a quantum algorithm that solves a problem of direct interest to humans and displays the result of the computation in a way that is accessable by humans.
Erik
[ 23. February 2004, 16:23: Message edited by: Erik ]
IP: Logged
|
|
|
Printer-friendly view of this topic