{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:37:16Z","timestamp":1760236636599,"version":"build-2065373602"},"reference-count":32,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,12,8]],"date-time":"2021-12-08T00:00:00Z","timestamp":1638921600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11974205","11774197","12005015"],"award-info":[{"award-number":["11974205","11774197","12005015"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2017YFA0303700"],"award-info":[{"award-number":["2017YFA0303700"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100015956","name":"Key Research and Development Program of Guangdong province","doi-asserted-by":"publisher","award":["2018B030325002"],"award-info":[{"award-number":["2018B030325002"]}],"id":[{"id":"10.13039\/501100015956","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given \u03bb=M\/N, where M is the number of marked state and N is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover\u2013Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity ON as the Grover\u2019s algorithm, and shows high tolerance of the uncertainty in the ratio M\/N. In particular, for a database with an uncertainty in the ratio M\u00b1MN, our algorithm will find the target states with a success rate no less than 96%.<\/jats:p>","DOI":"10.3390\/e23121649","type":"journal-article","created":{"date-parts":[[2021,12,10]],"date-time":"2021-12-10T02:07:18Z","timestamp":1639102038000},"page":"1649","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Robust Quantum Search with Uncertain Number of Target States"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6745-2883","authenticated-orcid":false,"given":"Yuanye","family":"Zhu","sequence":"first","affiliation":[{"name":"State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zeguo","family":"Wang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bao","family":"Yan","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China"},{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shijie","family":"Wei","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China"},{"name":"Beijing Academy of Quantum Information Sciences, Beijing 100193, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Grover, L.K. (1996, January 22\u201324). A Fast Quantum Mechanical Algorithm for Database Search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA.","DOI":"10.1145\/237814.237866"},{"key":"ref_2","unstructured":"Brassard, G., and H\u00f8yer, P. (1997, January 17\u201319). An exact quantum polynomial-time algorithm for Simon\u2019s problem. Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, Ramat-Gan, Israel."},{"key":"ref_3","unstructured":"Nielsen, M.A., and Chuang, I.L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","article-title":"Quantum mechanics helps in searching for a needle in a haystack","volume":"79","author":"Grover","year":"1997","journal-title":"Phys. Rev. Lett."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Aharonov, D. (1998). Quantum computation. Annual Reviews of Computational Physics VI, World Scientific.","DOI":"10.1142\/9789812815569_0007"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2746","DOI":"10.1103\/PhysRevA.60.2746","article-title":"Grover\u2019s quantum searching algorithm is optimal","volume":"60","author":"Zalka","year":"1999","journal-title":"Phys. Rev. A"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1023\/A:1019868924061","article-title":"Quantum algorithms for highly structured search problems","volume":"1","author":"Hunziker","year":"2002","journal-title":"Quantum Inf. Process."},{"key":"ref_8","unstructured":"Michele, M. (1998, January 24\u201328). Quantum searching, counting and amplitude amplification by eigenvector analysis. Proceedings of the Randomized Algorithms, Workshop of Mathematical Foundations of Computer Science, Brno, Czech Republic."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1088\/0253-6102\/32\/3\/335","article-title":"Arbitrary phase rotation of the marked state cannot be used for Grover\u2019s quantum search algorithm","volume":"32","author":"Guilu","year":"1999","journal-title":"Commun. Theoret. Phys."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1090\/conm\/305\/05215","article-title":"Quantum Amplitude Amplification and Estimation","volume":"Volume 305","author":"Brassard","year":"2002","journal-title":"Quantum Computation and Information, Contemporary Mathematics"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"022307","DOI":"10.1103\/PhysRevA.64.022307","article-title":"Grover algorithm with zero theoretical failure rate","volume":"64","author":"Long","year":"2001","journal-title":"Phys. Rev. A"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2571","DOI":"10.1007\/s10773-014-2055-3","article-title":"An Exact Quantum Search Algorithm with Arbitrary Database","volume":"53","author":"Liu","year":"2014","journal-title":"Int. J. Theor. Phys."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1897","DOI":"10.1007\/s11128-012-0498-0","article-title":"Quantum search with certainty based on modified Grover algorithms: Optimum choice of parameters","volume":"12","author":"Toyama","year":"2013","journal-title":"Quantum Inf. Process."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1007\/s10701-015-9968-4","article-title":"Highlighting the Mechanism of the Quantum Speedup by Time-Symmetric and Relational Quantum Mechanics","volume":"46","author":"Castagnoli","year":"2016","journal-title":"Found. Phys."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1126\/science.275.5300.627","article-title":"Searching a quantum phone book","volume":"275","author":"Brassard","year":"1997","journal-title":"Science"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"180501","DOI":"10.1103\/PhysRevLett.124.180501","article-title":"Grover Search as a Naturally Occurring Phenomenon","volume":"124","author":"Roget","year":"2020","journal-title":"Phys. Rev. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"022314","DOI":"10.1103\/PhysRevA.70.022314","article-title":"Spatial search by quantum walk","volume":"70","author":"Childs","year":"2004","journal-title":"Phys. Rev. A"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Portugal, R. (2018). Quantum Walks and Search Algorithms, Springer.","DOI":"10.1007\/978-3-319-97813-0"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"150501","DOI":"10.1103\/PhysRevLett.95.150501","article-title":"Fixed-point quantum search","volume":"95","author":"Grover","year":"2005","journal-title":"Phys. Rev. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"210501","DOI":"10.1103\/PhysRevLett.113.210501","article-title":"Fixed-point quantum search with an optimal number of queries","volume":"113","author":"Yoder","year":"2014","journal-title":"Phys. Rev. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","article-title":"Tight bounds on quantum searching","volume":"46","author":"Boyer","year":"1998","journal-title":"Fortsch. Phys."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., and Tapp, A. (1998). Quantum counting. International Colloquium on Automata, Languages, and Programming, Springer.","DOI":"10.1007\/BFb0055105"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s11128-011-0249-7","article-title":"Geometric pictures for quantum search algorithms","volume":"11","author":"Zhao","year":"2012","journal-title":"Quantum Inf. Process."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1016\/j.jcss.2003.07.010","article-title":"A new protocol and lower bounds for quantum coin flipping","volume":"68","author":"Ambainis","year":"2004","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2493252.2493256","article-title":"Quantum Rejection Sampling","volume":"5","author":"Ozols","year":"2013","journal-title":"ACM Trans. Comput. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"e34","DOI":"10.1002\/que2.34","article-title":"Recent advances in quantum machine learning","volume":"2","author":"Zhang","year":"2020","journal-title":"Quantum Eng."},{"key":"ref_27","unstructured":"Brassard, G., H\u00f8yer, P., and Tapp, A. (2008). Quantum Algorithm for the Collision Problem. Encyclopedia of Algorithms, Springer."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"e19","DOI":"10.1002\/que2.19","article-title":"Scaling reconfigurable emulation of quantum algorithms at high precision and high throughput","volume":"1","author":"Mahmud","year":"2019","journal-title":"Quantum Eng."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Wen, J., Lv, D., Yung, M.H., and Long, G.L. (2021). Variational Quantum Packaged Deflation for Arbitrary Excited States. Quantum Eng., e80.","DOI":"10.1002\/que2.80"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"e49","DOI":"10.1002\/que2.49","article-title":"A query-based quantum eigensolver","volume":"2","author":"Jin","year":"2020","journal-title":"Quantum Eng."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1016\/j.fmre.2021.06.005","article-title":"Enhancing crystal structure prediction by decomposition and evolution schemes based on graph theory","volume":"1","author":"Gao","year":"2021","journal-title":"Fundam. Res."},{"key":"ref_32","first-page":"9","article-title":"The Second Quantum Revolution with Quantum Computers","volume":"30","author":"Chang","year":"2020","journal-title":"AAPPS Bull."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/12\/1649\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:43:03Z","timestamp":1760168583000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/12\/1649"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,8]]},"references-count":32,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["e23121649"],"URL":"https:\/\/doi.org\/10.3390\/e23121649","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,12,8]]}}}