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

doi:10.1088/1674-1056/ab4e88

中国物理B ›› 2019, Vol. 28 ›› Issue (12): 120301-120301.doi: 10.1088/1674-1056/ab4e88

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

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

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

收稿日期:2019-08-11 修回日期:2019-09-16 出版日期:2019-12-05 发布日期:2019-12-05
通讯作者: Wan-Su Bao E-mail:bws@qiclab.cn
基金资助:
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).

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

Received:2019-08-11 Revised:2019-09-16 Online:2019-12-05 Published:2019-12-05
Contact: Wan-Su Bao E-mail:bws@qiclab.cn
Supported by:
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).

摘要/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.

关键词: quantum search, fixed-point, trail-and-error, unknown number of target items

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.

Key words: quantum search, fixed-point, trail-and-error, unknown number of target items

中图分类号: (Quantum algorithms, protocols, and simulations)

03.67.Ac

03.67.-a (Quantum information) 03.65.-w (Quantum mechanics)

李坦, 张硕, 付向群, 汪翔, 汪洋, 林杰, 鲍皖苏. Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method[J]. 中国物理B, 2019, 28(12): 120301-120301.

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[J]. Chin. Phys. B, 2019, 28(12): 120301-120301.

参考文献 54

[33]	Yoder T J, Low G H and Chuang I L 2014 Phys. Rev. Lett. 113 210501 doi: 10.1103/PhysRevLett.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 doi: 10.1103/PhysRevLett.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 doi: 10.1103/PhysRevA.93.042339
[4]	Long G L, Li Y S, Zhang W L and Niu L 1999 Phys. Lett. A 262 27 doi: 10.1016/S0375-9601(99)00631-3
[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 doi: 10.1103/PhysRevA.64.022307
[38]	Dalzell A M, Yoder T J and Chuang I L 2017 Phys. Rev. A 95 012311 doi: 10.1103/PhysRevA.95.012311
[6]	Long G L, Li X and Sun Y 2002 Phys. Lett. A 294 143 doi: 10.1016/S0375-9601(02)00055-5
[39]	Qiu D W and Zheng S G 2018 Phys. Rev. A 97 062331 doi: 10.1103/PhysRevA.97.062331
[7]	Li P C and Li S Y 2007 Phys. Lett. A 366 42 doi: 10.1016/j.physleta.2007.02.029
[40]	Cai G Y and Qiu D W 2018 J. Comput. Syst. Sci. 97 83 doi: 10.1016/j.jcss.2018.05.001
[8]	Zhang Y Y, Hu H P and Lu S F 2011 Chin. Phys. B 20 040309 doi: 10.1088/1674-1056/20/4/040309
[41]	Younes A, Rowe J and Miller J 2008 Physica D 237 1074 doi: 10.1016/j.physd.2007.12.005
[9]	Sun J, Lu S F, Liu F and Yang L P 2012 Chin. Phys. B 21 010306 doi: 10.1088/1674-1056/21/1/010306
[42]	Younes A 2013 Appl. Math. Inf. Sci. 7 93 doi: 10.12785/amis/070110
[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 doi: 10.1103/PhysRevA.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 doi: 10.1103/PhysRevA.77.042324
[44]	Younes A, Rowe J and Miller J 2004 AIP Conf. Proc. 734 171 doi: 10.1063/1.1834408
[12]	Toyama F M, Kasai S, Dijk W V and Nogami Y 2009 Phys. Rev. A 79 014301 doi: 10.1103/PhysRevA.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 doi: 10.1007/s11128-012-0498-0
[14]	Toyama F M and Dijk W V 2019 Can. J. Phys. 97 777 doi: 10.1139/cjp-2018-0452
[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 doi: 10.1088/0256-307X/26/2/020301
[16]	Giri P R and Korepin V E 2017 Quantum Inf. Process. 16 315 doi: 10.1007/s11128-017-1768-7
[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 doi: 10.1007/s11128-018-1907-9
[48]	Kim P, Han D and Jeong K C 2018 Quantum Inf. Process. 17 339 doi: 10.1007/s11128-018-2107-3
[18]	Mehri-Dehnavi H, Dashtianeh H, Kuchaksaraei H Y, Khoshdareh M M, Movahhedian H and Rahimi R 2018 Int. J. Theor. Phys. 57 3668 doi: 10.1007/s10773-018-3880-6
[49]	Denisenko D V and Nikitenkova M V 2019 J. Exp. Theor. Phys. 128 25 doi: 10.1134/S1063776118120142
[19]	Byrnes T, Forster G and Tessler L 2018 Phys. Rev. Lett. 120 060501 doi: 10.1103/PhysRevLett.120.060501
[50]	Cheng S T and Tao M H 2007 J. Comput. Syst. Sci. 73 123 doi: 10.1016/j.jcss.2006.09.003
[20]	Ma B W, Bao W S, Li T, Li F G, Zhang S, and Fu X Q 2014 Chin. Phys. Lett. 31 050301 doi: 10.1088/0256-307X/31/5/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 doi: 10.1088/0953-4075/42/14/145503
[21]	Li T, Bao W S, Lin W Q, Zhang H and Fu X Q 2014 Chin. Phys. Lett. 31 050301 doi: 10.1088/0256-307X/31/5/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 doi: 10.1103/PhysRevA.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 doi: 10.1103/PhysRevA.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 doi: 10.1103/PhysRevA.100.012349
[54]	Chailloux A, Naya-Plasencia M and Schrottenloher A 2017 Advances in Cryptology–ASIACRYPT 2017 (Cham: Springer) pp. 211-240 doi: ces in\|\|Cryptology
[25]	Pan M H, Qiu D W, Mateus P and Gruska J 2019 Theor. Comput. Sci. 773 138 doi: 10.1016/j.tcs.2018.10.001
[26]	Bennett C H, Bernstein E, Brassard G and Vazirani U 1998 Fortschr. Phys. 46 493 doi: 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
[27]	Boyer M, Brassard G, Høyer P and Tapp A 1998 Fortschr. Phys. 46 493 doi: 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
[28]	Zalka C 1999 Phys. Rev. A 60 2746 doi: 10.1103/PhysRevA.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 doi: 10.1126/science.275.5300.627
[32]	Grover L K 2005 Phys. Rev. Lett. 95 150501 doi: 10.1103/PhysRevLett.95.150501
[33]	Yoder T J, Low G H and Chuang I L 2014 Phys. Rev. Lett. 113 210501 doi: 10.1103/PhysRevLett.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 doi: 10.1103/PhysRevA.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 doi: 10.1103/PhysRevA.95.012311
[39]	Qiu D W and Zheng S G 2018 Phys. Rev. A 97 062331 doi: 10.1103/PhysRevA.97.062331
[40]	Cai G Y and Qiu D W 2018 J. Comput. Syst. Sci. 97 83 doi: 10.1016/j.jcss.2018.05.001
[41]	Younes A, Rowe J and Miller J 2008 Physica D 237 1074 doi: 10.1016/j.physd.2007.12.005
[42]	Younes A 2013 Appl. Math. Inf. Sci. 7 93 doi: 10.12785/amis/070110
[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 doi: 10.1063/1.1834408
[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 doi: 10.1007/s11128-018-2107-3
[49]	Denisenko D V and Nikitenkova M V 2019 J. Exp. Theor. Phys. 128 25 doi: 10.1134/S1063776118120142
[50]	Cheng S T and Tao M H 2007 J. Comput. Syst. Sci. 73 123 doi: 10.1016/j.jcss.2006.09.003
[51]	Yang W L, Wei H, Zhou F, Chang W L and Feng M 2009 J. Phys. B: At. Mol. Opt. Phys. 42 145503 doi: 10.1088/0953-4075/42/14/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 doi: ces in\|\|Cryptology

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

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

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 54

相关文章 9

Metrics

本文评价

推荐阅读 0

[1]	Tingting Ji(冀婷婷), Naiqiao Pan(潘乃桥), Tian Chen(陈天), and Xiangdong Zhang(张向东). Quantum search of many vertices on the joined complete graph[J]. 中国物理B, 2022, 31(7): 70504-070504.
[2]	李风光, 鲍皖苏, 张硕, 汪翔, 黄合良, 李坦, 马博文. Transitionless driving on local adiabatic quantum search algorithm[J]. 中国物理B, 2018, 27(1): 10308-010308.
[3]	薛希玲, 刘志昊, 陈汉武. Search algorithm on strongly regular graphsbased on scattering quantum walks[J]. 中国物理B, 2017, 26(1): 10301-010301.
[4]	张宇超, 鲍皖苏, 汪翔, 付向群. Decoherence in optimized quantum random-walk search algorithm[J]. 中国物理B, 2015, 24(8): 80307-080307.
[5]	张宇超, 鲍皖苏, 汪翔, 付向群. Effects of systematic phase errors on optimized quantum random-walk search algorithm[J]. 中国物理B, 2015, 24(6): 60304-060304.
[6]	张宇超, 鲍皖苏, 汪翔, 付向群. Optimized quantum random-walk search algorithm for multi-solution search[J]. 中国物理B, 2015, 24(11): 110309-110309.
[7]	孙杰, 路松峰, 刘芳, 杨莉萍. Partial evolution based local adiabatic quantum search[J]. 中国物理B, 2012, 21(1): 10306-010306.
[8]	张映玉, 胡和平, 路松峰. A quantum search algorithm based on partial adiabatic evolution[J]. 中国物理B, 2011, 20(4): 40309-040309.
[9]	刘文武, 李洪才, 杨榕灿. Implementation of quantum search scheme by adiabatic passage in a cavity--laser--atom system[J]. 中国物理B, 2009, 18(1): 23-29.