当解的数量未知时，量子搜索如何找出全部解？

解的数量未知时的完整搜索

Grover 算法在解的数量已知时，能以二次加速找到一个被标记的元素，但这里更困难的任务不同：在解集 S 的基数 M 未知的情况下，找出 S 的每一个元素。搜索空间有 N = 2^n 个元素，解的比例为 λ = M/N，而由于 M 未知，算法不能简单地运行固定次数的迭代。它改为在后验期望的未发现解数量降到预设容差 ε 时停止。

第二个复杂之处在于，测量一个候选并不会揭示它是否为解。每个被测候选仍需对 f(x) 做一次验证，可以用经典方式或通过量子预言机完成。论文用测试比 0 < r < 1 刻画这一成本，定义为一次验证的时间除以一次振幅放大迭代的时间，并把 r = 1 视为两者成本相等的极限情形。当经典与量子验证都可用时，由更快的那一种决定 r。

为什么单纯的 Grover 搜索不够

Grover 迭代把一个翻转被标记态相位的预言机 O 与一个扩散算子 D 结合起来。在由被标记态与未标记态的均匀叠加所张成的二维子空间中，m 次迭代后的成功概率为 P_Grover(λ, m) = sin²((2m + 1)θ)，其中 θ = arcsin√λ。这一形式暴露出两个局限。选择使概率最大的迭代次数需要知道 λ，而且即使取最优的整数迭代次数，一般也达不到成功概率为一。

广义定点量子搜索，论文中称为 YLC 搜索，通过增加一个可控的宽度参数 w 来抑制过冲，从而应对第二个局限。但宽度是一个需要额外调节的参数，论文的问题就是：一旦把每次迭代的成本计入，这种调节是否值得。

在三种搜索模式上的自适应贝叶斯策略

所提出的算法把经典采样、Grover 搜索和 YLC 定点搜索统一为一个自适应贝叶斯策略。它从解数量的先验出发，在每个实例之后更新后验，把每个被测元素从活动搜索空间中移除，然后选择下一个实例——对 YLC 还包括宽度 w——使单位执行时间成本下的后验预测成功概率最大。当后验期望的未发现解数量至多为 ε 时，搜索终止。

这是一个逐实例的贪心准则，论文明确指出，其最优性与界限结论针对的是单个搜索实例的得分，而不是由此得到的自适应策略的总运行时间。对于任何要把该算法与固定迭代基线作比较的人来说，这一区分很重要。

r = 1/4 以下定点搜索无法带来帮助

论文的核心阈值是 r = 1/4。对任意后验分布，以及在 0 < r ≤ 1/4 的情形下，作者证明 YLC 定点搜索无法改进由经典采样与未修改 Grover 搜索混合所得的最佳贪心得分。在该情形下，对 YLC 宽度的优化可以完全省去。

数值工作支持这一证明。在为有限数据库 N = 16384 以及连续极限 N → ∞ 构建、均推进到深度 20 的决策树中，在采样比值 r ≤ 0.30 时没有任何后验选择正宽度。在 r = 0.35 时，有限树 2,097,151 条后验记录中只有 1400 条选择了正宽度（约 0.0668%），最大值为 w ≈ 0.0211，而连续树有 140 条记录如此（约 0.00668%），最大值为 w ≈ 0.0247。在 r = 1/4 的配对基准中，全部 36,864 对都具有相同的动作、结果和后验均值，且 w 始终为 0。

阈值以上收益存在上界

对于 1/4 < r ≤ 1，论文推导出定点搜索相对于最佳 Grover 得分所能取得的相对得分改进的上界。该上界随振幅放大迭代次数的增加而减小，它同时界定了广义迭代在仍可能保有优势的前提下所能承担的额外成本。

残差分析对此做了数值检验。在有限树与连续树所有被选深度上，数值 YLC 与 Grover 差距同理论预测之间的最大残差为 5.3 × 10⁻¹⁵，在数值允许范围内没有任何状态超出其后验特定界限。在 r = 0.25 时残差保持在数值零，并在所有采样深度和比值上保持非正。

经典采样应在何处交接给量子搜索

从均匀先验出发，论文通过对解数量概率分布的积分近似，确定了经典采样与量子搜索之间的最优过渡点。对于 1/4 < r ≤ 1，从经典实例到量子实例的首次过渡由一个带一次振幅放大迭代的优化实例实现，论文给出了该过渡处所选的 YLC 宽度。

对于 r < 1/4，先前经典查询的数量具有 r⁻² 的主项，并带有一个显式的 r⁻¹ 修正。渐近比较覆盖了 s ∈ {0, 1, 2, 4} 的 56 个过渡以及 0.001 ≤ r ≤ 0.25 范围内的 14 个比值。在 r = 0.10 时，四个 s 值上的绝对相对误差介于 0.62% 与 2.02% 之间，而在 r = 0.001 时降至 0.0000403% 与 0.000213% 之间。s = 0, …, 4 的全部 558 个直接计算的过渡都与预测一致，其中 m = 1 给出首次量子跨越。

配对基准对运行时间说明了什么

配对完整搜索基准使用大小为 N = 4096 的数据库、测试比 r ∈ {0.25, 0.50, 0.75, 1}、真实解数量 M ∈ {1, …, 32, 64, 256, 1024, 4096}，每个 (M, r) 做 1024 次配对试验并共享随机流，共产生 294,912 条轨迹。运行时间按 T = Q_q + rQ_c 度量，因此每个搜索实例贡献其量子深度 m 和验证成本 r。

在 ε = 0.10 时，有 2114 条轨迹在找回全部解之前就停止，占所记录轨迹的不到 0.72%。允许定点实例在较大的验证比下降低了许多被测稀疏情形的平均缩放运行时间，但这一改进在所考虑的解数量上并不一致。作者还报告，提高停止容差可以降低运行时间，同时大幅增加留下未发现解的运行比例——这是由容差 ε 直接控制的、速度与完整性之间的权衡。

测试比决定该用哪种搜索模式

论文确立的实际优先级是一个单一比较，而不是对定点搜索的普遍认可。先看测试比 r：如果验证相对于一次振幅放大迭代很便宜，具体说 r ≤ 1/4，那么最佳策略是经典采样与未修改 Grover 搜索的混合，YLC 宽度可以保持为零。只有当 r 超过 1/4 时，定点搜索才成为候选，而且即便如此，它相对于最佳 Grover 得分的优势也被论文的界限所限制，该界限随所用振幅放大迭代次数增多而缩小。

第二个决策变量是停止容差 ε。由于基准显示放宽 ε 可以缩短运行时间，同时提高留下未发现解的运行比例，因此决定结果实际有多完整的是 ε 的选择，而不是搜索模式的选择。论文关于贪心策略渐近最优的结论适用于解数量已知且远小于数据库规模的情形，在该情形下该策略的总成本比在每个阶段都使用精确搜索实例低约 12.14%；这一参照情形不应被理解为可延伸到 M 未知的设定，在那里算法必须推断何时停止。

本文引用的文献