无序数据库搜索问题可以抽象地描述如下，在大小为$ N={2}^{n} $的无序数据库中，有$ M $个元素是符合要求的，这些目标元素通过一个函数$ f:\{\mathrm{0,1},\cdots , $$ N-1\}\to \left\{\mathrm{0,1}\right\} $来标识：若编号为$ x $的元素为目标元素，那么$ f\left(x\right)=1 $；否则，$ f\left(x\right)=0 $。假设有一个可以识别搜索问题目标元素的黑盒：要判断编号为$ x $的元素是否为目标元素，只需要将编号$ x $输入黑盒，它就会输出$ f\left(x\right) $的值。现在希望以尽可能少的黑盒调用次数(称之为查询复杂性)，找出一个目标元素。

在量子计算中，实现函数$ f\left(x\right) $的黑盒的作用效果是一个酉操作$ {O}_{f} $，其在计算基态上的作用效果为：

式中，$ \left| x \right\rangle $是存储元素编号的量子寄存器(即$ n $个qubit)；$ \left| q \right\rangle $是单qubit辅助寄存器，用于储存黑盒返回的结果，运算$ \oplus $为异或。如果将辅助寄存器$ \left| q \right\rangle $的初始态设置为$ \left| - \right\rangle : = (\left| 0 \right\rangle - \left| 1 \right\rangle )/\sqrt 2 $，那么黑盒将不改变辅助寄存器的状态$ \left| - \right\rangle $，故可以忽略它，因此可以将黑盒的作用效果表示为：

原始Grover算法的具体流程为，首先利用$ n $个qubit上的Hadamard变换制备初始均匀叠加态$ \left| \psi \right\rangle = {H^{ \otimes n}}\left| 0 \right\rangle $，然后迭代$ O(\sqrt{N/M}) $次Grover算子$ G $：

最后进行计算基态测量，将以很大概率得到某一目标元素的编号。即Grover算法的查询复杂度为$ O(\sqrt{N/M}) $。相比之下，在经典计算机上则期望需要$ O(N/M) $次检索才能以高概率得到目标元素，即其查询复杂度为$ O(N/M) $。因此Grover算法相对于经典算法有平方级别的加速。

Grover算子$ G $的作用效果有着很强的几何直观，令

分别为非目标元素和目标元素的均匀叠加态，那么在单位正交向量$ \left|A\right\rangle $和$ \left|B\right\rangle $张成的二维子空间中，$ G $的作用相当于先以$ \left|A\right\rangle $为法线进行反射，再以$ \left|\psi \right\rangle $为法线进行反射，总的效果是由$ \left|A\right\rangle $朝着$ \left|B\right\rangle $旋转了$ 2\theta $角度，这里$ {\rm{sin}}\left(\theta \right)=\sqrt{M/N} $为初始态$ \left|\psi \right\rangle $在$ \left|B\right\rangle $上的投影。

这么看来，Grover算法总的流程，在几何直观上可以理解为，从与$ \left|A\right\rangle $偏离了$ \theta $角度的初始状态向量$ \left|\psi \right\rangle $出发，通过作用$ k $次Grover算子$ G $，把它朝着$ \left|B\right\rangle $旋转了$ k\cdot 2\theta $角度，最终得到状态向量

如果迭代次数$ k $选得恰当，使得最终态尽可能地接近$ \left|B\right\rangle $，即使得$ \left(2k+1\right)\theta $尽可能接近${\text π} /2$，那么在计算基上测量将以高概率($ {\rm{sin}}^{2}\left(\left(2k+1\right)\theta \right) $)得到问题的一个目标元素。特别地，当$ M/N=1/4 $，即目标元素的占比为$ 1/4 $时，$ \theta $为$ {\text π} /6 $，那么取$ k $为$ 1 $，$ \left(2k+1\right)\theta $等于$ {\text π} /2 $，最终态就是$ \left|B\right\rangle $，进行计算基态测量将以$ 100\% $的概率得到一个目标元素。

但是通常情况下，目标元素的占比$ M/N $不会使得

恰为整数，而迭代次数$ k $必须是整数，因此原始Grover算法无法做到以$ 100\% $的概率精确地得到一个目标元素。

