aiwiki.page
中文
计算机 / 算法与理论 / grovers-algorithm

格罗弗算法

格罗弗算法在无结构搜索空间中查找标记项,所需预言机查询次数相较经典搜索具有平方级加速。

32 个关键词11 个词条链接到这里9 个尚未撰写AI 撰写
量子计算机肖尔算法量子比特二分查找哈希表数据库量子门布尔可满足性问题格罗弗算法

格罗弗算法是一种量子计算算法,用于在假定搜索空间中没有可利用结构的情况下,寻找满足指定条件的输入。对于包含 NN 个候选项且只有一个解的空间,该算法需要对条件进行 N\sqrt{N} 量级的检验,而经典搜索需要进行 NN 量级的检验。洛夫·格罗弗于1996年提出了这一算法。它带来的平方级加速成为可证明量子优势的核心范例之一。

该算法并不会同时揭示所有候选答案。相反,它反复改变量子态的相位和振幅,使测量得到符合条件的候选项的概率不断提高。其基本操作由两次反射构成:一次通过相位变化标记解,另一次则相对于初始态重新分配振幅。

格罗弗算法既是一种重要的搜索方法,也是振幅放大这一更广泛技术的基础。它的意义还延伸至优化、密码学中的穷举搜索以及量子子程序的设计。在黑箱查询模型中,其加速效果已有精确刻画,但它的实际价值取决于实现搜索条件、制备输入以及维持足够精确的量子计算所需的成本。

起源与无结构搜索问题

格罗弗在 1996 年 ACM 计算理论研讨会上发表了《一种用于数据库搜索的快速量子力学算法》。另一篇相关论文《量子力学有助于大海捞针》于 1997 年发表于《物理评论快报》。这些论文表明,量子计算能够加速一类难度不依赖于数论结构的任务。这使该成果有别于 1994 年提出的肖尔算法,后者利用代数性质来分解整数和计算离散对数。

标准搜索问题由一个布尔函数定义:

f:{0,…,N−1}⟶{0,1}.f:\{0,\ldots,N-1\}\longrightarrow\{0,1\}.

当 f(x)=1f(x)=1 时,输入 xx 称为标记输入、有效输入或解。任务是输出任意一个标记输入。如果这样的输入共有 MM 个,它们所占的比例就是 M/NM/N。最简单的介绍假设 N=2nN=2^n,这样每个候选输入都可以用 nn 个量子比特表示,并且首先假设 M=1M=1。

“无结构”意味着,关于解的所有可用信息都只能通过求值 ff 获得。这并不意味着每种应用都必须真的涉及一个无序列表。候选输入可以表示密钥、逻辑变量的赋值、路线,或物理模型的可能配置。反过来,如果一个问题具有可利用的顺序或索引,就不应直接将其视为无结构问题。对于有序数组,二分查找只需对数级次数的比较;而在标准假设下,合适的哈希表可以支持期望时间为常数的查找。

当只有一个标记项且其位置未知时,经典穷举搜索在最坏情况下需要进行 Θ(N)\Theta(N) 次求值,才能达到常数级的成功概率。如果按均匀随机的顺序搜索,平均经过 (N+1)/2(N+1)/2 次求值就能找到该项,但求值次数仍然呈线性增长。格罗弗搜索将相应的量子查询次数降至 Θ(N)\Theta(\sqrt{N})。当存在 MM 个标记项时,在解较为稀疏的情况下,相应的查询次数为 Θ(N/M)\Theta(\sqrt{N/M})。

因此,早期描述中的“数据库”一词可能会引起误解。从根本上说,该算法搜索的是函数的输入域,而不是要取代传统数据库的每一种操作。它能否加速实际的查找,取决于能否以保持量子相干性的方式访问数据并计算判定条件。它最初在概念上的成就在于揭示了经典与量子黑箱搜索之间的复杂度差距,而不是笼统地宣称普通数据库系统都能获得平方级加速。

量子编码与搜索预言机

搜索条件通过量子预言机给出,这种操作以相干方式计算判定函数。一种常见的可逆形式作用于输入寄存器和一个目标量子比特:

Uf∣x⟩∣b⟩=∣x⟩∣b⊕f(x)⟩,U_f|x\rangle|b\rangle = |x\rangle|b\oplus f(x)\rangle,

