精確Grover 量子搜索算法概述

李冠中，李綠周

(中山大學(xué)計(jì)算機(jī)學(xué)院 廣州 510006)

求解無(wú)序數(shù)據(jù)庫(kù)搜索問(wèn)題的Grover 量子搜索算法[1]于1996 年被提出，相對(duì)于經(jīng)典算法有平方級(jí)別的加速。自問(wèn)世以來(lái)，得到廣泛應(yīng)用，如被用于求解最小值查找問(wèn)題[2]、串匹配問(wèn)題[3]、量子動(dòng)態(tài)規(guī)劃[4]及計(jì)算幾何問(wèn)題[5]。不僅如此，針對(duì)Grover算法本身的擴(kuò)展也不少，如量子振幅放大[6]、圖上量子游走搜索[7]、不動(dòng)點(diǎn)量子搜索[8-9]及本文要介紹的精確Grover 量子搜索算法[6,10-11]。

1 原始Grover 算法及其缺陷

無(wú)序數(shù)據(jù)庫(kù)搜索問(wèn)題可以抽象地描述如下，在大小為N=2n的 無(wú)序數(shù)據(jù)庫(kù)中，有M個(gè)元素是符合要求的，這些目標(biāo)元素通過(guò)一個(gè)函數(shù)f:{0,1,···,N?1}→{0,1}來(lái) 標(biāo)識(shí)：若編號(hào)為x的元素為目標(biāo)元素，那么f(x)=1； 否則，f(x)=0。假設(shè)有一個(gè)可以識(shí)別搜索問(wèn)題目標(biāo)元素的黑盒：要判斷編號(hào)為x的 元素是否為目標(biāo)元素，只需要將編號(hào)x輸入黑盒，它就會(huì)輸出f(x)的值?，F(xiàn)在希望以盡可能少的黑盒調(diào)用次數(shù)(稱(chēng)之為查詢(xún)復(fù)雜性)，找出一個(gè)目標(biāo)元素。

在量子計(jì)算中，實(shí)現(xiàn)函數(shù)f(x)的黑盒的作用效果是一個(gè)酉操作Of，其在計(jì)算基態(tài)上的作用效果為：

2 精確Grover 量子搜索算法

2.1 大步小步

2.2 共軛旋轉(zhuǎn)

2.3 三維旋轉(zhuǎn)

這一方法[11]的思路為：把G(?,?)在 正交基 |A〉和|B〉下的二維酉矩陣對(duì)應(yīng)到相應(yīng)Bloch 球中的三維旋轉(zhuǎn)，再通過(guò)選取適當(dāng)?shù)慕嵌??和旋轉(zhuǎn)次數(shù)k，使得Gk(?,?)|ψ〉在 該Bloch 球面上與 |B〉重合。

具體來(lái)說(shuō)，由于任意二維酉矩陣都可以寫(xiě)成下式右邊的形式，因此令

由 于 初 態(tài) |ψ〉在Bloch 球 中 對(duì) 應(yīng) 的 向 量 為s:=[sin(2θ),0,?cos(2θ)]， 而算法最終欲得的 |B〉對(duì)應(yīng)的向量為t:=[0,0,1]， 故 〈n|s〉=〈n|t〉 。 這說(shuō)明s和t在Bloch 球面以n為軸的同一個(gè)的圓上，所以確實(shí)可以通過(guò)繞固定軸n進(jìn)行多次旋轉(zhuǎn)，把s轉(zhuǎn) 到t。為了確定參數(shù) ?和旋轉(zhuǎn)次數(shù)k， 記r為s和t在n上的投影，如圖1 所示，解析幾何計(jì)算表明s?r和t?r之間的角度為 ω=π?2β。根據(jù)之前的推導(dǎo)，每作用一次G(?,?)相 當(dāng)于繞轉(zhuǎn)軸n旋 轉(zhuǎn) α =4β， 而 ω是所希望的總旋轉(zhuǎn)角度，因此令ω =kα 可以求出 ? 與k應(yīng)該滿(mǎn)足關(guān)系式：

圖1 在{ |A〉,|B〉}的 Bloch 球中，G (?,?)的多次作用相當(dāng)于把初態(tài) s 繞 轉(zhuǎn)軸 n旋 轉(zhuǎn)到目標(biāo)元素的均勻疊加態(tài)t

容易驗(yàn)證，圖2 和圖3 分別展示了S f(φ)和Sψ(?)的電路實(shí)現(xiàn)，其中最后一行為輔助qubit。注意到S f(φ) 需 要調(diào)用兩次黑盒Of，因此表1 中后兩種方法的黑盒調(diào)用次數(shù)是原始Grover 算法的兩倍，不過(guò)這并不影響平方加速的數(shù)量級(jí)。

表1 3 種精確Grover 量子搜索算法

圖2 S f(φ)的 電路實(shí)現(xiàn)，其中Of|x〉|b〉=|x〉|b⊕f(x)〉

圖3 S ψ(?)的電路實(shí)現(xiàn)

3 精確量子搜索的查詢(xún)下界

3.1 目標(biāo)元素占比未知時(shí)的查詢(xún)下界

3.2 目標(biāo)元素占比已知時(shí)的查詢(xún)下界

在目標(biāo)元素的占比已知的情況下，利用文獻(xiàn)[14]的quantum angle 方法，并把它直接地?cái)U(kuò)展到多個(gè)目標(biāo)元素的情形(即文獻(xiàn)[15]文末提及的選取?N/M」個(gè)“不相交”數(shù)據(jù)庫(kù)的思路)，可以證得精確量子搜索的查詢(xún)下界為

4 結(jié) 束 語(yǔ)

本文梳理了3 種精確Grover 量子搜索算法，給出了算法流程、參數(shù)設(shè)置以及背后的幾何直觀，并指出它們都依賴(lài)于目標(biāo)元素的占比，由此為出發(fā)點(diǎn)，說(shuō)明了算法的最優(yōu)性：對(duì)于目標(biāo)元素占比已知的情況，3 種精確Grover 量子搜索算法已經(jīng)達(dá)到最優(yōu)；而對(duì)于目標(biāo)元素占比未知的情形，精確量子搜索算法相比經(jīng)典算法沒(méi)有加速。因此本文對(duì)精確量子搜索算法給出了較為完整的概述。