精确Grover量子搜索算法概述

Grover算法自提出以来就备受关注，因其对无序数据库搜索问题有相对于经典算法平方级别的加速。但是原始Grover算法通常无法百分之百得到目标元素，即使目标元素占比已知。为此，精确Grover量子搜索算法被提出，它们作为原始Grover算法的扩展，在保持平方加速的同时，能以100%的概率输出目标元素。该文较系统地梳理已有的3种精确Grover量子搜索算法，详细介绍算法的流程、参数设置、背后的几何直观，并针对目标元素占比已知及未知的情况，说明精确量子搜索的查询复杂性下界。

Overview of Exact Grover's Quantum Search Algorithms

Grover’s algorithm has attracted much attention ever since it was proposed, because it has a quadratic speedup over classical algorithm for searching unstructured database. However, the original Grover’s algorithm usually cannot obtain the target elements with certainty, even if the proportion of target elements is known. To this end, exact Grover’s quantum search algorithms were proposed as extensions of the original Grover’s algorithm, which can output the target element with certainty, while maintaining the quadratic speedup. This paper systematically sorts out the three existing exact Grover’s quantum search algorithms, introducing in detail the algorithm process, parameter settings, and the geometric intuition behind them. Moreover, the lower bound on the query complexity of these algorithms is shown, under both situations when the proportion of target elements is known or unknown.