Grover 搜尋從均勻疊加態出發,但其旋轉原理適用於更一般的製備過程。如果一個算法已經以已知的非零概率 產生所需結果,振幅放大可以透過分別關於所需子空間和已製備狀態作反射,提高成功概率。代價是必須能夠相干地實現製備操作及其逆操作,而不僅僅是把它當作黑箱來抽樣。
製備好分量和壞分量
定義 2.8.1
(好分量與壞分量)
設 是有限維寄存器上的酉算子,令 。設 為到好子空間的正交投影。暫且假設 ,其中
歸一化向量 互相正交。取滿足 的 ,則
定義 2.8.2
(相位預言機、製備反射與迭代)
定義相位預言機 和關於已製備狀態的反射 。後者實現為 。一次放大迭代是 :最右邊的預言機先作用。這裏 表示整個寄存器的全零初始基態。
概念視角幾何
兩次反射合成一次旋轉
同一個迭代有平面幾何的描述。在 生成的平面中,預言機 固定 並把 變號,所以它是關於過 的直線的反射; 則是關於過 的直線的反射。這兩條直線的夾角為 ,而關於夾角為 的兩條直線作兩次反射,合成為轉角 的旋轉。因此每次迭代把狀態向 轉動 ,而 起初與 的夾角為 。下一節的矩陣把這幅圖像化為計算。
兩次反射為何產生旋轉
定理 2.8.3
(振幅放大公式)
經過整數 次迭代,
區分好子空間與其正交補的測量以概率 成功。
證明
(兩次反射合成旋轉)
兩個反射都保持 生成的平面不變。在此有序基下,簡記 、,
相乘得
它作用於 得到 。同樣的和角公式透過歸納法證明所述公式。 的係數平方即為成功概率。
證明透視
證明在哪裏用到各項假設
論證分三部分。第一,平面的不變性:由於 、, 把 變號並固定 ;而 留在平面內,因為 屬於該平面。這需要 ,正是它使 成為良定的標準正交對。第二,唯一不屬例行的一步是倍角化簡 、、,它把乘積化為旋轉矩陣。第三,歸納得以閉合,是因為轉角 的旋轉把 的角度增加 ,所以起始角 在 步後成為 。其中沒有任何近似;旋轉只作用於兩個係數,所以原來好投影內部的相對權重得以保留:在成功條件下,更細的計算基測量服從 的分佈。
例題 2.8.4
(一次迭代後必然成功)
假設
且 是好結果。那麼 ,所以 。一次迭代後的好振幅為 ,必然成功。在成功條件下, 和 的概率分別為 和 ,並不相等。好子空間內的分佈由狀態製備決定。
常見錯誤
(混淆 與 )
角 由 定義,而不是 。當 時,正確的角是 ,因為 ;若用 ,便得到錯誤的角和錯誤的成功概率。 次迭代後的成功概率是 ,一般只在 時等於 。
選擇迭代次數
當 已知時,取最接近 的非負整數 ;並列時任選。由於 ,目標數非負,而取整給出
成功概率至少為 。特別是當 很小時,這個值接近一。由於 ,此選擇滿足 。每次迭代各調用一次 、 和 ,並執行一次關於 的反射;初始製備還需要額外調用一次 。這些是理想相干操作;查詢次數不包括它們依賴具體問題的實現成本。
例題 2.8.5
(在八個項目中搜尋一個被標記的項目)
取 ,令 標記一個基態,則 、、,。於是 ,,規則選取 。記 ,有 ,所以
這高於保證的 。作為比較, 給出 , 給出約 ,所以 是最佳選擇。
例題 2.8.6
(並列情形:成功概率停在一半)
設 ,則 , 恰好位於 與 的正中間;規則兩者皆可。成功概率為 ,而 是 的奇數倍,所以對每個 其值都是 。保證值 取等號,而且無論迭代多少次都不能得到必然成功:狀態每次轉動 ,在此從不落在好方向上。
反例模式
更多迭代可能抵消改進
一個誘人的想法是:每多迭代一次,成功概率只會變好。若 ,則 。立即測量已製備狀態的成功概率為 。一次迭代後的成功概率反而為 。狀態已旋轉越過好方向。無限重複同一迭代不是單調改進的規則。
若 ,歸一化的 無定義,已製備狀態沒有好分量:僅憑這些反射無法創造該分量。若 ,初始測量已必然成功。這些端點情形必須與二維公式分開處理。
保證所依賴的假設
已知 才能選擇上述 ;成功概率未知時需要另一種策略和分析。預言機必須相干地施加正確相位,也必須確實能夠使用 。只從 的輸出產生獨立經典樣本,並不足以實現關於 的反射。此保證針對理想電路,計算預言機和製備的調用次數;不完美操作和識別好輸出的複雜度需要另外分析。
常見錯誤
(把關於 的反射當成關於 的反射)
算子 單獨使用時,是關於全零態的反射,而全零態一般並不是已製備狀態。關於 的反射是共軛形式 。漏掉 和 會得到另一個算子,旋轉公式對它並不成立。
這個一般結論包含均勻搜尋:取 ,令 標記 個基態中的 個,則 。只要能夠實現所需反射,它也允許非均勻製備態和任意好子空間。
練習與解答
快速檢查
(當 時,求 及兩次迭代後的成功概率。)
解答 · 答案
此時 ,且 :第二次迭代越過目標,因為一次迭代已經達到概率 。
快速檢查
(當 時,規則選取哪個 ?成功概率是多少?)
解答 · 答案
此時 ,,所以 ,取 。令 ,,所以成功概率為 ,高於保證的 。
快速檢查
(在第一個例子中,一次迭代後測得 的概率是多少?)
解答 · 答案
是 :以概率 到達好子空間,其中 的條件概率為 。
快速檢查
(為甚麼只獲得 的經典樣本分佈,不足以提供所述反射?)
解答 · 答案
構造 需要相干訪問 及其逆操作,包括經典樣本分佈不包含的相位資訊。