Quantum Rough Counting and Its Application to Grover's Search Algorithm

Naphan Benchasattabuse
Prabhas Chongstitvatana
Chatchawit Aporntewan

submit to the 3rd International Conference on Computer and Communication Systems (ICCCS) Nagoya, Japan on April 27-30, 2018


We propose in this paper a rough counting algorithm and modified version of Groverís search algorithm. The proposed counting algorithm uses Deutsch-Jozsaís algorithm to roughly estimate the number of items satisfying some search conditions. The modified Grover's search is to combine the counting into one part of the algorithm using the counting result to determine the number of Groverís iterations taken to get such items. We provide an analysis of expected probability of the proposed algorithm taking into account the problem size, the number of satisfying items and the query complexity.