Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method

doi:10.1088/1674-1056/ab4e88

Abstract For the unsorted database quantum search with the unknown fraction λ of target items, there are mainly two kinds of methods, i.e., fixed-point and trail-and-error. (i) In terms of the fixed-point method, Yoder et al.[Phys. Rev. Lett. 113 210501 (2014)] claimed that the quadratic speedup over classical algorithms has been achieved. However, in this paper, we point out that this is not the case, because the query complexity of Yoder's algorithm is actually in O(1/√λ₀) rather than O(1/√λ), where λ₀ is a known lower bound of λ. (ii) In terms of the trail-and-error method, currently the algorithm without randomness has to take more than 1 times queries or iterations than the algorithm with randomly selected parameters. For the above problems, we provide the first hybrid quantum search algorithm based on the fixed-point and trail-and-error methods, where the matched multiphase Grover operations are trialed multiple times and the number of iterations increases exponentially along with the number of trials. The upper bound of expected queries as well as the optimal parameters are derived. Compared with Yoder's algorithm, the query complexity of our algorithm indeed achieves the optimal scaling in λ for quantum search, which reconfirms the practicality of the fixed-point method. In addition, our algorithm also does not contain randomness, and compared with the existing deterministic algorithm, the query complexity can be reduced by about 1/3. Our work provides a new idea for the research on fixed-point and trial-and-error quantum search.

Keywords: quantum search fixed-point trail-and-error unknown number of target items

Received: 11 August 2019
Revised: 16 September 2019
Accepted manuscript online:

PACS:	03.67.Ac	(Quantum algorithms, protocols, and simulations)
	03.67.-a	(Quantum information)
	03.65.-w	(Quantum mechanics)

Fund: Project supported by the National Natural Science Foundation of China (Grant Nos. 11504430 and 61502526) and the National Basic Research Program of China (Grant No. 2013CB338002).

Corresponding Authors: Wan-Su Bao
E-mail: bws@qiclab.cn

Cite this article:

Tan Li(李坦), Shuo Zhang(张硕), Xiang-Qun Fu(付向群), Xiang Wang(汪翔), Yang Wang(汪洋), Jie Lin(林杰), Wan-Su Bao(鲍皖苏) Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method 2019 Chin. Phys. B 28 120301

