仅仅制备叠加态并不能带来量子加速:测量只返回一个结果。算法必须利用干涉,使有用结果的概率增大;复杂度结论也必须明确输入模型和计数的资源。
量子傅里叶变换
定义 2.2.1
(量子傅里叶变换)
取 和 。 个量子比特上的量子傅里叶(Fourier)变换 是线性映射
命题 2.2.2
(傅里叶变换的酉性)
是酉的。
证明
(各列标准正交)
第 列和第 列的内积是 。若 ,和为 。否则它是有限等比和,其公比不为 1、但公比的 次方为 1,故和为 0。因此各列标准正交,。
例题 2.2.3
(基态的傅里叶变换)
当 且输入为 ,输出是 。直接测量各标签的概率均为 ;只有后续变换使相对相位产生干涉,它们才会发挥作用。
逆变换把 换为 。若将每个旋转都算作一个门,可用 Hadamard 门和受控相位旋转构造包含 个门的精确电路;若只允许固定的离散门集,则需近似,代价还依赖于所需精度。
相位估计与求阶
设 ,其中 ,且已能制备特征态 。把 个控制比特初始化为 并作用 Hadamard 门。随后作用受控幂 ,得到
若 恰好成立,第一个寄存器就是 ;作用 再测量,必然得到 。不是 整数倍的相位会给出集中在 附近的分布,而非保证得到精确答案。 的受控幂能否实现及其代价,都是算法资源假设的一部分。
例题 2.2.4
(落在两个格点之间的相位)
令 ,即 ,取 ,它不是 的整数倍。经过逆变换,结果 的振幅为 。记 ,其概率为 。当 时, 的概率分别为 、约 、 和约 ,总和为一。最可能的结果 满足 最接近 ,但它的概率只有约 :对这类相位,此过程给出的是一个分布,而不是精确答案。
常见错误
(把测量结果当成相位本身)
测得的结果是整数 (),相位估计值是 ,而不是 。用三个控制比特、 时,结果是 (二进制 ),估计值是 。
定义 2.2.5
(模 M 的阶及其特征态)
求阶使用一个特定的酉变换。对与整数 互素的 ,模 乘以 置换余数,因而在包含这些余数的寄存器上定义酉变换 ;对未使用的基态可扩充为恒等变换。若 是满足 的最小正整数,则对 ,
循环平移求和下标便得到特征值。容易制备的 是这些特征态的等幅叠加;相位估计抽样得到关于 的信息。在精度与互素条件适当时,可以用连分数恢复候选的阶。仍需重复并用经典计算验证:一次抽样未必揭示 。
命题 2.2.6
(由偶数阶得到因子)
设 与 互素, 是 模 的阶。若 为偶数且 ,则 与 都是 的非平凡因子,即既不等于 也不等于 。
证明
(乘积可被 M 整除,而两个因子都不能)
记 、,则 可被 整除。由于 而 是最小的正指数,故 ;由假设 。因此 且 。若 ,则由 得 ,矛盾;若 ,则 ,同样矛盾。所以两个最大公因数都严格介于 与 之间。
证明透视
各项假设在哪里用到
每项假设恰好用一次。 的最小性给出 。偶数性使 成为整数幂。条件 正是 。唯一不显然的一步是互素性论证:若某个因子与 互素,就会迫使 整除另一个因子,而上述两项假设正好排除了这种情况。去掉条件 , 就可能整除 ,乘积便不能给出分解。
例题 2.2.7
(用底 2 分解 15)
模 的幂依次为 ,所以阶为 ,是偶数。于是 。因此 ,,而确实 。
反例模式
并非每个底都能分解 M
一个诱人的说法是:每个与 互素的 都能这样分解 。取 、:,所以阶为 ,且 。于是 ,,两者都是平凡的。条件 不能去掉。奇数阶则以另一种方式失败:、 的阶为 , 没有定义。这样的底必须舍弃,另选一个底再试。
这是 Shor 分解算法所用的经典归约,并不意味着每个 都成功。
作为旋转的 Grover 搜索
定义 2.2.8
(被标记与未标记的分量)
假设 个基标签中有已知的 个被标记,其中 ;相位预言机恰好对被标记的标签翻转符号。令 是被标记标签的均匀叠加, 是未标记标签的均匀叠加,则均匀初态为
定理 2.2.9
(Grover 成功概率)
在此设定下,令 为一次 Grover 迭代:先对被标记标签翻转符号,再作用 。则 ,所以 次迭代后的成功概率为 。
证明
(两次反射合成旋转)
预言机是关于 轴的反射, 是关于 轴的反射。两者都保持 张成的平面不变。在有序基 中,预言机是 ,而 的矩阵元为 、 和 ,于是
把它作用于 得到 。从 出发,对 归纳即得所述公式。
取 接近 ,当 时,用 次预言机调用即可得到高成功概率。继续迭代反而可能使成功率降低:旋转会越过目标。此界统计的是预言机查询次数,并不包括实现预言机或制备输入数据的代价。 和 需另行处理,不能直接使用上述二维公式。
例题 2.2.10
(四个标签、一个被标记)
例如 且只有一个被标记标签时,,一次迭代给出 。在理想模型下,此时测量必然得到被标记标签。
练习与解答
快速检查
(计算 和 。)
解答 · 答案
;由酉性,。
快速检查
(精确相位估计使用三个控制比特时,特征值 对应什么结果?)
解答 · 答案
逆变换前控制寄存器为 ;测量必得二进制 。
快速检查
( 且一个标签被标记时,两次 Grover 迭代后的成功概率是多少?)
解答 · 答案
此时 ,概率为 ;第二次迭代已经越过最佳位置。