• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      精確Grover 量子搜索算法概述

      2022-05-28 06:16:34李冠中李綠周
      關(guān)鍵詞:黑盒下界無(wú)序

      李冠中,李綠周

      (中山大學(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ì)精確量子搜索算法給出了較為完整的概述。

      猜你喜歡
      黑盒下界無(wú)序
      一種基于局部平均有限差分的黑盒對(duì)抗攻擊方法
      車(chē)身無(wú)序堆疊零件自動(dòng)抓取系統(tǒng)
      Lower bound estimation of the maximum allowable initial error and its numerical calculation
      張博庭:煤電不能再這么無(wú)序發(fā)展下去了
      能源(2017年11期)2017-12-13 08:12:30
      高速路上右行規(guī)則與無(wú)序行駛規(guī)則的比較研究
      無(wú)序體系中的國(guó)際秩序
      矩陣Hadamard積的上下界序列
      最大度為10的邊染色臨界圖邊數(shù)的新下界
      常維碼的一個(gè)構(gòu)造性下界
      会泽县| 兴城市| 南平市| 德清县| 美姑县| 犍为县| 修水县| 宁陕县| 临西县| 镇赉县| 阿尔山市| 赫章县| 靖宇县| 竹山县| 专栏| 宁武县| 衡东县| 东兴市| 合山市| 北碚区| 钟山县| 五指山市| 若尔盖县| 泾阳县| 盐源县| 龙州县| 郴州市| 清新县| 信阳市| 合肥市| 新巴尔虎左旗| 双牌县| 定南县| 射阳县| 宁河县| 嘉鱼县| 富阳市| 榆中县| 赣州市| 正定县| 登封市|