迭代次數(shù)自適應(yīng)的Grover算法

朱皖寧,陳漢武

(1.金陵科技學(xué)院軟件工程學(xué)院,江蘇南京 211199；2.東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,江蘇南京210096;3.東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室,江蘇南京210096)

迭代次數(shù)自適應(yīng)的Grover算法

朱皖寧1,2,陳漢武2,3

(1.金陵科技學(xué)院軟件工程學(xué)院,江蘇南京 211199；2.東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,江蘇南京210096;3.東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室,江蘇南京210096)

本文提出了利用相位門自動控制Grover搜索算法迭代次數(shù)的算法.Grover搜索算法最終得到目標(biāo)分量的概率非常依賴于酉算子迭代的次數(shù).迭代次數(shù)的計(jì)算依賴于目標(biāo)分量的數(shù)量.因此當(dāng)目標(biāo)分量數(shù)未知時(shí),該方法無法以高概率測量到目標(biāo)分量.在以往的解決方案中需要較高的Oracle查詢復(fù)雜度才能以一定概率得到目標(biāo)分量的數(shù)量.本文提出了一種通過判斷疊加態(tài)相位正負(fù)性,可自動控制Grover搜索算法迭代次數(shù)的方法.只需要添加一個(gè)判斷相位的門電路,僅增加一次Oracle查詢次數(shù)就可以精確的在最優(yōu)迭代次數(shù)時(shí)停止Grover搜索算法,在搜索空間較小時(shí)可比原算法有更大的概率得到目標(biāo)分量.

Grover搜索算法；相位正負(fù)性；自動控制

1 引言

本文提出了一種基于判定X基下(|±〉={|0〉±|1〉}) 特定分量相位的正負(fù)性的新Grover算法.新算法只需要多一個(gè)可逆門和一次Oracle調(diào)用,就可以在目標(biāo)分量未知時(shí)仍然可以以最高的概率測量出目標(biāo)分量.

2 準(zhǔn)備知識

Grover搜索算法是由一組酉算子的迭代運(yùn)算組成.可以簡單的由下圖表示[9]:

當(dāng)n個(gè)量子比特初態(tài)|0〉?n經(jīng)過門H?n后變成n量子均勻疊加態(tài),具體變換過程由如下公式表示:

(1)

其中N=2n.令|s〉表示初態(tài)的均勻疊加態(tài).U算子由一個(gè)Oracle決定解(即用一個(gè)函數(shù)可以表達(dá)出解)和一個(gè)Grover均值反演算子來增加解的概率.

如圖2所示的Oracle算子令所求目標(biāo)分量相位翻轉(zhuǎn):Oracle=I-2|φ〉〈φ|；Grover均值反演算子通過簡單計(jì)算可以得到如下表示:

(2)

3 迭代次數(shù)自適應(yīng)的Grover搜索算法

每次進(jìn)行Grover算子迭代后,目標(biāo)分量的幅度都會發(fā)生變化.且可以證明運(yùn)行最佳迭代次數(shù),目標(biāo)分量的幅度都會增加,而目標(biāo)分量的幅度直接影響最終測量出結(jié)果的概率.因此可以通過判斷目標(biāo)分量幅度是否已經(jīng)最大化,控制Grover搜索算法的迭代次數(shù).

定理2(均值反演定理) 經(jīng)過均值反演算子作用,疊加態(tài)所有分量的相位之和首次變?yōu)樨?fù)值時(shí)目標(biāo)分量的概率幅首次達(dá)到最大值.

(3)

(4)

定理3(相位和定理) 疊加態(tài)分量Z基下相位和正負(fù)性由X基下的|++…+〉分量相位正負(fù)性所決定.

證明:這個(gè)結(jié)果可以很容易的通過變換基底獲得.假設(shè)初始基底為Z基,即{|0〉,|1〉}基.那么一個(gè)n量子比特的疊加態(tài)總是可以表示為:

(α00|0〉+α01|1〉)(α10|0〉+α11|1〉)… (α(n-1)0|0〉+α(n-1)1|1〉)

(5)

現(xiàn)在將Z基轉(zhuǎn)化為X基,即{|+〉,|-〉}基,某一量子比特的轉(zhuǎn)換公式可如下表示:

(6)