为了弥补上述缺陷，即在不牺牲平方加速的同时，使得到的最终状态向量就是$\left| B \right\rangle $(可以相差一个整体相位，因为这并不会影响测量结果)，有3种方法^[6,10-11]在2000年左右被提出，它们的思路虽然不一样，但都基于对原始Grover算子进行扩展：

再通过设置适当的角度$ \phi ,\varphi $和迭代次数$ k $，使得多次迭代扩展Grover算子$ G\left(\phi ,\varphi \right) $后得到的最终态就是目标元素的均匀叠加态$\left| B \right\rangle $。本文把3种方法的思路总结为：大步小步、共轭旋转和三维旋转，由于推导过程较为繁琐，下面在分别阐述3种方法时某些步骤有所省略，感兴趣的读者可以参考原始文献。

在$ G\left(\phi ,\varphi \right) $的定义式中，算子$ \mathcal{A} $满足$\mathcal{A}\left|0\right\rangle = $$ 1/\sqrt{N}\displaystyle\sum\limits _{x=0}^{N-1}\left|x\right\rangle$，用于得到均匀叠加态，如在原始Grover算法中$ \mathcal{A} $就是Hadamard变换$ {H}^{\otimes n} $；${S}_{0}\left(\phi \right)\left|x\right\rangle = $$ {{\rm{e}}}^{{\rm{i}}\phi }\left|x\right\rangle$当且仅当$\left|x\right\rangle =\left|0\right\rangle$，用于旋转状态$ \left|0\right\rangle $的相位；${S}_{f}\left(\varphi \right)\left|x\right\rangle ={{\rm{e}}}^{{\rm{i}}\varphi }\left|x\right\rangle$当且仅当$ f(x)=1 $，用于旋转目标元素的相位。特别地，当$\varphi =\phi ={\text π}$时，$ G\left(\phi ,\varphi \right) $恢复到原始Grover算子$ G=G\left({\text π} ,{\text π} \right) $。

这一方法^[6]的思路比较直接。由于原始Grover算法中的误差来自需要旋转的角度($ {\text π} /2-\theta $)不是单次旋转角度($ 2\theta $)的整数倍，那么不妨在前$ \left\lfloor {k}_{{\rm{opt}}}\right\rfloor $步仍作用原始Grover算子每次旋转$ 2\theta $角度，最后一步减缓速度作用$ G\left(\phi ,\varphi \right) $，旋转剩余的角度。因此总流程可以形象地描述为：从$ \left|\psi \right\rangle $出发先走$ \left\lfloor {k}_{{\rm{opt}}}\right\rfloor $大步，再走一小步到达$ \left|B\right\rangle $。

具体来说，首先作用$ \left\lfloor{k}_{{\rm{opt}}}\right\rfloor $次原始Grover算子于初始状态向量$ \left|\psi \right\rangle =\mathcal{A}\left| 0 \right\rangle $，得到状态向量

其次考虑$ G\left(\phi ,\varphi \right) $在正交基$ \left| A \right\rangle $和$ \left| B \right\rangle $下的矩阵，可以得到：

再令$ G\left(\phi ,\varphi \right)\left|\tilde{\psi }\right\rangle $的$ \left|A\right\rangle $分量为$ 0 $，便能解出参数$ \phi $和$ \varphi $，使得最终态为目标元素的均匀叠加态$ \left|B\right\rangle $。

这一方法^[10]主要基于如下观察：通过选取适当的角度$ \phi $和$ \varphi $，可以使得$ G\left(\phi ,\varphi \right) $在共轭一个条件相位旋转的意义下，实现任意角度$ \beta $的二维旋转。具体来说，当参数$ \phi $和$ \varphi $满足：

时，$ G\left(\phi ,\varphi \right) $的对角元相等，且可以分解为：

式中，参数$ u=\left( {\text π} -\varphi \right)/2 $；$ v $作为整体相位无需考虑。因此，如果在上式两边同时进行$ k=\left\lceil{k}_{{\rm{opt}}}\right\rceil $次幂，并令角度$ \beta $满足$ k\beta = {\text π} /2-\theta $，那么移项可以得到：

