Deterministic Application of Grover’s Quantum Search Algorithm

Grover’s quantum search algorithm finds one of t solutions in N candidates by using (π/4)$$ \sqrt {{N \mathord{\left/ {\vphantom {N t}} \right. \kern-\nulldelimiterspace} t}} $$basic steps. It is, however, necessary to know the number t of solutions in advance for using the Grover’s algorithm directly. On the other hand, Boyer etal proposed a randomized application of Grover’s algorithm, which runs, on average, in Oi($$ \sqrt {{N \mathord{\left/ {\vphantom {N t}} \right. \kern-\nulldelimiterspace} t}} $$) basic steps (more precisely, (9/4)$$ \sqrt {{N \mathord{\left/ {\vphantom {N t}} \right. \kern-\nulldelimiterspace} t}} $$ steps) without knowing t in advance. Here we show a simple (almost trivial) deterministic application of Grover’s algorithm also works and finds a solution in O$$ \sqrt {{N \mathord{\left/ {\vphantom {N t}} \right. \kern-\nulldelimiterspace} t}} $$) basic steps (more precisely, (8π/3)$$ \sqrt {{N \mathord{\left/ {\vphantom {N t}} \right. \kern-\nulldelimiterspace} t}} $$ steps) on average.