Abstract:
In this article, we propose a new strategy to exploit Grover’s algorithm for unstructured search problems. We first show that running Grover’s routine with a reduced number of iterations but allowing several trials presents a complexity advantage while keeping the same success probability. Then, by a theoretical analysis of the performance, we provide a generic procedure to parameterize the number of iterations k within one shot of Grover’s algorithm and the maximum number of trials T, given a targeted success p and the size of the database N. At the end, we highlight that this new approach permits to reduce the computational time by at least 10% for p≥0.999 independently of the size of the database.