量子相关词汇搜索_英文_

量子相关词汇搜索_英文_ 第 22 卷第 4 期Vol . 22 ?. 4 原 子 与 分 子 物 理 学 报 2005 年 1 0 月 J OU RNAL O F A TOM IC AND MOL ECUL A R P H YSICS Oct . 2005 ?研究简报 ? () 文章编号 : 100020364 20050420774203 Ξ 量子相关词汇搜索 ΞΞ 11 ,22 红穆万军,游志胜,张 ( )1 . 四川大学物理科学与技术学院 ,成都 610065 ;2 . 四川大学计算机学院 ,成都 610064 摘 要 : 本文讨论了基于量子并行计算和叠加态原理的量子搜索算法 ,并结合概率论 ,给出了从无结构的 () () 海量数据 库中搜索相关词汇 组的方法 ,并说明该方法远远优越于经典搜索算法 。 关键词 :量子搜索 ;叠加态 ; 相关词汇 ; 概率论 中图分类号 : TP3 ;O4 文献标识码 :A Quantum search on relevant words 1 ,2 2 1M U Wan2jun, YOU Zhi2sheng, ZHAN G Ho ng ( 1 ,Depart ment of Physics Science and Technology , Sichuan U niversit y , Chengdu610065 , P. R. China ; )2 . Depart ment of Co mp uter Science , Sichuan U niversit y , Chengdu 610064 , P. R. China Abstract : The paper discusses quant um search algo rit hm based o n quant um parallelism and superpo sitio n state , and gives a co mp uting way acco rding to Grover’s search algo rit hm and p ro babilit y to search relevant ( wo rds f ro m a large volumes of unst ruct ured data , and t hen describes t he algo rit hm to be op timal co mparing ) wit h any classical algo rit hm. Key words : Q uant um search , Superpo sitio n state , Relevant wo rds , Pro bability states and p ro babilit y. 1 Introduct ion 1 ,3 Grover’s quant um search algo rit hmis o ne 2 Quantum search of t he mo st widely st udied wit h p resence of a large volumes of data because t he algo rit hm needs fewer Q uant um searching algo rit hm is created by queries t han any classical search . To a unst ruct ured exploiting quant um - mechanical effect s such as database of N reco rds , classical search may need ( ) superpo sitio n quant um parallelism and f ro m 1 to N queries —abo ut N/ 2 times o n average 4 interference . Acco rding to p rinciple of quant um (( ) ) o r O N, however , quant um search o nly needs O 1/ 2 mechanics , t he basic unit of quant um info r matio n is )( iterative . Many papers p ublished are almo st N ( ) quant um bit qubit of 0 o r 1 . In Pauli idea , we to use t he algo rit hms to search isolated wo rds o r σσmay use Pauli operato r and to fo r m Hadmard x z items. The paper will discuss quant um search of () o y Walsht ransfo r matio n : meaningf ul relevant wo rds wit h superpo sitio n of Ξ 收稿日期 :2004209228 ( ) 作者简介 :穆万军 1963 - ,男 ,讲师 ,在职博士生 ,从事物理教学和量子信息与计算机技术的研究 。ΞΞ 通讯联系人 :穆万军 , E2mail : muwj @263 . net 1 2 D^ = P^ - I^ 1 1 (σσ) H = + =x z 1 - 1 2 2 1 1 2 10 ( ) ω N ×N isP^ = w here mat rix of , , in Hilbert space suppo sing | 0〉= , | 1〉=N 0 1 1 1 of t wo dimensio ns , we have identit y mat rix of N × N . m ( ) () To let D^ Q^ operate to Eq. 2, we have 1 1 1 ( ( )1 H | 0〉> | 0〉+| 1〉=( )( )m m m 1 2 2 ΨΨ ( ) ( ) Ψ( )| 〉= | k , l D^ Q^ | 〉 3〉 m x x Notice t hat‚H?is bot h unitary t ransfo r matio n and( )( ) m m w here and l respectively rep resent s k x x co njugate t ransfo r matio n , and t hus it has bot h p ro babilit y of target state and ot her states by reversibilit y and scalabilit y. searching of m times w hen H operate respectively n2qubit state | [ 5 ] 1 n θ () using sin= and Eq. 3, If t he 00 0〉, we shall get a superpo sitio n of 2 N no n2quant um o r‚classical?states , i . e . , p ro babilit y of measuring t he target state app roaches 6 ( )n1 , t hen Ψ00 0〉H || 〉= ( )m = H ? H ? ? H | 00 0〉 ( )θ( )k 4 = sin 2 m + 1? 1 x 1 ( ( )? [ | 0〉+| 1〉? | 0〉+| 1〉 = () we o nly need O N operatio ns n 2 ) π H | 00 0〉+| 1〉] ( )5 m = N n 4 2 - 1 1 ( )| x 〉2 = w here square bracket s ‘[]’rep resent sto o btain ? n i = 0 2 integer . So , quant um search algo rit hm successf ully ‚0?o rof w here | x 〉 = | x x x x 〉st ring 0 1 2n - 1 finds t he unique target state f ro m a large database () ‚1?. Equatio n 2implies t he p resence of a kind of n () () N = 2 reco rdsby O N operatio ns. including massive parallelism in t he quant um state . We co uld If K element s satisf y t he p redicate , t hen n t hink t hat each of 2 quant um states co rrespo nd to π Nan item of info r matio n . Fo r instance , if searched )( m = 6 4 Kn ζdata | 〉is a state of superpo sitio n of 2 states , it s 7 queries suffice. p ro babilit y is : 1 Ψζ〈| 〉= 3 Quantum search on relevant words n 2 The idea of Grover’s algo rit hm is to devise a Web data Mining is to use co mp utatio nal mat rix to perfo r m iterative algo rit hm , namely , to techniques to search t he p rocess of large volumes of place register in a equal superpo sitio n of all states raw data o n t he Web. It s aim is to find co ntext2 () such as Eq. 2, and t hen selectively invert t he sensitive wo rds o r co ntext . However , a large p hase of t he target state : volumes of data of Inter net are mo stly irrelevant list ζ- | x 〉, | x 〉= | 〉 of document s. How to find t he wo rds f ro m a large O^ | x 〉= ζ| x 〉, | x 〉?| 〉 unst ruct ured database of Web ? The co ntext is and t hen perfo r m an inversio n abo ut average co mpo sed of relevant wo rds t hat can be fo r med by ( ) operatio n a number of times. The selective inversio n logic operatio n such as‚AND?and‚O R?of so me of t he target state follow s by t he inversio n abo ut wo rds. average step s t hat have t he effect of increasing t he We suppo se t hat o ne item of database can be amplit ude of t he target state and decreasing t he mapped o ne event of sample space w hich is t he set of all po ssible o utco mes fo r an event o r experiment . amplit ude of t he ot her states simultaneo usly : () () () So , using Eqs. 9, 10and 11,we o btain t he Acco rding to p ro babilit y , if t wo event s A and B result of searching relevant wo rds‚r hinitis t reat ment occurring simultaneo usly is independent , t heir joint met ho ds o r p reventive measures?by p ro babilities are : ()() () () P A AND B = P AB= P A3 P B. NN m = m 1 + m 2 , LJIf A and B is dependent , we have , operatio ns. () () ()P A AND B= P B3 P A| B ()() ()7 = P A3 P B| A 4 Concl usion ( ) Where P A | B is co nditio nal p ro babilit y w hich By co mpariso n , to search fo r a unique item in ( ) means t he seco nd o utco me Adependent upo n t he ( ) unst ruct ured database co ntaining N reco rds , ( ) ( ) first B . equatio n 8 is referred to ’Bayesian ’ classical algo rit hm may need f ro m 1 to N queries p ro babilit y , (( )depending o n inp ut , N / 2 o n average o r O N 40 ) N = operatio ns . suppo sing 2,using classical () () ()P A| B= P A AND B/ P B algo rit hm , co mp uter can ’t find a unique item in To t hree event s A ,B and C , we have bearable time . However , quant um co mp uter () ()P A AND B AND C= P ABC ( ) utilizing quant um search algo rit hm can get a ()( ) () ()8 = P CP B| CP A| BC 40 20 ( ) 2= 2operatio ns. As a unique target item by If o nly A o r B , t hat is , o nly o ne of t wo event s result of massive parallelism , quant um search happens , t he p ro babilit y wo uld be t he sum of t he algo rit hm is expo nentially f aster t han any classical t wo p ro babilities , algo rit hm Thro ugh associating t he quant um search algo rit hms wit h p ro babilit y , we get an algo rit hm of ()() () ()9 P A O R B= P A+ P B searching fo r significative relevant wo rds f ro m a Fo r example , w hen searching fo r t he relevant wo rds large volumes data . t reat ment met ho ds o r p reventive ‚ r hinitis Ref erences : we can describe it : r hinitis AND measures ?, 1 Grover L K. A fast quant um mechanical algorit hm for ( ( ) ( t reat ment AND met ho dsO R p reventive AND estimating t he median R . Technical Re port , quant2p h/ ) ) measures. 9607024 , 1996 . Assuming a large unst ruct ured database 2 Grover L K. Quant um teleco m p utatio n R . Technical includes N wo rds , and existing M items co ntain Report , quant2p h/ 9704012 , 1997 . ( ) ‚r hinitis ?, acco rding to Eq. 6 , we may get3 Shor P W. Scheme for reducin g deco herence in quant um N co mp uter memoryJ . Ph ys. Rev. , 1995 ,A52 : R2493 . p ro babilit y of target wo rds app roaches 1 by M 4 Shor P W. Fault 2tolerant quant um co mp utatio n C . In : operatio ns. In M items , if existing K items Proceedings of t he 37t h Annual Symposium o n K , by Eqs. ‚t reat ment?and L items‚met ho ds?in Foundatio ns of Co mp uter Science. I EEE Co mp uter () () 6and 8, we o nly need iterative Societ y Press , 1996 . 56 . 5 Nielso n M A , Chuan g I L . Quant um co mp utatio n and NN M K ( )m 1 ,= 10 quant um informatio n M . Cambrid ge : Cambridge M LK L U niversit y Press , 2000 . we get t hat t he p ro babilit y of t he relevant wo rds 6 Grover L . A fast quant um mechanical algorit hm for ‚r hinitis t reat ment met ho ds? app roaches 1 . The database search C . Proceedin gs of t he 28t h Annual same reaso ns , if existing I items‚p reventive?in M ACM Symposium o n Theory of Co mp uting , 1996 . 212 . I satisf y t he co nditio ns , and J items‚measures?in 7 Bo yer M , Brassard G , Hoyer P , et al . Tight bounds o n we have quant um searchingJ . Fort sch. Ph ys. ,1998 , 46 :493 . ()卷终 NN M I ( )m 2 ,= 11 M JI J