僅僅製備疊加態並不能帶來量子加速:測量只返回一個結果。算法必須利用干涉,使有用結果的概率增大;複雜度結論也必須明確輸入模型和計數的資源。
量子傅立葉變換
定義 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 迭代後的成功概率是多少?)
解答 · 答案
此時 ,概率為 ;第二次迭代已經越過最佳位置。