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

Tan Li(李坦)^{1,2}, Shuo Zhang(张硕)^{1,2}, Xiang-Qun Fu(付向群)^{1,2}, Xiang Wang(汪翔)^{1,2}, Yang Wang(汪洋)^{1,2}, Jie Lin(林杰)^{1,2}, Wan-Su Bao(鲍皖苏)^{1,2}

1 Henan Key Laboratory of Quantum Information and Cryptography, PLA SSF IEU, Zhengzhou 450001, China; 2 Synergetic Innovation Center of Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei 230026, China

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/√λ_{0}) rather than O(1/√λ), where λ_{0} 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.

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

Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.