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

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

Abstract

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.