Speeding up Grover’s algorithm

Stefan Creemers
Additional contact information
Stefan Creemers: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3325, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: To find one of the M target entries in an unstructured database that has N entries, Grover's algorithm performs π/4(N/M)^(1/2) iterations. In each iteration, a function is called that evaluates whether an entry is a target entry. Compared to a classical procedure, that requires N/M evaluations, Grover's algorithm achieves a quadratic speedup. This quadratic speedup, combined with its general applicability as a search algorithm, have made Grover's algorithms one of the most important (quantum) algorithms available today. A study to improve its runtime is more than justified. For this purpose, we investigate two speedup strategies: (1) reducing the number of iterations that are performed in each run of Grover's algorithm and (2) partitioning the database. For each of these strategies, we not only execute Grover's algorithm in parallel, but also explore the possibility to execute Grover's algorithm in series on a single Quantum Processing Unit (QPU) as well as on multiple QPUs. For each combination of execution mode (serial, parallel, and serial/parallel) and speedup strategy, we show how to obtain optimal policies using closed-form expressions and a gradient-descent procedure. For a single QPU we obtain a speedup factor of 1.1382 when compared to a textbook implementation of Grover's algorithm. If multiple QPUs are at our disposal, we obtain a speedup factor of at most 1.1382 Q^(1/2), where Q denotes the number of QPUs. In addition, we show that the dominant policies that minimize the expected number of Grover iterations also minimize the expected number of iterations that are performed per qubit.

Keywords: Quantum; Computing; Algorithm; Grover; Serial; Parallel (search for similar items in EconPapers)
Pages: 15
Date: 2025-01-01
Note: In: European Journal of Operational Research, 2025, vol. 326 (1), p. 13-27
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3325

DOI: 10.1016/j.ejor.2025.02.034

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().