把它作用到初态$ \left|\psi \right\rangle ={{\rm{cos}}}\left(\theta \right)\left|A\right\rangle +{{\rm{sin}}}\left(\theta \right)\left|B\right\rangle $上，就能得到目标元素的均匀叠加态$ \left|B\right\rangle $。注意到$ {S}_{f}\left(\varphi \right) $在正交基$ \left|A\right\rangle $和$ \left|B\right\rangle $下的矩阵表示就是$\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}({1,{\rm{e}}}^{{\rm{i}}\varphi })$，因此总的算法流程可以表示为$ {G}^{k}\left({\phi },{\varphi }\right){S}_{f}\left(u\right)\left|\psi \right\rangle =\left|B\right\rangle $。也就是说，从初始状态$ \left|\psi \right\rangle $出发，先作用条件相位旋转$ {S}_{f}\left(u\right) $把目标元素的相位旋转角度$ u $，再作用$ k $次扩展Grover算子$ G\left(\phi ,\varphi \right) $，便得到$ \left|B\right\rangle $。

这一方法^[11]的思路为：把$ G\left(\phi ,\phi \right) $在正交基$ \left| A \right\rangle $和$ \left| B \right\rangle $下的二维酉矩阵对应到相应Bloch球中的三维旋转，再通过选取适当的角度$ \phi $和旋转次数$ k $，使得$ {G}^{k}\left(\phi ,\phi \right)\left|\psi \right\rangle $在该Bloch球面上与$ \left|B\right\rangle $重合。

具体来说，由于任意二维酉矩阵都可以写成下式右边的形式，因此令

再通过把$ -G\left(\phi ,\phi \right) $展开成单位矩阵和泡利矩阵${\boldsymbol{I}},{\boldsymbol{X}},{\boldsymbol{Y}},{\boldsymbol{Z}}$的线性组合，对比$ I $前的系数，得到旋转角度$ {\alpha }=4\beta ,其中\beta 满足{{\rm{sin}}}\left(\beta \right)={{\rm{sin}}}\left(\phi /2\right){{\rm{sin}}}\left(\theta \right) $。对比${\boldsymbol{X}},{\boldsymbol{Y}}, $$ {\boldsymbol{Z}}$前的系数，得到转轴

即在$ \{\left|A\right\rangle ,\left|B\right\rangle \} $的Bloch球中，$ G\left(\phi ,\phi \right) $相当于以${{\boldsymbol{n}}}$为转轴、角度为$ {\alpha } $的三维旋转^[12]。

由于初态$ \left|\psi \right\rangle $在Bloch球中对应的向量为${{\boldsymbol{s}}}:=\left[\mathrm{sin}\left(2\theta \right),0,-\mathrm{cos}\left(2\theta \right)\right]$，而算法最终欲得的$ \left|B\right\rangle $对应的向量为${{\boldsymbol{t}}}:=\left[\mathrm{0,0},1\right]$，故$\left\langle{{\boldsymbol{n}}}|{{\boldsymbol{s}}}\right\rangle=\left\langle{{\boldsymbol{n}}}|{{\boldsymbol{t}}}\right\rangle$。这说明${{\boldsymbol{s}}}$和${{\boldsymbol{t}}}$在Bloch球面以${{\boldsymbol{n}}}$为轴的同一个的圆上，所以确实可以通过绕固定轴${{\boldsymbol{n}}}$进行多次旋转，把${{\boldsymbol{s}}}$转到${{\boldsymbol{t}}}$。为了确定参数$ \phi $和旋转次数$ k $，记${{\boldsymbol{r}}}$为${{\boldsymbol{s}}}$和${{\boldsymbol{t}}}$在${{\boldsymbol{n}}}$上的投影，如图1所示，解析几何计算表明${{\boldsymbol{s}}}-{{\boldsymbol{r}}}$和${{\boldsymbol{t}}}-{{\boldsymbol{r}}}$之间的角度为$ \omega = {\text π} -2\beta $。根据之前的推导，每作用一次$ G\left(\phi ,\phi \right) $相当于绕转轴${{\boldsymbol{n}}}$旋转$ \mathrm{\alpha }=4\beta $，而$ \omega $是所希望的总旋转角度，因此令$ \omega =k\mathrm{\alpha } $可以求出$ \phi $与$ k $应该满足关系式：

