寻阶电路不会直接打印出阶。它可以产生接近某个分数的测量结果,而该分数的最简分母整除阶。经典后处理必须恢复候选值、检验其含义,有时还要舍弃结果。当候选值用于分解因数时,区分周期与最小周期尤其重要。
作为特征相位的阶
定义 2.7.1
(阶与乘法酉算子)
设 、 且 。阶 是满足 的最小正整数。它存在,因为乘以 会置换模 的剩余类;特别地 。在包含这些剩余类的基态的寄存器上,对 定义 ,未使用的基态保持不变。这是酉算子。
定义 2.7.2
(乘法酉算子的特征态)
轨道 有 个互异元素。对 ,定义
循环移动指标得到 。这些 构成轨道子空间的标准正交基,傅里叶(Fourier)正交性给出
因此,从 出发的相位估计实验,其测量分布与下述过程相同:先从 中均匀选取 ,再估计 。这个概念上的混合由特征态的正交性得到;电路无需测量 。
精度与待重构的分数
选择控制寄存器大小 ,满足 。固定 ,令 是最接近 的整数,并使用固定的并列处理规则。它属于 ,理想相位估计返回这个特定 的概率至少为 。最近网格点界来自其等比和分布:若 ,则 ;恰好落在网格点时概率为一。这里没有绕回歧义:对 ,,而网格间距小得多。
在这个有利事件上,
将 约成最简分数 ,则 ,其中 。因此 ,同一个误差严格小于 。
我们引用经典的连分数逼近定理:若最简分数 满足 ,则它是 的简单连分数的一个渐近分数。因此 出现在测得的有理数 的渐近分数中。这里引用定理而不证明。欧几里得(Euclid)算法计算这些渐近分数;对有限有理数展开可精确处理,无需浮点舍入。
命题 2.7.3
(靠近 的有界分母分数是唯一的)
固定整数 与 。满足 且 的最简分数 至多一个。
证明
(不同的分数相距甚远)
设 是两个分母不超过 的最简分数。因为 是非零整数,所以 。若两个分数与 的距离都严格小于 ,由三角不等式得 ,矛盾。
这个唯一性是误差保证,而不是仅凭单个样本便能知道有利事件发生的方法。
常见错误
(把约简后的分母当成阶)
观察的分数为 ,但连分数以最简形式揭示它。如果 与 有公因子,其分母就是 的真因子。零相位无论阶是什么都给出分母 1。因此精确的相位估计并不自动成为阶的估计。
验证及其局限
计算分母至多为 的渐近分数,并对每个分母 用模幂运算检验: 是否成立?任何通过检验的 都是周期,但不一定是最小周期。
命题 2.7.4
(由互素样本恢复阶)
设 ,且 ,其中 且 。则 会作为不超过 的渐近分数分母出现,每个通过检验的分母都是 的倍数,而在所检验的渐近分数中,通过检验的最小分母就是 。
证明
(周期都是阶的倍数)
由于 , 的最简形式分母为 ,并由逼近定理出现在渐近分数中。若 ,写 ,;则 ,而 的最小性迫使 。所以每个通过检验的周期都是 的倍数,因而不小于 ,而 本身通过检验。
这个充分事件的概率至少为
其中 计数 中与 互素的剩余类,并约定 。此下界结合了均匀选取 和最近网格点保证。其他样本也可能得到正确的阶。该表达式依赖 ;单凭这个计算不能得到对所有 一致的正常数下界。完整的因数分解算法还需要重复及进一步分析。
反例模式
通过检验的指数不一定是阶
对 、,阶为 。相位 的样本约简后分母为 2,但 ,所以检验拒绝它为周期。反之, 通过检验,因为 ,但它不是最小周期。每个通过检验的分母都是 的倍数,但不一定等于 。
例题 2.7.5
(从精确的网格样本读出阶)
当 、 时,取 。最近网格点结果 给出 ,已经是最简分数。其分母通过 的检验。这里 与 4 互素,所以有利事件论证将阶确定为 4。结果 则给出 ,其分母 2 被拒绝。对于其他阶,这个精确例子并不要求每个相位都能被精确表示。
例题 2.7.6
(不在网格上的样本)
令 、。 这些幂说明阶为 。取 。对 ,,所以 ,,它并不恰好等于 。辗转相除得 、、,所以连分数为 ,渐近分数为 。分母至多为 的有 。检验 、、,通过检验的最小分母是 。最后 ,且 、。
例题 2.7.7
(分母已经缩小的样本)
仍取 、、,并令 。此时 ,所以 ,。由于 ,连分数为 ,渐近分数为 、、。分母至多为 的有 和 ,而 、 模 都不是 。检验把两者都拒绝,这是正确的:,所以约简后的相位是 ,其分母 是 的真因子。这次运行被舍弃并重做。
从周期得到因数
命题 2.7.8
(由 1 的非平凡平方根得到因数)
设 是偶周期,即 ,并令 。若 且 ,则 ,并且
证明
(消去互素因子)
事实上,,所以 整除 ,但不整除其中任一因子。若 ,在模 下消去该因子便得到 ,与假设矛盾;另一最大公因数同理大于 1。两者都不等于 。因此任一最大公因数都给出非平凡因数。这个判据适用于任何满足上述非平凡平方根检验的已验证偶周期;不必先证明它最小。
证明透视
平方根检验用在哪里
同余式 来自 是偶周期。条件 与 说明 既不整除 也不整除 ,却整除它们的乘积,因此 的因子分散在两个因子之中。唯一不显然的一步是消去:与 互素的因子在模 下可逆,这把“最大公因数为 1”变成被禁止的同余式。对合数 ,除 外还有 的其他平方根;模 时是 和 ,恰好是能产生因数的那些值。这里没有用到 的最小性。
当 、 时,阶 4 给出 ,因此 、。通过检验的周期 8 则给出 ,所以不通过平方根检验,也不能给出因数。奇数阶、平凡平方根、不准确的相位样本及与 不互素的 都需要另行处理或重复。这个计算没有证明随机选取底数的成功概率,也没有证明完整的因数分解复杂度定理。
练习与解答
快速检查
(如果 、,约简 后的分母是多少?)
解答 · 答案
,所以分母是 。
快速检查
(为什么单凭 不能证明 是阶?)
解答 · 答案
阶的每个正整数倍数也是周期;例如底数 模 时, 就是一例。
快速检查
(对 、,检验 并计算所得的最大公因数。)
解答 · 答案
,而 给出 和 。
快速检查
(还需要什么附加条件,约简后的相位分母才等于 ?)
解答 · 答案
。相位还必须被准确恢复,结论才适用于测得的分母。