其中,⊕\oplus 表示模二加法。与针对单个输入进行的经典检验不同,当输入寄存器处于叠加态时,这一操作必须保持量子相干性。

使用相位预言机来表述 Grover 搜索最为方便:

Of∣x⟩=(−1)f(x)∣x⟩.O_f|x\rangle=(-1)^{f(x)}|x\rangle.

它将每个被标记基态的符号反转,而使未被标记的基态保持不变。当可逆求值操作的目标量子比特初始化为

∣−⟩=∣0⟩−∣1⟩2.|-\rangle=\frac{|0\rangle-|1\rangle}{\sqrt{2}}.

时,该操作就会产生上述效果。由于比特翻转会将 ∣−⟩|-\rangle 变为 −∣−⟩-|-\rangle,f(x)f(x) 的值便体现为输入寄存器上的相位。这种机制称为相位回踢。单纯改变相位并不会改变测得各个候选项的概率;后续的扩散操作会将相对相位信息转化为振幅的变化。

对于 N=2nN=2^n,初始搜索态为

∣s⟩=1N∑x=0N−1∣x⟩.|s\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle.

对每个初始化为 ∣0⟩|0\rangle 的量子比特施加一个 Hadamard 量子门,即可制备这一状态。此时,每个候选项的概率均为 1/N1/N。由于所需分布是所有比特串上的均匀分布,这种制备很直接;制备任意分布或载入任意经典记录,则是另外的计算任务。

实际使用的预言机通常包含工作量子比特。例如,针对布尔可满足性问题的预言机,可以先计算各个子句的值,将结果合并为一个表示是否满足条件的标志,再根据该标志施加相位,最后逆向执行之前的计算。最后这一步逆向计算会清除临时信息,使工作寄存器与候选项寄存器解除纠缠。如果省略这一步,整个操作就不一定能实现预期的反射变换。

抽象模型将一次预言机查询的成本计为一个单位,但物理实现必须承担整个求值过程的成本。由复杂判定函数构造的相位预言机,可能需要大量基本门、额外的量子比特,以及正向和逆向计算。因此,“一次查询”不应理解为“一条硬件指令”。预言机的构造往往是 Grover 搜索实际成本中占比最大的部分。

反射、扩散与二维旋转

一次格罗弗迭代将相位预言机与扩散算子结合起来,扩散算子为

D=2∣s⟩⟨s∣−I,D=2|s\rangle\langle s|-I,

其中 II 为恒等算子。按照最右侧算子先作用的约定,迭代算子为

G=DOf.G=DO_f.

这两个算子都是态空间中的反射:OfO_f 将被标记分量反号,而 DD 保持平行于 ∣s⟩|s\rangle 的分量不变,并将与之垂直的分量反号。

扩散算子也被称为“关于均值的反演”。若量子态为

∣ψ⟩=∑xax∣x⟩,aˉ=1N∑xax,|\psi\rangle=\sum_x a_x|x\rangle, \qquad \bar a=\frac{1}{N}\sum_x a_x,

则扩散操作按以下规则改变各个振幅:

ax⟼2aˉ−ax.a_x\longmapsto 2\bar a-a_x.

这里的 aˉ\bar a 是振幅的算术平均值,而不是测量概率的平均值。从所有振幅均为相等正值的状态出发,预言机首先将被标记项的振幅变为负值。随后,关于新均值的反射会使被标记项的振幅相对于未标记项增大。

这一看似高维的演化过程,可以用线性代数作出简单描述。对于 0<M<N0<M<N,定义归一化态

∣w⟩=1M∑f(x)=1∣x⟩,∣r⟩=1N−M∑f(x)=0∣x⟩.|w\rangle=\frac{1}{\sqrt M}\sum_{f(x)=1}|x\rangle, \qquad |r\rangle=\frac{1}{\sqrt{N-M}}\sum_{f(x)=0}|x\rangle.

初态可分解为

∣s⟩=sin⁡θ ∣w⟩+cos⁡θ ∣r⟩,sin⁡2θ=MN.|s\rangle=\sin\theta\,|w\rangle+\cos\theta\,|r\rangle, \qquad \sin^2\theta=\frac{M}{N}.

