朱皖寧,陳漢武

(1.金陵科技學院軟件工程學院,江蘇南京 211199；2.東南大學計算機科學與工程學院,江蘇南京210096;3.東南大學計算機網(wǎng)絡和信息集成教育部重點實驗室,江蘇南京210096)

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

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

(1.金陵科技學院軟件工程學院,江蘇南京 211199；2.東南大學計算機科學與工程學院,江蘇南京210096;3.東南大學計算機網(wǎng)絡和信息集成教育部重點實驗室,江蘇南京210096)

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

Grover搜索算法；相位正負性；自動控制

1 引言

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

2 準備知識

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

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

(1)

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

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

(2)

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

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

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

(3)

(4)

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

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

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

(5)

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

(6)

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

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

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

4 小結

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

[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].電子學報,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].計算機學報,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)絡的Grover路由算法研究[J].浙江工業(yè)大學學報,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].北京工業(yè)大學學報,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年生,安徽淮南人,博士,主要研究領域為量子計算與量子可逆邏輯綜合.

E-mail:granny025@163.com

陳漢武 男,1955年生,江蘇南京人,博士,教授,主要研究領域為量子信息與量子計算技術.

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；責任編輯：梅志強

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

TP387;TN911.73

A

0372-2112 (2016)12-2975-06

??學報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.12.023