量子科技中心_量科网

Grover算法在给定目标集合全局预言机的条件下，对无结构搜索实现了二次加速。然而在许多应用中，目标集合被指定为多个约束集合的交集。为交集构建全局预言机可能代价高昂，而单个约束预言机的实现往往简单得多。该团队研究了一种直接使用这些约束预言机的随机化Grover搜索算法。在每次迭代中，研究人员随机选择其中一个对应的Grover算子。对于均匀采样的两算子情形，该团队证明经过 \[ Θ\left(\frac\pi4\sqrt{\frac{N}{r}}\right) \] 次迭代后，成功概率趋近于1，其中 \(r\) 是交集的大小。因此，该算法在不需全局预言机的情况下，达到了与标准Grover搜索相同的渐近查询复杂度。随后，该团队通过一个近似期望Grover演化的辅助算子，将分析推广到任意采样分布和任意数量的Grover算子，同时保持相同的渐近复杂度。该工作进一步表明，高度偏倚的采样分布仍能实现接近单位的成功概率，从而允许更频繁地使用代价更低的Grover算子。最后，该团队证明了渐近最优性，并通过数值模拟支持了理论结果。