Grover 搜索从均匀叠加态出发,但其旋转原理适用于更一般的制备过程。如果一个算法已经以已知的非零概率 产生所需结果,振幅放大可以通过分别关于所需子空间和已制备状态作反射,提高成功概率。代价是必须能够相干地实现制备操作及其逆操作,而不仅仅是把它当作黑箱来抽样。
制备好分量和坏分量
定义 2.8.1
(好分量与坏分量)
设 是有限维寄存器上的酉算子,令 。设 为到好子空间的正交投影。暂且假设 ,其中
归一化向量 互相正交。取满足 的 ,则
定义 2.8.2
(相位预言机、制备反射与迭代)
定义相位预言机 和关于已制备状态的反射 。后者实现为 。一次放大迭代是 :最右边的预言机先作用。这里 表示整个寄存器的全零初始基态。
概念视角几何
两次反射合成一次旋转
同一个迭代有平面几何的描述。在 张成的平面中,预言机 固定 并把 变号,所以它是关于过 的直线的反射; 则是关于过 的直线的反射。这两条直线的夹角为 ,而关于夹角为 的两条直线作两次反射,合成为转角 的旋转。因此每次迭代把状态向 转动 ,而 起初与 的夹角为 。下一节的矩阵把这幅图像化为计算。
两次反射为何产生旋转
定理 2.8.3
(振幅放大公式)
经过整数 次迭代,
区分好子空间与其正交补的测量以概率 成功。
证明
(两次反射合成旋转)
两个反射都保持 张成的平面不变。在此有序基下,简记 、,
相乘得
它作用于 得到 。同样的和角公式通过归纳法证明所述公式。 的系数平方即为成功概率。
证明透视
证明在哪里用到各项假设
论证分三部分。第一,平面的不变性:由于 、, 把 变号并固定 ;而 留在平面内,因为 属于该平面。这需要 ,正是它使 成为良定义的标准正交对。第二,唯一不属例行的一步是倍角化简 、、,它把乘积化为旋转矩阵。第三,归纳得以闭合,是因为转角 的旋转把 的角度增加 ,所以起始角 在 步后成为 。其中没有任何近似;旋转只作用于两个系数,所以原来好投影内部的相对权重得以保留:在成功条件下,更细的计算基测量服从 的分布。
例题 2.8.4
(一次迭代后必然成功)
假设
且 是好结果。那么 ,所以 。一次迭代后的好振幅为 ,必然成功。在成功条件下, 和 的概率分别为 和 ,并不相等。好子空间内的分布由状态制备决定。
常见错误
(混淆 与 )
角 由 定义,而不是 。当 时,正确的角是 ,因为 ;若用 ,便得到错误的角和错误的成功概率。 次迭代后的成功概率是 ,一般只在 时等于 。
选择迭代次数
当 已知时,取最接近 的非负整数 ;并列时任选。由于 ,目标数非负,而取整给出
成功概率至少为 。特别是当 很小时,这个值接近一。由于 ,此选择满足 。每次迭代各调用一次 、 和 ,并执行一次关于 的反射;初始制备还需要额外调用一次 。这些是理想相干操作;查询次数不包括它们依赖具体问题的实现成本。
例题 2.8.5
(在八个项目中搜索一个被标记的项目)
取 ,令 标记一个基态,则 、、,。于是 ,,规则选取 。记 ,有 ,所以
这高于保证的 。作为比较, 给出 , 给出约 ,所以 是最佳选择。
例题 2.8.6
(并列情形:成功概率停在一半)
设 ,则 , 恰好位于 与 的正中间;规则两者皆可。成功概率为 ,而 是 的奇数倍,所以对每个 其值都是 。保证值 取等号,而且无论迭代多少次都不能得到必然成功:状态每次转动 ,在此从不落在好方向上。
反例模式
更多迭代可能抵消改进
一个诱人的想法是:每多迭代一次,成功概率只会变好。若 ,则 。立即测量已制备状态的成功概率为 。一次迭代后的成功概率反而为 。状态已旋转越过好方向。无限重复同一迭代不是单调改进的规则。
若 ,归一化的 无定义,已制备状态没有好分量:仅凭这些反射无法创造该分量。若 ,初始测量已必然成功。这些端点情形必须与二维公式分开处理。
保证所依赖的假设
已知 才能选择上述 ;成功概率未知时需要另一种策略和分析。预言机必须相干地施加正确相位,也必须确实能够使用 。只从 的输出产生独立经典样本,并不足以实现关于 的反射。此保证针对理想电路,计算预言机和制备的调用次数;不完美操作和识别好输出的复杂度需要另外分析。
常见错误
(把关于 的反射当成关于 的反射)
算子 单独使用时,是关于全零态的反射,而全零态一般并不是已制备状态。关于 的反射是共轭形式 。漏掉 和 会得到另一个算子,旋转公式对它并不成立。
这个一般结论包含均匀搜索:取 ,令 标记 个基态中的 个,则 。只要能够实现所需反射,它也允许非均匀制备态和任意好子空间。
练习与解答
快速检查
(当 时,求 及两次迭代后的成功概率。)
解答 · 答案
此时 ,且 :第二次迭代越过目标,因为一次迭代已经达到概率 。
快速检查
(当 时,规则选取哪个 ?成功概率是多少?)
解答 · 答案
此时 ,,所以 ,取 。令 ,,所以成功概率为 ,高于保证的 。
快速检查
(在第一个例子中,一次迭代后测得 的概率是多少?)
解答 · 答案
是 :以概率 到达好子空间,其中 的条件概率为 。
快速检查
(为什么只获得 的经典样本分布,不足以提供所述反射?)
解答 · 答案
构造 需要相干访问 及其逆操作,包括经典样本分布不包含的相位信息。