尋階電路不會直接列印出階。它可以產生接近某個分數的測量結果,而該分數的最簡分母整除階。經典後處理必須恢復候選值、檢驗其含義,有時還要捨棄結果。當候選值用於分解因數時,區分週期與最小週期尤其重要。
作為特徵相位的階
定義 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 則給出 ,所以不通過平方根檢驗,也不能給出因數。奇數階、平凡平方根、不準確的相位樣本及與 不互質的 都需要另行處理或重複。這個計算沒有證明隨機選取底數的成功概率,也沒有證明完整的因數分解複雜度定理。
練習與解答
快速檢查
(如果 、,約簡 後的分母是多少?)
解答 · 答案
,所以分母是 。
快速檢查
(為甚麼單憑 不能證明 是階?)
解答 · 答案
階的每個正整數倍數也是週期;例如底數 模 時, 就是一例。
快速檢查
(對 、,檢驗 並計算所得的最大公因數。)
解答 · 答案
,而 給出 和 。
快速檢查
(還需要甚麼附加條件,約簡後的相位分母才等於 ?)
解答 · 答案
。相位還必須被準確恢復,結論才適用於測得的分母。