[33]	Yoder T J, Low G H and Chuang I L 2014 Phys. Rev. Lett. 113 210501
[1]	Grover L K 1996 Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, New York, pp. 212-219
[34]	Chakraborty S, Radhakrishnan J and Raghunathan N 2005 Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (Berlin: Springer) pp. 245-256
[2]	Grover L K 1997 Phys. Rev. Lett. 79 325
[35]	Tulsi T, Grover L K and Patel A 2006 Quantum Inf. Comput. 6 483
[3]	Biron D, Biham O, Biham E, Grassl M and Lidar D A 1999 Quantum Computing and Quantum Communications (Berlin: Springer) pp. 140-147
[36]	Bhole G, Anjusha V S and Mahesh T S 2016 Phys. Rev. A 93 042339
[4]	Long G L, Li Y S, Zhang W L and Niu L 1999 Phys. Lett. A 262 27
[37]	Gurnani K, Behera B K and Panigrahi P K 2017 arXiv: 1712.10231 [quant-ph]
[5]	Long G L 2001 Phys. Rev. A 64 022307
[38]	Dalzell A M, Yoder T J and Chuang I L 2017 Phys. Rev. A 95 012311
[6]	Long G L, Li X and Sun Y 2002 Phys. Lett. A 294 143
[39]	Qiu D W and Zheng S G 2018 Phys. Rev. A 97 062331
[7]	Li P C and Li S Y 2007 Phys. Lett. A 366 42
[40]	Cai G Y and Qiu D W 2018 J. Comput. Syst. Sci. 97 83
[8]	Zhang Y Y, Hu H P and Lu S F 2011 Chin. Phys. B 20 040309
[41]	Younes A, Rowe J and Miller J 2008 Physica D 237 1074
[9]	Sun J, Lu S F, Liu F and Yang L P 2012 Chin. Phys. B 21 010306
[42]	Younes A 2013 Appl. Math. Inf. Sci. 7 93
[10]	Li F G, Bao W S, Zhang S, Wang X, Huang H L, Li T and Ma B W 2009 Phys. Rev. A 79 014301
[43]	Okamoto K and Watanabe O 2001 Computing and Combinatorics (Berlin: Springer) pp. 493-501
[11]	Toyama F M, Dijk W V, Nogami Y, Tabuchi M and Kimura Y 2008 Phys. Rev. A 77 042324
[44]	Younes A, Rowe J and Miller J 2004 AIP Conf. Proc. 734 171
[12]	Toyama F M, Kasai S, Dijk W V and Nogami Y 2009 Phys. Rev. A 79 014301
[45]	Brassard G, Hoyer P, Mosca M and Tapp A 2002 Quantum Computation and Information (Providence: American Mathematical Society) pp. 53-74
[13]	Toyama F M, Dijk W V and Nogami Y 2013 Quantum Inf. Process. 12 1897
[14]	Toyama F M and Dijk W V 2019 Can. J. Phys. 97 777
[46]	Mason J C and Handscomb D C 2002 Chebyshev Polynomials (Boca Raton: CRC Press) pp. 2-3
[15]	Zhong P C, Bao W S and Wei Y 2009 Chinese Phys. Lett. 26 020301
[16]	Giri P R and Korepin V E 2017 Quantum Inf. Process. 16 315
[47]	Grassl M, Langenberg B, Roetteler M and Steinwandt R 2016 Post-Quantum Cryptography (Switzerland: Springer) pp. 29-43
[17]	Zhang K and Korepin V E 2018 Quantum Inf. Process. 17 143
[48]	Kim P, Han D and Jeong K C 2018 Quantum Inf. Process. 17 339
[18]	Mehri-Dehnavi H, Dashtianeh H, Kuchaksaraei H Y, Khoshdareh M M, Movahhedian H and Rahimi R 2018 Int. J. Theor. Phys. 57 3668
[49]	Denisenko D V and Nikitenkova M V 2019 J. Exp. Theor. Phys. 128 25
[19]	Byrnes T, Forster G and Tessler L 2018 Phys. Rev. Lett. 120 060501
[50]	Cheng S T and Tao M H 2007 J. Comput. Syst. Sci. 73 123
[20]	Ma B W, Bao W S, Li T, Li F G, Zhang S, and Fu X Q 2014 Chin. Phys. Lett. 31 050301
[51]	Yang W L, Wei H, Zhou F, Chang W L and Feng M 2009 J. Phys. B: At. Mol. Opt. Phys. 42 145503
[21]	Li T, Bao W S, Lin W Q, Zhang H and Fu X Q 2014 Chin. Phys. Lett. 31 050301
[52]	Lee B and Perkowski M 2016 Euromicro Conference on Digital System Design (DSD) (Cyprus: IEEE) pp. 413-422
[22]	Li T, Bao W S, Huang H L, Li F G, Fu X Q, Zhang S, Guo C, Du Y T, Wang X and Lin J 2018 Phys. Rev. A 98 062308
[23]	Li T, Fu X Q, Wang Y, Zhang S, Wang X, Du Y T and Bao W S 2019 Phys. Rev. A 100 012349
[53]	Matuschak A and Nielsen M A https://quantum.country/search [Accessed: 15 September 2019]
[24]	Pan M H and Qiu D W 2019 Phys. Rev. A 100 012349
[54]	Chailloux A, Naya-Plasencia M and Schrottenloher A 2017 Advances in Cryptology–ASIACRYPT 2017 (Cham: Springer) pp. 211-240
[25]	Pan M H, Qiu D W, Mateus P and Gruska J 2019 Theor. Comput. Sci. 773 138
[26]	Bennett C H, Bernstein E, Brassard G and Vazirani U 1998 Fortschr. Phys. 46 493
[27]	Boyer M, Brassard G, Høyer P and Tapp A 1998 Fortschr. Phys. 46 493
[28]	Zalka C 1999 Phys. Rev. A 60 2746
[29]	Nielson M A and Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge: Cambridge University Press) pp. 269-271
[30]	Grover L K and Radhakrishnan J2005 Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures New York, pp. 186-194
[31]	Brassard G 1997 Science 275 627
[32]	Grover L K 2005 Phys. Rev. Lett. 95 150501
[33]	Yoder T J, Low G H and Chuang I L 2014 Phys. Rev. Lett. 113 210501
[34]	Chakraborty S, Radhakrishnan J and Raghunathan N 2005 Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (Berlin: Springer) pp. 245-256
[35]	Tulsi T, Grover L K and Patel A 2006 Quantum Inf. Comput. 6 483
[36]	Bhole G, Anjusha V S and Mahesh T S 2016 Phys. Rev. A 93 042339
[37]	Gurnani K, Behera B K and Panigrahi P K 2017 arXiv: 1712.10231 [quant-ph]
[38]	Dalzell A M, Yoder T J and Chuang I L 2017 Phys. Rev. A 95 012311
[39]	Qiu D W and Zheng S G 2018 Phys. Rev. A 97 062331
[40]	Cai G Y and Qiu D W 2018 J. Comput. Syst. Sci. 97 83
[41]	Younes A, Rowe J and Miller J 2008 Physica D 237 1074
[42]	Younes A 2013 Appl. Math. Inf. Sci. 7 93
[43]	Okamoto K and Watanabe O 2001 Computing and Combinatorics (Berlin: Springer) pp. 493-501
[44]	Younes A, Rowe J and Miller J 2004 AIP Conf. Proc. 734 171
[45]	Brassard G, Hoyer P, Mosca M and Tapp A 2002 Quantum Computation and Information (Providence: American Mathematical Society) pp. 53-74
[46]	Mason J C and Handscomb D C 2002 Chebyshev Polynomials (Boca Raton: CRC Press) pp. 2-3
[47]	Grassl M, Langenberg B, Roetteler M and Steinwandt R 2016 Post-Quantum Cryptography (Switzerland: Springer) pp. 29-43
[48]	Kim P, Han D and Jeong K C 2018 Quantum Inf. Process. 17 339
[49]	Denisenko D V and Nikitenkova M V 2019 J. Exp. Theor. Phys. 128 25
[50]	Cheng S T and Tao M H 2007 J. Comput. Syst. Sci. 73 123
[51]	Yang W L, Wei H, Zhou F, Chang W L and Feng M 2009 J. Phys. B: At. Mol. Opt. Phys. 42 145503
[52]	Lee B and Perkowski M 2016 Euromicro Conference on Digital System Design (DSD) (Cyprus: IEEE) pp. 413-422
[53]	Matuschak A and Nielsen M A https://quantum.country/search [Accessed: 15 September 2019]
[54]	Chailloux A, Naya-Plasencia M and Schrottenloher A 2017 Advances in Cryptology–ASIACRYPT 2017 (Cham: Springer) pp. 211-240