由于相位正負(fù)性可以估測[22,23],所以使用相位檢測門Phase門,輸入為需要進(jìn)行相位判斷的疊加態(tài)和一個(gè)輔助比特|ψ〉?|β〉.經(jīng)過Phase門后,疊加態(tài)|ψ〉不產(chǎn)生變化.輔助位根據(jù)疊加態(tài)在X基下|+ + …+〉分量前相位φ|+ + …+ 〉正負(fù)性進(jìn)行運(yùn)算:當(dāng)φ|+ + …+〉為正時(shí)不做任何操作,否則翻轉(zhuǎn)控制端.顯然此電路為可逆電路.Phase門可以由圖3所示的線路所表示:

將這個(gè)電路加入到Grover算法電路的U算子中,令|ψ〉為經(jīng)過Oracle算子的疊加態(tài),令|β〉=|0〉.

如圖4所示,每迭代一次U算子時(shí),都在運(yùn)行Oracle算子后對輔助位進(jìn)行一次測量再決定是否進(jìn)行Grover均值反演算子的計(jì)算.當(dāng)測量結(jié)果為|0〉時(shí)繼續(xù)進(jìn)行算法迭代,當(dāng)測量結(jié)果為|1〉時(shí)結(jié)束算法.由此嵌入Phase門后的Grover搜索算法可以自適應(yīng)的控制U算子迭代次數(shù).

4 小結(jié)

本文提出了一種在M未知時(shí)運(yùn)行Grover算法的解決方案.利用判斷經(jīng)過Oracle后疊加態(tài)相位和的正負(fù)性,自動控制Grover算法酉算子的迭代次數(shù),可以精確在目標(biāo)分量概率達(dá)到最大值時(shí)停止算法,并且只加入了一個(gè)進(jìn)行相位判斷的門電路,只增加一次Oracle查詢次數(shù).不僅如此迭代次數(shù)自適應(yīng)的Grover算法在搜索空間較小時(shí)會獲得更高的概率測量到目標(biāo)分量.在近幾年來有許多學(xué)者對Grover算法進(jìn)行了改進(jìn),增加測量出目標(biāo)分量的概率并減少Oracle調(diào)用的次數(shù).這些改進(jìn)算法并沒有改動均值反演算子這個(gè)核心,因此本文所述的方法均可以用于這些改進(jìn)算法.

[1]Shor P W.Algorithms for quantum computation:discrete logarithms and factoring[A].Proceedings of the 35th Annual Symposium on foundations of Computer Science[C].Santa Fe,NM:IEEE,1994.124-134.

[2]GroverL K.A fast quantum mechanical algorithm for database search[A].Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing[C].Philadelphia,USA:ACM,1996.212-219.

[3]Grover L K.Quantum mechanics helps in searching for a needle in a haystack[J].Physical Review Letters,1997,79(2):325-328.

[4]Grover L K.Quantum computers can search rapidly by using almost any transformation[J].Physical Review Letters,1998,80(19):4329-4332.

[5]Long G L,Li Y S,Zhang W L,et al.Dominant gate imperfection in Grover’s quantum search algorithm[J].Physical Review A,2000,61(4):042305.

[6]Biron D,Biham O,Biham E,et al.Generalized Grover search algorithm for arbitrary initial amplitude distribution[A].Quantum Computing and Quantum Communications[C].Palm Springs,CA:Springer Berlin Heidelberg,1999.140-147.

[7]Chuang I L,Gershenfeld N,Kubinec M.Experimental implementation of fast quantum searching[J].Physical Review Letters,1998,80(15):3408-3411.

[8]Boyer M,Brassard G,H?yer P,et al.Tight bounds on quantum searching[OL].arXiv Preprint Quant-ph/9605034,1996.

[9]Michael A Nielsen,Isaac L Chuang.Quantum Computation and Quantum Information[M].British:Cambridge University Press,2000.240-243.

[10]Daniel Reitzner,Daniel Nagaj,Vladimir Buzek.Quantum walks[J].Acta Physica Slovaca,2011,61(6):603-725.

[11]金文梁,陳向東.相位不匹配的量子搜索算法[J].電子學(xué)報(bào),2012,40(1):189-192. Jin Wenliang,Chen Xiangdong.Phase-unmatched quantum search algorithm[J].Acta Electronica Sinica,2012,40(1):189-192.( in Chinese)

[12]Zalka Christof.Using Grover’s quantum algorithm for searching actual databases[J].Physical Review A,2000,62(5):052305-052301.

