Counting by quantum eigenvalue estimation

For every "computation" there corresponds the physical task of manipulating a starting state into an output state with a desired property. As the classical theory of physics has been replaced by quantum physics, it is interesting to consider the capabilities of a computer that can exploit the distinctive quantum features of nature. The extra capabilities seem enormous. For example, with only an expected O(rootN) evaluations of a function f: { 0, 1,...,N - 1} --> {0,1}, we can find a solution to f(x) = 1 provided one exists. Another example is the ability to find efficiently the order of an element g in a group by using a quantum computer to estimate a random eigenvalue of the unitary operator that multiplies by g in the group. By using this eigenvalue estimation algorithm to estimate an eigenvalue of the unitary operator used in quantum searching we can approximately count the number of solutions to f(x) = 1. This paper describes this eigenvector approach to quantum counting and related algorithms. Crown Copyright (C) 2001 Published by Elsevier Science B.V. All rights reserved.