[1]	Quantum search of many vertices on the joined complete graph Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天), and Xiangdong Zhang(张向东). Chin. Phys. B, 2022, 31(7): 070504.
[2]	Transitionless driving on local adiabatic quantum search algorithm Feng-guang Li(李风光), Wan-su Bao(鲍皖苏), Shuo Zhang(张硕), Xiang Wang(汪翔), He-liang Huang(黄合良), Tan Li(李坦), Bo-wen Ma(马博文). Chin. Phys. B, 2018, 27(1): 010308.
[3]	Search algorithm on strongly regular graphsbased on scattering quantum walks Xi-Ling Xue(薛希玲), Zhi-Hao Liu(刘志昊), Han-Wu Chen(陈汉武). Chin. Phys. B, 2017, 26(1): 010301.
[4]	Decoherence in optimized quantum random-walk search algorithm Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(8): 080307.
[5]	Effects of systematic phase errors on optimized quantum random-walk search algorithm Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(6): 060304.
[6]	Optimized quantum random-walk search algorithm for multi-solution search Zhang Yu-Chao (张宇超), Bao Wan-Su (鲍皖苏), Wang Xiang (汪翔), Fu Xiang-Qun (付向群). Chin. Phys. B, 2015, 24(11): 110309.
[7]	Partial evolution based local adiabatic quantum search Sun Jie(孙杰), Lu Song-Feng(路松峰), Liu Fang(刘芳), and Yang Li-Ping(杨莉萍) . Chin. Phys. B, 2012, 21(1): 010306.
[8]	A quantum search algorithm based on partial adiabatic evolution Zhang Ying-Yu(张映玉), Hu He-Ping(胡和平), and Lu Song-Feng(路松峰) . Chin. Phys. B, 2011, 20(4): 040309.
[9]	Implementation of quantum search scheme by adiabatic passage in a cavity--laser--atom system Liu Wen-Wu(刘文武), Li Hong-Cai(李洪才), and Yang Rong-Can(杨榕灿). Chin. Phys. B, 2009, 18(1): 23-29.

No Suggested Reading articles found!

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method

Cite this article:

Online attention