[13]Yamashita S.How to utilize a Grover search in general paogramming[J].Laser Physics,2006,16(4):730-734.

[14]阮越,陳漢武,劉志昊,等.量子主成分分析算法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(3):666-676. Ruan Yue,Chen Hanwu,Liu Zhihao.Quantum principal component analysis algorithm[J].Chinese Journal of Computers,2014,37(3):666-676.(in Chinese)

[15]彭宏,荊晶.無線自組織量子通信網(wǎng)絡(luò)的Grover路由算法研究[J].浙江工業(yè)大學(xué)學(xué)報(bào),2014,42(6):612-615. Peng Hong,Jing Jing.Research on routing algorithm of Grover for wireless ad hoc quantum communication network[J].Journal of Zhejiang University of Technology,2014,42(6):612-615.(in Chinese)

[16]孫國棟,蘇盛輝,徐茂智.求根問題的量子計(jì)算算法[J].北京工業(yè)大學(xué)學(xué)報(bào),2015,41(3):366-371. Sun Guodong,Su Shenghui,Xu Maozhi.Quantum mechanical algorithms for solving root finding problem[J].Journal of Beijing University of Technology,2015,41(3):366-371.( in Chinese)

[17]Shenvi N,Kempe J,Whaley R B.A quantum random walk search algorithm[J].Physical Review A,2003,67(5):052307.

[18]Aaronson S,Ambainis A.Quantum search of spatial regions[A].Proceedings of 44th Annual IEEE Symposium on Foundations of Computer Science[C].MA,USA:IEEE,2003.200-209.

[19]Ambainis A,Kempe J,Rivosh A.Coins make quantum walks faster[A].Proceedings of 16th ACM-SIAM SODA[C].British Columbia,Canada:ACM,2005.1099-1108.

[20]Ambainis A.Quantum walk algorithm for element distinctness[A].Proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS’04)[C].Rome,Italy:IEEE,2004.22-31.

[21]Childs A M,Eisenberg J M.Quantum algorithms for subset finding[J].Quantum Information and Computation,2005,5(7):593-604.

[22]Dorner U,Demkowicz-Dobrzanski R,Smith B J,et al.Optimal quantum phase estimation[J].Physical Review Letters,2009,102(4):040403.

[23]Hradil Z.Phase measurement in quantum optics[J].Quantum Optics:Journal of the European Optical Society Part B,1992,4(2):93-110.

朱皖寧 男,1983年生,安徽淮南人,博士,主要研究領(lǐng)域?yàn)榱孔佑?jì)算與量子可逆邏輯綜合.

E-mail:granny025@163.com

陳漢武 男,1955年生,江蘇南京人,博士,教授,主要研究領(lǐng)域?yàn)榱孔有畔⑴c量子計(jì)算技術(shù).

E-mail:hanwu-chen@163.com

Grover Auto-Control Searching Algorithm

ZHU Wan-ning1,2,CHEN Han-wu2,3

(1.DepartmentofSoftwareEngineering,JinlingInstituteofTechnology,Nanjing,Jiangsu211199,China; 2.DepartmentofComputerScienceandEngineering,SoutheastUniversity,Nanjing,Jiangsu210096,China; 3.KeyLaboratoryofComputerNetworkandInformationIntegrationofMinistryofEducation,SoutheastUniversity,Nanjing,Jiangsu210096,China)

This paper presents an improved Grover searching algorithm which can automatically control the iterative processing when the number of target states is unknown.The probability of success of Grover searching algorithm depends on the number of iteration times and the number of the time of iterations relies on the number of target states.Therefore,it is hard to get the target state with high probability when the number of target states is unknown.To this question,the time complexity of conventional solution is high and the answer is non-deterministic.This paper shows an improved Grover searching algorithm,which is based on the sign for the phases of superposition state.Compared to existing research results,this algorithm can always stop the Grover iterations when the number of iteration times is optimal by the cost where just one more gate,and one more time Oracle call are needed to judge the sign of phase.

Grover searching algorithm;sign of phase;auto-control

2015-03-10；

2016-05-10；責(zé)任編輯：梅志強(qiáng)

國家自然科學(xué)基金(No.61170321，No. 61502101)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(No.20110092110024);江蘇省自然科學(xué)基金(No.BK20140651);金陵科技學(xué)院高層次人才科研啟動基金(No.jit-b-201624)

TP387;TN911.73

A

0372-2112 (2016)12-2975-06

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.12.023