1252. Speeding up Grover's algorithm
Invited abstract in session WC-16: Quantum Computing for Optimization, stream Quantum OR .
Wednesday, 12:30-14:00Room: Esther Simpson 2.07
Authors (first author is the speaker)
| 1. | Stefan Creemers
|
| UCLouvain |
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, has made Grover's algorithms one of the most important algorithms in existence today. We investigate two strategies to speed up Grover’s algorithm: (1) reducing the number of iterations performed in each run and (2) partitioning the database. For each of these strategies, we not only execute Grover's algorithm in parallel, but also 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
- Algorithms
- Parallel Algorithms and Implementation
Status: accepted
Back to the list of papers