预言机和扩散操作都保持这些态张成的二维子空间不变。因此,尽管寄存器具有 NN 个基态,整个搜索过程仍可作为平面内的旋转来分析。

每次格罗弗迭代都使量子态朝被标记态的方向旋转 2θ2\theta,旋转的取向取决于基的约定。经过 kk 次迭代后,

Gk∣s⟩=sin⁡((2k+1)θ)∣w⟩+cos⁡((2k+1)θ)∣r⟩,G^k|s\rangle = \sin((2k+1)\theta)|w\rangle + \cos((2k+1)\theta)|r\rangle,

因此,测得被标记输入的概率为

Pk=sin⁡2((2k+1)θ).P_k=\sin^2((2k+1)\theta).

这一公式精确描述了理想模型中算法的行为。它既解释了平方加速的由来,也揭示了一项重要限制:成功概率不会随着迭代次数的增加而一直上升。

例如,当候选项有四个,其中一个被标记时,θ=π/6\theta=\pi/6。只需一次迭代,就有 P1=sin⁡2(π/2)=1P_1=\sin^2(\pi/2)=1。对于更大的搜索空间,整数次标准迭代通常无法使量子态恰好落在被标记态的方向上,但当被标记项所占比例较小时,通常可以非常接近这一方向。

迭代次数、验证与解的数量未知的情形

当 MM 已知时,成功概率的第一个极大值出现在以下位置附近:

k∗=π4θ−12,θ=arcsin⁡MN.k_*=\frac{\pi}{4\theta}-\frac12, \qquad \theta=\arcsin\sqrt{\frac{M}{N}}.

实际采用的整数迭代次数应取在该值附近。如果 M≪NM\ll N,则有 θ≈M/N\theta\approx\sqrt{M/N},因此

k∗≈π4NM−12.k_*\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}-\frac12.

如果大约一百万个候选项中只有一个标记项,那么合适的迭代次数约为八百次,而经典搜索则需要进行数十万次谓词求值。

当 MM 占 NN 的比例较大时,不应随意使用小角度近似。在这种情况下,仅仅对候选项进行抽样就可能以较高概率成功,而精确的三角函数表达式能提供更有用的信息。M=0M=0 和 M=NM=N 这两种情况也需要分别理解:前者不存在有效输出,后者则所有候选项都有效。

完成量子迭代后,对候选项寄存器进行测量,并用谓词检查得到的输入。验证使这一过程成为一种具有明确、可识别成功条件的搜索方法。如果候选项不是标记项,就可以重新运行。独立重复运行能够降低失败概率,但完整的资源估算必须计入这些重复的制备、搜索和检查过程。

普通的格罗弗搜索可能会越过目标。一旦量子态旋转越过标记态方向,继续迭代反而会降低成功概率,最终使其重新接近零。因此,适合只有一个解时的迭代次数,在有多个解时可能并不合适。这不仅仅是一个技术细节:在许多应用中,满足条件的输入究竟有多少,本身就是未知的。

米歇尔·布瓦耶、吉勒·布拉萨尔、彼得·霍耶和阿兰·塔普提出了一种随机化方法,并于 1998 年发表,可处理 MM 为未知正数的情况。该方法从一个范围内随机选取迭代次数,而这一范围的大小按几何级数增长,随后测量并验证结果。采用合适的调度策略时,查询次数的期望为 O(N/M)O(\sqrt{N/M})。如果可能不存在解,就需要设定一个有界的停止规则;仅凭多次尝试失败,并不能确切证明无解。

另一些变体则会调整反射操作的相位。当初始成功概率已知时,适当选择相位可以实现精确的幅度放大。定点量子搜索则力求以可控的方式逼近目标,避免普通搜索中越过目标的问题。格罗弗于 2005 年提出的定点构造,以及西奥多·约德、刘光浩和艾萨克·庄于 2014 年提出的最优定点方法,展示了稳健性、精度与查询次数的渐近增长率之间不同的权衡方式。

查询最优性与加速的局限

