謝旭明，段隆振，邱桃榮，康小麗

1(南昌大學 信息工程學院，南昌 330031) 2(南昌大學 圖書館，南昌 330031)

1 引 言

量子計算最早由Feynman[1]提出，此后不少學者提出了不同的量子算法.其中Shor[2]提出的大數(shù)質(zhì)分解量子算法和Grover[3]提出的無序數(shù)據(jù)庫量子搜索算法是最為經(jīng)典的兩個量子算法.Shor提出的大數(shù)質(zhì)分解量子算法相對于經(jīng)典算法實現(xiàn)了多項式級別的加速，但這個算法目前看來只能針對這類特定的問題；而Grover算法，因其解決的搜索問題可應用于許多機器學習算法中，得到了更為廣泛的關注和研究.

Grover算法是由L.K.Grover于1996年提出的.自提出以來，許多學者對其進行了進一步的研究，主要方面有：經(jīng)典計算下的難點問題、與機器學習相結(jié)合、以及算法自身的改進等.

Grover算法能夠處理以前難以解決的或加速需要大量計算的問題.孫國棟等人[4]將Grover算法應用到求根問題上，將求根問題的計算復雜度降低到原來的平方根.朱皖寧等[5]用Grover算法來識別Weblog中的用戶，相較于經(jīng)典計算，改進策略將搜索的查詢復雜度進行了二次加速.Indranil等[6]先將Grover算法的黑盒添加上動態(tài)選擇的功能，然后將改進算法用在推薦系統(tǒng)上.楊婕等[7]先將Grover算法與量子計數(shù)相結(jié)合，提出一種量子黑箱線路設計方案，然后將提出的方案應用于BLAKE算法的安全性分析中.

Grover算法，因其適用性，也可以用來改進很多機器學習算法的一些子程序，進而達到對原機器學習加速的效果.阮越等[8]將Grover算法引入到主成分分析算法中，設計了一種人臉編碼方案，進一步壓縮了降維處理后的特征空間.Yu等[9]，通過改進Grover算法來求解頻繁項集，實現(xiàn)了關聯(lián)規(guī)則挖掘的量子化.He等人[10]將經(jīng)典量子搜索黑盒改進為可以同時接受候選特征集及特征索引的黑盒，實現(xiàn)了特征抽取的量子化.周曉彥等人[11]借助量子搜索的思想對k-means算法進行量子化處理.

為了提高Grover算法的成功概率，不少學者也進行了相關的研究.這方面的研究主要集中在改進算子的相位旋轉(zhuǎn)角度.Li等[12]將相位角度改為0.1π，Zhong等[13]將相位角度改為1.018，Younes等[14]將相位角度改為1.92684π.這些改進策略使成功概率均獲得了提升.

在已見的Grover算法改進策略中，大多數(shù)是圍繞著改變算子的相位角度來進行的，但這些策略的一個致命缺點就是迭代次數(shù)不好確定.為解決這個問題，本文提出一種搜索空間自適應的量子搜索算法，擬在不改變迭代次數(shù)計算方法的基礎上，提高算法的成功概率.

2 Grover算法及其缺陷

2.1 Grover算法

Grover算法首先要準備n個|0>態(tài)的量子位，并通過n個Hadamard門構(gòu)造一個n量子位的等權重疊加態(tài)，然后以一定的次數(shù)將U算子作用于n量子位，最后測量這n個量子位.U算子包含兩個子算子Ua和Us：Ua算子又稱為量子黑盒，用于實現(xiàn)目標分量的相位取反；Us算子用于實現(xiàn)目標分量取反后疊加態(tài)的均值翻轉(zhuǎn).

Grover算法的運算過程在Hilbert空間中的表示如圖1所示.

圖1 Grover算法在Hilbert空間的表示Fig.1 Grover algorithm in Hilbert space

圖1中，目標分量值平面α由X軸與Z軸確定.Y軸表示α的垂直分量.s0是初始的等權重疊加態(tài)，s′為經(jīng)過Ua算子作用后的疊加態(tài)，s1為s′經(jīng)過Us算子作用后的疊加態(tài)，sT為T次迭代后的疊加態(tài).Grover算法的基本思想就是將與目標分量值平面α夾角較大的疊加態(tài)s0經(jīng)過一系列的幺正變換轉(zhuǎn)變?yōu)榕cα夾角較小的sT，此時目標分量的概率幅值較大.

設Tpft是理論上算子的迭代次數(shù)，這個值大部分情況下是小數(shù)，在現(xiàn)實中是不可能出現(xiàn)小數(shù)次的迭代次數(shù)的.而T是算法的實際迭代次數(shù)，是一個正整數(shù)，是對Tpft四舍五入取整后的值.T的表達式如公式(1)所示，其中round()為四舍五入取整函數(shù).Tpft的表達式如式(2)所示.

T=round(Tpft)

(1)

(2)

(3)

2.2 Grover算法的缺陷

結(jié)合式(1)-式(3)，成功概率P與目標分量λ的關系可以繪出圖2.

2005年，“北京DRC工業(yè)設計創(chuàng)意產(chǎn)業(yè)基地”規(guī)劃投建，為中國工業(yè)設計帶來全新的元素與升級。基地中搭建起“逆向工程實驗室”“3D打印體驗館”“設計博物館”等一系列創(chuàng)意空間；同年，“光華龍騰獎.中國設計十大杰出青年”評選啟動，為中國設計行業(yè)發(fā)掘中國力量；2006年，“中國設計紅星獎”設立，助力中國設計走出國門，在國際化征途中完成設計服務業(yè)和制造業(yè)的融合與蛻變；2008年，以北京奧運為契機，“奧運設計”的理念走進社區(qū)，走進人們生活，這一年，深圳成為全球第六個世界“設計之都”。

圖2 經(jīng)典Grover算法成功概率Fig.2 Success rate of the classic Grover algorithm

3 改進的量子搜索算法

當目標分量占比很小的時候，量子搜索算法總能以較高的概率得到目標分量；當目標分量占比較大的時候，算法得到目標分量的概率就不那么高.因此，該研究只需要改進目標分量占比較大的情況.本文擬采用擴大搜索空間的方式來提升目標分量的概率幅.但隨著搜索空間的增大，算法的計算復雜度也會提升，因此，我們必須將搜索空間在合適的范圍內(nèi)擴大.下面我們先提出幾個定理，再給出具體的改進策略.

3.1 定理證明

證畢.

證畢.

證明：結(jié)合定理1和定理2，很容易得出.

證畢.

定理3.當T越大時，目標分量概率的極小值越大.

證畢.

證畢.

3.2 改進策略

(4)

4 算法效率分析

該研究將提出算法與經(jīng)典Grover算法的效率進行了比較.比較結(jié)果如圖3所示.

圖3 成功概率比較圖Fig.3 Comparison of success rates

5 結(jié) 語

通過自適應地改變不同目標分量占比時的搜索空間，本文整體上實現(xiàn)了成功概率的提升.該策略可以沿用經(jīng)典Grover算法的思路來求解算子的迭代次數(shù)，避免了以往通過改變算子旋轉(zhuǎn)相位策略的缺陷，在實施方面有更好的可操作性.