Thequantumsearchalgorithm

1、1The quantum search algorithmGrovers Algorithm in 1996報(bào)告人:莊額碩2A possible problemn假設(shè)有N 個(gè)事物,編號(hào)分別為1,2,3,N.其中有M 個(gè)事物是我們想要的.n現(xiàn)在我們要在這N 個(gè)事物之中挑取一個(gè)我們想要的,而事先並不知道哪些編號(hào)的事物是我們想要的.3The oraclen假設(shè)存在一個(gè)黑盒子(black box)可以很快的告知我們所選的事物是否是我們所要的.n我們用function f 來(lái)代表這個(gè)黑盒子,若所選的事物是我們要的則回傳1,反之回傳0n例:若編號(hào)x 的事物是我們要的則f (x)=1否則f (x)=04Th

2、e oracle(2)n我們可以用一個(gè)簡(jiǎn)單的方式來(lái)得知黑盒子的傳回值n我們可以利用Deutsch-Jozsa algorithm則21|0|)1(21|0|)(xxxfO)(|xfyxyxOO5The circuit of Grovers algorithmnThe Algorithm Begins with the equal superposition state.nN210|10|NxnnxNH0|n qubitsoracle workspacemeasurenH6The circuit of the Grover iteration (G)I|00|2:PhaseOIG)|2( :nn

3、H0|IHIH n qubitsoracle workspace7About the Phase )|00|2(I 1 | 1 | )|00|(21 |0|0|0|2 0| )|00|2(0|PhasePhaseII0|1 |0|ba1 |0|ba 1 |對(duì) 軸做鏡射0|OIG)|2( :8What does the Grover iteration do?(1)nWe define the new basis:|2sin|2cos|)(2sin)(2cosNMNMN|1|1| NMNMNxMxMNxx9What does the Grover iteration do?(2)| )212si

4、n(| )212cos(|)|(kkGbabaOKOIG)|2( :10PerformancenHow many times must the Grover iteration be repeated?nWhats the probability of getting a solution?11How many times(R) must the Grover iteration be repeated?nThe times R2222CIRMNRNM42sin2)(MNO12The probability of get a solution?nBy observation:The probability at least nFor example when MN:NMNM/2most at is state final the/2sin13ConclusionnDifference with classic :Grovers Algorithm have high probability when MN nAdvantag