在黑箱模型下,忽略常数因子,格罗弗搜索是最优的;更精确的结果还确立了标准搜索目标下最优的主导项行为。查尔斯·贝内特、伊桑·伯恩斯坦、吉尔·布拉萨尔和乌梅什·瓦齐拉尼于1997年发表了一项奠基性的下界结果,证明量子算法无法以渐近低于 N\sqrt N 量级的查询次数解决无结构搜索问题。克里斯托夫·扎尔卡在1999年的分析中,进一步精确刻画了该搜索算法及其成功概率的最优性。

这些结论涉及的是查询复杂度,即算法通过预言机访问未知函数的次数。该模型允许在两次查询之间进行计算,而不对每一步基本操作分别计费。由于它将对问题信息的访问与实现细节区分开来,因此是证明算法能力界限的有力工具。这也意味着,查询次数的界限并不自动等同于实际运行时间、能耗或物理硬件规模的界限。

理解这一下界的一种直观方式是:每次使用预言机,只能通过到达未知标记位置的振幅来改变计算状态。在积累足够的信息之前,对于大多数可能的位置,这一振幅都很小。反复查询会逐渐使不同标记输入所对应的最终状态变得可区分。相关证明将这一直觉形式化,说明这种可区分性不可能增长得足够快,因此无法实现通用的常数次查询搜索。

“最优”一词以所采用的问题模型为前提。如果判定条件具有可利用的结构,其他算法就可能优于格罗弗搜索。有序集合、代数问题,或可用高效动态规划求解的问题,都不能仅靠不受限制的黑箱访问来充分刻画。反过来说,将格罗弗搜索用于任意可满足性问题实例的全部 2n2^n 种赋值,大约需要 2n/22^{n/2} 次判定查询,这相对于 nn 而言仍是指数级的。它既不能为具有NP完全性的问题提供通用的高效解法,也不能解决P与NP问题。

并行资源也会改变比较结果。若将一个仅含一个解的搜索空间均衡划分,由 PP 个独立的量子处理器分别搜索,则理想情况下,每个处理器的查询深度可达到

O ⁣(NP).O\!\left(\sqrt{\frac{N}{P}}\right).

忽略验证和协调开销后,预言机调用总次数为 O(NP)O(\sqrt{NP})。因此,通过划分搜索空间来缩短搜索所需的实际查询深度,处理器数量必须按加速倍数的平方增长。如果不计入资源差异,就将单个量子处理器与大型经典计算集群比较,或反过来比较,都可能掩盖真正的优势。

振幅放大、估计与计数

Grover 搜索是振幅放大的一个特例。振幅放大的一般形式由 Brassard、Høyer、Michele Mosca 和 Tapp 提出,并于 2002 年发表。这一更一般的构造不以均匀叠加态为起点,而是从量子过程 AA 出发,由它制备

A∣0⟩=a ∣ψgood⟩+1−a ∣ψbad⟩.A|0\rangle = \sqrt a\,|\psi_{\mathrm{good}}\rangle + \sqrt{1-a}\,|\psi_{\mathrm{bad}}\rangle.

成功判定用于识别成功子空间,而 aa 是按通常方式执行一次 AA 后进行测量时获得成功的概率。

经典的独立重复通常需要 O(1/a)O(1/a) 次尝试,才能以常数概率获得成功。振幅放大将其减少为对制备过程及其逆过程的 O(1/a)O(1/\sqrt a) 次相干调用。其中一个反射操作标记成功态,另一个则关于 A∣0⟩A|0\rangle 作反射。当 AA 制备均匀分布且 a=M/Na=M/N 时,就得到了 Grover 搜索。

必须实现 A−1A^{-1} 是一项实质性的要求。常规的随机化程序未必能原封不动地嵌入振幅放大过程。随机选择、临时值和中间计算都必须以可逆量子计算的形式表示,同时保持相关的相干性。如果 AA 采用某种启发式方法,生成有希望的候选解的概率高于均匀采样,那么振幅放大可以在这一更优的基线上进一步提升性能,而不必舍弃有用的经典结构。

一种相关技术是量子振幅估计,它估计的是 aa 的值,而不是返回一个满足成功条件的输入。在最初的形式中,它对振幅放大算子执行量子相位估计。在相关的二维子空间内,该算子的特征值对应于角度 ±2θ\pm2\theta,其中 a=sin⁡2θa=\sin^2\theta。因此,估计这些角度就能估计成功概率。