容易看出当$ k > {k}_{{\rm{opt}}} $时$ \phi $有实数解，从而最小可以取$ k=\left\lceil{k}_{{\rm{opt}}}\right\rceil $，并得到相应的$ \phi $值。

图  1  在$ \{\left|A\right\rangle,\left|B\right\rangle\} $的Bloch球中，$ G\left(\phi ,\phi \right) $的多次作用相当于把初态${{\boldsymbol{s}}}$绕转轴${{\boldsymbol{n}}}$旋转到目标元素的均匀叠加态${{\boldsymbol{t}}}$

最后，本文把上述3种精确Grover量子搜索算法总结如表1所示。值得注意的是，3种算法中参数的设置都依赖于目标元素的占比$ M/N $。另外，(扩展)Grover算子的迭代次数都是$\left\lceil{k}_{{\rm{opt}}}\right\rceil=O(\sqrt{N/M})$，保持了原始Grover算法的平方加速。

实际操作中，还需考虑扩展Grover算子$ G\left(\phi ,\varphi \right) $的量子电路实现。由于

容易验证，图2和图3分别展示了$ {S}_{f}\left(\varphi \right) $和$ {S}_{\psi }\left(\phi \right) $的电路实现，其中最后一行为辅助qubit。注意到$ {S}_{f}\left(\varphi \right) $需要调用两次黑盒$ {O}_{f} $，因此表1中后两种方法的黑盒调用次数是原始Grover算法的两倍，不过这并不影响平方加速的数量级。

图  2  $ {S}_{f}\left(\varphi \right) $的电路实现，其中${{O}}_{f}\left|x\right\rangle\left|b\right\rangle=\left|x\right\rangle\left|b \oplus f\left(x\right)\right\rangle$

图  3  $ {S}_{\psi }\left(\phi \right) $的电路实现

上面3种方法说明：在目标元素的占比已知的情况下，可以设计量子搜索算法在保持平方加速的同时，精确地找到目标元素。由此自然引出的一个问题是：如果目标元素的占比未知，还能设计出量子搜索算法既百分之百找到目标元素又保持平方加速吗？答案是否定的。事实上，假设存在这样的精确量子搜索算法，它在调用T次黑盒：$ {\mathrm{S}}_{x}\left|i\right\rangle= $$ {\left(-1\right)}^{{x}_{i}}\left|i\right\rangle $后(这里把搜索问题函数$f:\left\{0,1,\cdots ,N-1\right\}\to $$ \left\{\mathrm{0,1}\right\}$视为长为$ N $的比特串$ {x}_{0}{x}_{1}\cdots {x}_{N-1} $，以便于后面的讨论)，精确地输出目标元素$ i $(如果无解，则输出不合法的指标，比如$ \left|N\right\rangle $)，那么该算法稍加修改就能以相同的黑盒调用次数精确计算${\rm{O}}{{\rm{R}}}_{N}= {x}_{0}\vee {x}_{1}\vee \cdots $$ \vee {x}_{N-1}$(如在算法的最后进行二分投影测量$\left\{{{P}}_{0}=\left|N\right\rangle \left\langle N \right|, $$ {{P}}_{1}={I}-{{P}}_{0}\right\}$)。但是，下面将用多项式方法^[13]证明：任意精确计算$ {\rm{O}}{{\rm{R}}}_{N} $的量子算法都至少要调用$ {N}/2 $次黑盒，因此，在目标元素占比未知的情况下，任意精确量子搜索算法都必定丢失平方加速！

对于任意精确计算$ {\rm{O}}{{\rm{R}}}_{N} $的量子算法，假设它进行了T次黑盒调用。首先把黑盒写成如下形式：

