Speeding up Grover’s algorithm

Stefan Creemers

European Journal of Operational Research, 2025, vol. 326, issue 1, 13-27

Abstract: To find one of the M target entries in an unstructured database that has N entries, Grover’s algorithm performs π4NM iterations. In each iteration, a function is called that evaluates whether an entry is a target entry. Compared to a classical procedure, that requires NM 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.1382Q, 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)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725001705
Full text for ScienceDirect subscribers only

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:eee:ejores:v:326:y:2025:i:1:p:13-27

DOI: 10.1016/j.ejor.2025.02.034

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().