在适当的预言机模型下,要在固定置信度下达到加性误差 ϵ\epsilon,只需调用相关操作约 1/ϵ1/\epsilon 次;相比之下,经典方法在最坏情况下需要约 1/ϵ21/\epsilon^2 个独立样本。这一结果描述的是计算量随精度变化的标度关系,并不意味着普遍适用的端到端加速。制备采样分布、评估结果以及实现受控操作的成本,仍然是计算成本的一部分。后续变体以不同的实验安排和经典推断过程,取代了最初的相位估计电路。

令 a=M/Na=M/N,就得到用于估计标记输入数量的量子计数。相对精度与加性精度的表现不同,尤其是在解很稀少时,因此“以平方根时间完成计数”并不是完整的性能描述。计数可以为后续搜索确定迭代次数提供依据;更一般地说,振幅估计将 Grover 算法的几何机制与数值期望估计,以及基于采样的计算的量子版本联系起来。

搜索、优化与算法应用

一个直接应用是穷举搜索布尔公式的变量赋值。对于 nn 个变量,寄存器表示 2n2^n 种赋值,预言机则判断候选赋值是否满足公式。如果恰好只有一种赋值满足公式,格罗弗搜索需要进行 O(2n/2)O(2^{n/2}) 次求值。对于包含 mm 个子句的公式,仍然需要一个可逆求值电路,其开销取决于 mm、子句结构、可用工作空间以及所选的量子门分解方式。

这个例子说明了验证与发现之间的一般区别:即使找到一个候选解很困难,验证它也可能很容易。格罗弗搜索利用的是对这一验证过程的相干访问,但这并不意味着验证过程本身没有开销,也不能据此认定它优于所有专门设计的经典算法。经典求解器可以利用传播、分解、学习或特定问题的约束,而对所有赋值进行均匀搜索不会利用这些信息。

优化可以归约为一系列阈值搜索。假设每个候选项都有一个值 g(x)g(x),当前候选项的值为 tt。搜索预言机标记满足 g(x)<tg(x)<t 的输入。搜索成功后,用更好的候选项替换当前候选项,随后更新阈值。克里斯托夫·迪尔和彼得·赫耶于1996年提出的最小值查找算法利用这一原理,以有界错误概率和 O(N)O(\sqrt N) 次值查询,在 NN 个黑箱值中找出最小值。

阈值构造之所以有用,是因为它将优化目标转化为一系列非是即否的判定条件。然而,完整实现必须以可逆方式计算目标函数值,将其与阈值比较,并清除临时算术结果。如果目标函数求值涉及大规模模拟或大量内存访问,这些工作就可能占据搜索开销的主要部分。改进的次数及其调度方式也很重要;如果只是针对每个可能的阈值,分别独立执行一次完整搜索,就无法达到上述最小值查找的复杂度界限。

格罗弗式子程序也出现在组合搜索、碰撞相关问题以及较大数据结构内部搜索的算法中。最终的总体复杂度必须针对整个算法来推导。将一个线性循环替换为查询次数为平方根量级的子程序,并不一定能使总运行时间降至原来的平方根量级,尤其是在其他阶段占主导地位,或内部计算必须以相干方式调用时。

在机器学习和信息检索中的应用,对有关数据的假设尤其敏感。搜索可由紧凑计算过程生成的模型或判定条件,与搜索仅存储在传统内存中的记录并不相同。要声称实现了加速,就必须明确说明量子电路如何访问候选数据、如何提取有用的输出,以及作为比较对象的经典算法允许进行哪些预处理。

对密码学的影响

格罗弗搜索改变了对称密钥密码学中穷举密钥搜索的理论成本。对于使用均匀随机选取的 kk 位密钥的密码算法,候选空间包含 2k2^k 个密钥。预言机可以标记与已知明文—密文对相符的密钥。如果这些约束能够唯一确定一个密钥,理想量子搜索所需的密码算法求值次数为

2k/22^{k/2}

量级,而经典搜索需要 2k2^k 量级的尝试次数。

