  By using a new way to encode Boolean functions in a reversible gate, an
algorithm is developed in quantum computing over Z_2, symbolized QC/2, (as
opposed to QC over C) that needs only one function evaluation to solve the
Grover Database Search Problem of finding a designated record among 2^m records
for any m. In the usual Grover algorithm in quantum computing over C, one needs
essentially Sqrt(2^m) function evaluations as opposed to the average of (2^m)/2
functions evaluations needed in the classical algorithm. The one function
evaluation of the QC/2 algorithm (for any m) represents such a super speedup,
even over the Grover algorithm in QC/C, that one feels something has gone awry.
Indeed, our analysis of the transparent calculations of Boolean functions over
Z_2 shows that the classical algorithm is just repackaged in a rather obvious
way in the single function evaluation of the QC/2 algorithm--whereas the
calculations are hidden and non-transparent in the Grover QC/C algorithm using
C. The conclusion in both cases (which is rather obvious in the QC/2 case) is
that "counting function evaluations" is a false coin to measure speedup in the
comparison between quantum and classical computing.
