The Number of Elements in a Subset: A Grover-Kronecker Quantum Algorithm
Shahar Dolev, Itamar Pitowsky, Boaz Tamir · arXiv (Cornell University) · 2005
In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size N by using only O(N^{1/2}) queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either M or K, determine which is the case. We show how to solve this problem with a high probability of success by iterating Grover's basic step and subsequently measuring the register. Let m be the required number if iterations, we prove that under certain restrictions on the sizes of M and K estimations of the form m < O(N^{a}), for some (1/2)<a<1 obtain. We also indicate how these restrictions may be relaxed. In addition, we comment on situations where a large m may be needed for the job, and note the similarity between these cases and the problem of small divisors in classical mechanics.