Speeding up Grover’s algorithm
研究了两种加速格罗弗搜索算法的策略：减少迭代次数和划分数据库，并分析了在单量子处理单元和多量子处理单元上的串行、并行及串并行执行模式，给出了最优策略的闭式表达式和梯度下降方法。
To find one of the M target entries in an unstructured database that has N entries, Grover’s algorithm performs π 4 N M 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 , 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.