| GENERAL |
|
|
|
|
A Four-Phase Improvement of Grover's Algorithm |
| Bo-Wen Ma1,2, Wan-Su Bao1,2**, Tan Li1,2, Feng-Guang Li1,2, Shuo Zhang1,2, Xiang-Qun Fu1,2 |
1Henan Key Laboratory of Quantum Information and Cryptography, Zhengzhou 450001
2Synergetic Innovation Center of Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei 230026
|
|
| Cite this article: |
|
Bo-Wen Ma, Wan-Su Bao, Tan Li et al 2017 Chin. Phys. Lett. 34 070305 |
|
|
|
|
Abstract When applying Grover's algorithm to an unordered database, the probability of obtaining correct results usually decreases as the quantity of target increases. A four-phase improvement of Grover's algorithm is proposed to fix the deficiency, and the unitary and the phase-matching condition are also proposed. With this improved scheme, when the proportion of target is over 1/3, the probability of obtaining correct results is greater than 97.82% with only one iteration using two phases. When the computational complexity is $O(\sqrt{M/N})$, the algorithm can succeed with a probability no less than 99.63%.
|
|
|
Received: 26 April 2017
Published: 23 June 2017
|
|
| PACS: |
03.67.Lx
|
(Quantum computation architectures and implementations)
|
| |
03.67.-a
|
(Quantum information)
|
| |
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
|
|
| Fund: Supported by the National Basic Research Program of China under Grant No 2013CB338002, and the National Natural Science Foundation of China under Grant No 11504430. |
|
|
|
| [1] | Grover L K 1996 Proceedings of the 28th Annual Symposium on Theory of Computing (New York: ACM Press) | | [2] | Grover L K 1997 Phys. Rev. Lett. 79 325 | | [3] | Grover L K 1998 Phys. Rev. Lett. 80 4329 | | [4] | Long G L, Li Y S, Zhang W L and Niu L 1999 Phys. Lett. A 262 27 | | [5] | Biham E, Biham O, Biron D, Grassl M and Lidar D A 1999 Phys. Rev. A 60 2742 | | [6] | Hoyer P 2000 Phys. Rev. A 62 052304 | | [7] | Long G L 2001 Phys. Rev. A 64 022307 | | [8] | Long G L, Li X and Sun Y 2002 Phys. Lett. A 294 143 | | [9] | Younes A, Rowe J and Miller J 2004 Proc. 7th International Conference on Quantum Communication, Measurement and Computing (UK, 25–29 July 2004) | | [10] | Grover L K 2005 Phys. Rev. Lett. 95 150501 | | [11] | Li P C and Li S Y 2007 Phys. Lett. A 366 42 | | [12] | Toyama F M, Van Dijk W, Nogami Y, Tabuchi M and Kimura Y 2008 Phys. Rev. A 77 042324 | | [13] | Tulsi A 2008 Phys. Rev. A 78 022332 | | [14] | Zhong P C and Bao W S 2008 Chin. Phys. Lett. 25 2774 | | [15] | Li X and Li P C 2012 J. Quantum Inf. Sci. 2 28 | | [16] | Younes A 2013 Appl. Math. Inf. Sci. 7 93 | | [17] | Li T, Bao W S, Lin W Q, Zhang H and Fu X Q 2013 Chin. Phys. Lett. 30 050301 | | [18] | Guo Y, Shi W S et al 2017 J. Phys. Soc. Jpn. 86 024006 | | [19] | Zhong P C and Bao W S 2008 Proc. ICCSE 3rd International Conference on Computer Science & Education (Kaifeng, China, 25–27 July 2008) | | [20] | Nielson M A and Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge: Cambridge University Press) chap 6 p 253 |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
