Ancilla-mediated fixed-point quantum search using Grover iterations

技术摘要：基于辅助比特介导的固定点量子搜索（利用 Grover 迭代）

问题陈述
Grover 量子搜索算法为在非结构化数据集中寻找标记项提供了二次加速（$O(\sqrt{N/M})$），相比于经典的线性搜索（$O(N/M)$）。然而，标准算法存在“舒芙蕾问题”（soufflé problem）：其成功概率遵循正弦曲线，需要精确的迭代次数才能使发现解的概率最大化。如果解状态的数量 ($M$) 未知，过旋转或欠旋转都会导致成功概率急剧下降。虽然已有研究提出了固定点搜索算法以确保单调收敛，但许多现有方法依赖于复杂的相位匹配技术（例如 $\pi/3$ 相位偏移）或随机试错法（例如 Boyer 等人的方法），这些方法可能会带来更高的查询开销或丢失 Grover 原创算法中直观的几何结构。

方法论
作者提出了一种辅助比特介导的固定点量子搜索算法，该算法保留了 Grover 原创算法的几何反射架构，同时在无需精确了解 $M$ 的情况下实现了鲁棒收敛。

1. 辅助比特介导架构： 系统利用 $n$ 个数据量子比特和一个辅助量子比特。算法在由 $\{|0_a\rangle|R\rangle, |0_a\rangle|S\rangle, |1_a\rangle|R\rangle, |1_a\rangle|S\rangle\}$ 张成的四维不变子空间内运行，其中 $|S\rangle$ 代表解子空间，$|R\rangle$ 代表非解子空间。
2. 固定点算符 ($\hat{F}(\theta)$)： 作者并非使用相位门来创建吸引盆（attraction basins），而是定义了一个由 Grover 原创的反射操作（Oracle $\hat{O}$、状态准备 $\hat{P}$ 及其伴随算符）构建的幺正算符 $\hat{F}(\theta)$。
   • 该算符将数据量子比特的解振幅映射到辅助量子比特的状态 $|1_a\rangle$。
   • 至关重要的是，如果测量得到的辅助比特为 $|0_a\rangle$（失败），系统并不会坍缩到随机状态，而是重置为一个相干叠加态 $|0_a\rangle(\cos(2\theta)|R\rangle + \sin(2\theta)|S\rangle)$。这保留了初始状态的信息（编码在角度 $2\theta$ 中），使得搜索可以从已知状态继续进行，而不是重新开始。
3. 确定性调度： 算法采用了一种确定性的几何迭代调度。它执行一系列由 $j = 0, 1, \dots, a-1$ 索引的检查。在每一步 $j$，状态首先通过 $g_j$ 次 Grover 迭代进行放大（其中 $g_j$ 遵循倍增调度：$0, 0, 1, 3, 7, \dots$），然后接受固定点检查。
4. 测量与终止： 在放大之后，应用固定点算符并测量辅助比特。
   • 如果观测到 $|1_a\rangle$，则数据量子比特已坍缩到解状态 $|1_a\rangle$，搜索终止。
   • 如果观测到 $|0_a\rangle$，过程将使用保留的角度 $2\theta$ 进入调度中的下一次迭代，以进一步放大解的振幅。

核心贡献

• 几何独特性： 与需要相位门的相位匹配固定点方法（如 Yoder 等人、Li 等人）不同，本方法利用了 Grover 的实平面反射。这保持了原始算法直观的几何架构。
• 查询效率： 所提方法在每次应用固定点算符 $\hat{F}(\theta)$ 时仅需一次 Oracle 调用。然而，每次检查的总查询成本包括之前的 Grover 放大步骤 ($g_j$)，而每个放大步骤也构成一次 Oracle 调用。这与现有的相位匹配固定点方案形成对比，后者通常在每次迭代中需要两次 Oracle 调用，本方法有效地降低了与固定点机制相关的门深度，并减少了对近程硬件的退相干影响。
• 无需随机化的鲁棒性： 该算法提供了一个确定性的终止调度和保证的成功底线，这使其区别于依赖于概率停止规则的随机化方法（如 BBHT）。
• 作为成功标志的辅助比特： 辅助比特纯粹作为可测量的成功标志。如果结果为负，测量并不会破坏数据量子比特的相干性，从而允许迭代优化。

结果与性能

• 成功概率： 作者证明，无论解的数量 $M$ 是否已知，该算法都能实现 92.6% ($0.9259$) 的严格成功概率下界。该界限是基于测量角度落在区间$[\pi/4, \pi/2)$ 内的最坏情况推导得出的。
• 查询复杂度：
  • 实现 $\ge 92.6\%$ 成功概率的最坏情况查询复杂度为 $O(\pi\sqrt{N/M})$。
  • 期望 Oracle 调用次数约为 $O(\sqrt{N/M})$。
  • 针对 $N=10^{10}$ 的数值模拟显示，期望成功概率约为 95%，且期望查询复杂度与最优 Grover 迭代次数相当（具体而言，期望成本为 $\approx 1.33 \times \epsilon$，其中 $\epsilon$ 是已知 $M$ 时的最优迭代次数）。
• 比较： 在保持相同的二次加速的同时，该方法在常数因子方面优于 Li 等人的固定点算法（其查询复杂度为 $O(5.643\sqrt{N/M})$）。

意义
本文声称解决了在 $M$ 未知情况下的非结构化搜索“舒芙蕾问题”，即通过将成功概率与精确的迭代次数知识解耦。通过将 Grover 原创的基于反射的几何结构与辅助比特介导的固定点算符相结合，该算法在无需相位门开销或随机策略不可预测性的情况下，实现了鲁棒的收敛。作者强调，这种方法在保持 Grover 算法核心架构的同时，提供了一个确定性的调度和高成功底线，使其成为近程量子硬件（其中门深度和退相可是关键约束）的一个实际候选方案。该工作还暗示了未来集成到动态优化问题的自适应搜索框架中的潜力。