可以看出，如果把基态前的振幅表示成关于变量${x}_{0},{x}_{1},\cdots ,{x}_{N-1}$的多元多项式，那么每次黑盒调用只会使得任意基态前的振幅多项式的次数增加至多1。又注意到任意两次黑盒调用之间的酉变换作为线性变换，不会增加多项式的次数，因此最终测得$ {{P}}_{1} $的概率(振幅的模平方和)可以表示成次数$\leqslant 2{T}$的多项式$p\left({x}_{0},{x}_{1},\cdots ,{x}_{N-1}\right)$。由于算法以概率1计算$ {\rm{O}}{{\rm{R}}}_{N} $，因此$p(x)={\rm{O}}{{\rm{R}}}_{N}(x),\mathrm{ }\forall {x}=\left({x}_{0},{x}_{1},\cdots ,{x}_{N-1}\right)\in {\left\{\mathrm{0,1}\right\}}^{N}$。考虑对$ p $的$ N $个变量${x}_{0},{x}_{1},\cdots ,{x}_{N-1}$的所有排列进行平均所得的对称多项式

那么可以证明，存在次数不超过$ \mathrm{d}\mathrm{e}\mathrm{g}\left(q\right) $的单变量多项式$ r\left({z}\right) $，使得$ r\left(\left|x\right|\right)=q\left({x}\right) $。而且不难看出$r\left(0\right)= 0, $$ \mathrm{且}\mathrm{对}\mathrm{任}\mathrm{意}{t}\in \left\{1,2,\cdots ,N\right\}\mathrm{都}\mathrm{有}r\left(\mathrm{t}\right)=1$，所以$\mathrm{d}\mathrm{e}\mathrm{g}\left(r\left({z}\right)\right) \geqslant $$ N$(因为$ r\left({z}\right)-1 $是有$ N $个零点的非零多项式)。从而$ {T}\geqslant \mathrm{N}/2 $。

在目标元素的占比已知的情况下，利用文献[14]的quantum angle方法，并把它直接地扩展到多个目标元素的情形(即文献[15]文末提及的选取$ \left\lfloor N/M \right\rfloor $个“不相交”数据库的思路)，可以证得精确量子搜索的查询下界为

这说明前面3种精确Grover量子搜索算法的查询复杂性都达到了最优。

事实上，对于任意精确量子搜索算法，设其进行T次黑盒调用后的状态为：

那么令$\displaystyle\prod\limits_{x}=\displaystyle\sum\limits _{j:{x}_{j}=1} |j\rangle \langle j|$，则该算法必须保证对于任意数据库$ x={x}_{1}{x}_{2}\cdots {x}_{N} $，都有

令 $\left|{{\varPsi }}^{{{T}}}\right.\rangle ={U}_{T}{U}_{T-1}\cdots {U}_{1}{U}_{0}\left|0\right.\rangle$，并记$K:=\left\lfloor N/M \right\rfloor$，那么得到查询下界$ {k}_{{\rm{low}}} $的思路在于给出如下表达式(即quantum angle的均值)：

的上下界，其中

而$ {S} $则表示$\left[{N}\right]$:=$\left\{\mathrm{1,2},\cdots ,{N}\right\}$的$ K $个不相交子集的集合(把数据库$ {y} $对应到$ \left[{N}\right] $的子集$ \left\{i:{y}_{i}=1\right\} $)。具体的上下界如下式所示：

由此便可以得出T的下界：

式(26)的详细证明和文献[14]中的Lemma 5(上界)和Lemma 7(下界)几乎一模一样，只需要把求和下标由$ \mathrm{y}=1 $至$ {N} $改为$ y\in S $，并把$ N $改为$ K=\left\lfloor N/M \right\rfloor $即可，这里不再赘述，只简要说明背后的直观想法：表达式(24)下界的直观是，经过T次查询，算法最终能以很大概率区分平凡黑盒$ I $和数据库$ x $的黑盒的$ {S}_{x} $，即${{\varPsi }}^{{{T}}}$和${{\varPsi }}_{x}^{{{T}}}$几乎垂直。而表达式(24)上界的直观是，每次查询最多只能使两者之间的角度增加很小的值。

本文梳理了3种精确Grover量子搜索算法，给出了算法流程、参数设置以及背后的几何直观，并指出它们都依赖于目标元素的占比，由此为出发点，说明了算法的最优性：对于目标元素占比已知的情况，3种精确Grover量子搜索算法已经达到最优；而对于目标元素占比未知的情形，精确量子搜索算法相比经典算法没有加速。因此本文对精确量子搜索算法给出了较为完整的概述。