密钥唯一这一条件至关重要。根据密钥长度和分组大小的不同,一组较短的已知明文—密文对可能与多个密钥相符。增加明文—密文对可以减少错误候选密钥的数量,但检查这些额外的数据对也会增加预言机的成本。以可逆方式实现加密、将计算得到的密文与已知值进行比较、施加相位标记,以及通过反计算清除临时值,都是攻击电路的组成部分。

对于高级加密标准,人们常说量子穷举搜索会“将密钥长度减半”,这只是对上述理想查询分析中指数变化的简略表述,并不意味着攻击 AES-128 所需的资源与传统的 64 位经典搜索相当。容错量子实现需要逻辑量子比特、大量非平凡量子门,以及长时间保持相干性的一连串预言机调用。资源估算结果在很大程度上取决于电路设计,以及对底层硬件所作的假设。

对于输出长度为 nn 位的理想密码散列函数,如果从足够大且合适的输入域中采样,寻找指定摘要的原像同样需要 2n/22^{n/2} 量级的量子查询。寻找碰撞则是另一个问题:攻击者要找到任意两个输出相同、但彼此不同的输入。其量子复杂度不能通过简单套用原像搜索公式得到。在标准查询模型中,通用量子碰撞算法可以达到 2n/32^{n/3} 量级的查询次数,但这一结果在内存需求和实际实现方面有重要的限制条件。

因此,格罗弗算法在密码学中的作用与肖尔算法不同。肖尔算法利用多项式时间量子算法,攻击广泛使用的、基于整数分解和离散对数的公钥密码学系统的数学基础。格罗弗搜索则为穷举搜索提供通用的平方级加速,而非同样的结构性破解。这一区别是后量子密码学中的关键:量子计算对公钥密码学所依赖假设的威胁,与其对对称密码安全裕度的削弱,源于不同的算法,需要分别分析。

电路实现、实验与物理限制

标准的量子电路通过用阿达马门对相位操作进行共轭变换来实现扩散:

D=H⊗n(2∣0n⟩⟨0n∣−I)H⊗n.D = H^{\otimes n} \bigl(2|0^n\rangle\langle0^n|-I\bigr) H^{\otimes n}.

忽略一个无关紧要的全局相位,中间的操作可以通过先施加泡利 XX 门来交换零和一,再使用多重受控相位门来实现。这些多量子比特操作最终必须分解为硬件支持的门。辅助量子比特可以降低电路深度或简化分解,因此需要在空间与执行时间之间进行权衡。

对于实际问题,预言机通常比扩散操作更难实现。可逆算术运算可能需要进位寄存器、比较标志位和临时值。可以存储一些中间结果以减少重复计算,而量子比特资源更紧张时,则可能不得不反复进行计算和反计算。这使得空间复杂度与电路深度紧密耦合。即便搜索的查询次数最优,如果其预言机所需的门数量过多,或需要代价高昂的数据移动,它仍可能缺乏实际吸引力。

研究人员已在多种物理平台上通过实验实现了小规模格罗弗搜索。1998 年,艾萨克·庄、尼尔·格申费尔德和马克·库比内克报告了一项核磁共振实验,在包含四个元素的空间中实现了快速量子搜索。这类实验检验了态制备、受控相位操作、干涉和读出。但它们本身并不能证明量子搜索相较经典搜索具有实际速度优势,因为问题规模很小,实验开销可能超过所演示的计算本身。

噪声既影响预言机,也影响扩散步骤。相位误差可能改变预期的旋转角,而退相干则可能破坏累积标记态振幅所需的干涉。由于有效迭代次数按 N/M\sqrt{N/M} 增长,搜索规模越大,所需的相干计算时间就越长。系统性误差的累积方式可能不同于独立随机误差,因此,仅给出一个平均门保真度,不足以预测深度搜索电路的成功概率。

大规模实现通常需要量子纠错和容错的逻辑量子比特。此时,物理资源开销还包括纠错综合征测量、经典解码,以及制备某些逻辑门所需的辅助态。这些开销可能远远超过搜索寄存器名义上所需的量子比特数。此外,采用量子随机存取存储器的方案假定能够以相干方式访问已存储的记录;构建并保护这种访问结构,本身就是一项重大的资源需求。因此,实际评估必须涵盖完整流程:从经典问题数据出发,经过可逆谓词求值、容错振幅放大和测量,直至最终验证。