Counting by quantum eigenvalue estimation

AbstractFor 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(N) 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