{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:35:48Z","timestamp":1777487748189,"version":"3.51.4"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T00:00:00Z","timestamp":1639353600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T00:00:00Z","timestamp":1639353600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Sci. China Inf. Sci."],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s11432-021-3334-1","type":"journal-article","created":{"date-parts":[[2021,12,19]],"date-time":"2021-12-19T14:02:56Z","timestamp":1639922576000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Quantum algorithm and experimental demonstration for the subset sum problem"],"prefix":"10.1007","volume":"65","author":[{"given":"Qilin","family":"Zheng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pingyu","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shichuan","family":"Xue","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chao","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinyao","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miaomiao","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yingwen","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mingtang","family":"Deng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junjie","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ping","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,12,13]]},"reference":[{"key":"3334_CR1","first-page":"340","volume":"44","author":"M R Garey","year":"1979","unstructured":"Garey M R. Computers and intractability: a guide to the theory of np-completeness. Rev Esc Enferm USP, 1979, 44: 340","journal-title":"Rev Esc Enferm USP"},{"key":"3334_CR2","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1109\/TIT.1978.1055927","volume":"24","author":"R Merkle","year":"1978","unstructured":"Merkle R, Hellman M. Hiding information and signatures in trapdoor knapsacks. IEEE Trans Inform Theor, 1978, 24: 525\u2013530","journal-title":"IEEE Trans Inform Theor"},{"key":"3334_CR3","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10207-011-0129-2","volume":"10","author":"A Kate","year":"2011","unstructured":"Kate A, Goldberg I. Generalizing cryptosystems based on the subset sum problem. Int J Inf Secur, 2011, 10: 189\u2013199","journal-title":"Int J Inf Secur"},{"key":"3334_CR4","doi-asserted-by":"crossref","unstructured":"Murakami Y, Sakai R. Security of knapsack cryptosystem using subset-sum decision problem against alternative-solution attack. In: Proceedings of International Symposium on Information Theory and Its Applications (ISITA), 2018. 614\u2013617","DOI":"10.23919\/ISITA.2018.8664306"},{"key":"3334_CR5","unstructured":"Murakami Y, Hamasho S, Kasahara M. A public-key cryptosystem based on decision version of subset sum problem. In: Proceedings of International Symposium on Information Theory and its Applications, 2012. 735\u2013739"},{"key":"3334_CR6","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1002\/nav.20202","volume":"54","author":"C A Glass","year":"2007","unstructured":"Glass C A, Kellerer H. Parallel machine scheduling with job assignment restrictions. Naval Res Logist, 2007, 54: 250\u2013257","journal-title":"Naval Res Logist"},{"key":"3334_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1023\/A:1018930613891","volume":"92","author":"C Gu\u00e9ret","year":"1999","unstructured":"Gu\u00e9ret C, Prins C. A new lower bound for the open-shop problem. Ann Oper Res, 1999, 92: 165\u2013183","journal-title":"Ann Oper Res"},{"key":"3334_CR8","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1109\/TASE.2006.887159","volume":"5","author":"X T Qi","year":"2008","unstructured":"Qi X T. Coordinated logistics scheduling for in-house production and outsourcing. IEEE Trans Automat Sci Eng, 2008, 5: 188\u2013192","journal-title":"IEEE Trans Automat Sci Eng"},{"key":"3334_CR9","first-page":"239","volume-title":"Random separation: a new method for solving fixed-cardinality optimization problems","author":"L Cai","year":"2006","unstructured":"Cai L, Chan S M, Chan S O. Random separation: a new method for solving fixed-cardinality optimization problems. In: Proceedings of International Workshop on Parameterized and Exact Computation. Berlin: Springer, 2006. 239\u2013250"},{"key":"3334_CR10","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1002\/(SICI)1097-0118(199811)29:3<151::AID-JGT3>3.0.CO;2-P","volume":"29","author":"Y Caro","year":"1998","unstructured":"Caro Y, Yuster R. The characterization of zero-sum (mod 2) bipartite Ramsey numbers. J Graph Theor, 1998, 29: 151\u2013166","journal-title":"J Graph Theor"},{"key":"3334_CR11","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02331572","volume":"35","author":"K H Borgwardt","year":"1991","unstructured":"Borgwardt K H, Tremel B. The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem. ZOR \u2014 Methods Model Oper Res, 1991, 35: 113\u2013149","journal-title":"ZOR \u2014 Methods Model Oper Res"},{"key":"3334_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3329863","volume":"15","author":"K Koiliaris","year":"2019","unstructured":"Koiliaris K, Xu C. Faster pseudopolynomial time algorithms for subset sum. ACM Trans Algorithms, 2019, 15: 1\u201320","journal-title":"ACM Trans Algorithms"},{"key":"3334_CR13","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E Horowitz","year":"1974","unstructured":"Horowitz E, Sahni S. Computing partitions with applications to the knapsack problem. J ACM, 1974, 21: 277\u2013292","journal-title":"J ACM"},{"key":"3334_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1999.1034","volume":"33","author":"D Pisinger","year":"1999","unstructured":"Pisinger D. Linear time algorithms for knapsack problems with bounded weights. J Algorithms, 1999, 33: 1\u201314","journal-title":"J Algorithms"},{"key":"3334_CR15","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-24777-7_9","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U, Pisinger D. Multidimensional Knapsack Problems. In: Knapsack Problems. Berlin: Springer, 2004. 235\u2013283"},{"key":"3334_CR16","doi-asserted-by":"crossref","unstructured":"Tsai S. Fast parallel molecular solution for DNA-based computing: the 0\u20131 knapsack problem. In: Proceedings of International Conference on Algorithms and Architectures for Parallel Processing, 2009. 416\u2013427","DOI":"10.1007\/978-3-642-03095-6_40"},{"key":"3334_CR17","doi-asserted-by":"publisher","first-page":"2591","DOI":"10.1073\/pnas.1510825113","volume":"113","author":"J D V Nicolau","year":"2016","unstructured":"Nicolau J D V, Lard M, Korten T, et al. Parallel computation with molecular-motor-propelled agents in nanofabricated networks. Proc Natl Acad Sci USA, 2016, 113: 2591\u20132596","journal-title":"Proc Natl Acad Sci USA"},{"key":"3334_CR18","doi-asserted-by":"publisher","first-page":"20180034","DOI":"10.1098\/rsfs.2018.0034","volume":"8","author":"F C M J M van Delft","year":"2018","unstructured":"van Delft F C M J M, Ipolitti G, Nicolau J D V, et al. Something has to give: scaling combinatorial computing by biological agents exploring physical networks encoding NP-complete problems. Interface Focus, 2018, 8: 20180034","journal-title":"Interface Focus"},{"key":"3334_CR19","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/j.biosystems.2006.06.001","volume":"88","author":"C V Henkel","year":"2007","unstructured":"Henkel C V, B\u00e4ck T, Kok J N, et al. DNA computing of solutions to knapsack problems. Biosystems, 2007, 88: 156\u2013162","journal-title":"Biosystems"},{"key":"3334_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11047-004-5199-x","volume":"4","author":"C V Henkel","year":"2005","unstructured":"Henkel C V, Bladergroen R S, Balog C I A, et al. Protein output for DNA computing. Nat Comput, 2005, 4: 1\u201310","journal-title":"Nat Comput"},{"key":"3334_CR21","first-page":"514","volume":"64","author":"C Isenberg","year":"1976","unstructured":"Isenberg C. The soap film: an analogue computer: soap films provide a simple method of obtaining analogue solutions to some mathematical problems. Am Scientist, 1976, 64: 514\u2013518","journal-title":"Am Scientist"},{"key":"3334_CR22","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/1052796.1052804","volume":"36","author":"S Aaronson","year":"2005","unstructured":"Aaronson S. Guest column: NP-complete problems and physical reality. SIGACT News, 2005, 36: 30\u201352","journal-title":"SIGACT News"},{"key":"3334_CR23","doi-asserted-by":"publisher","first-page":"e147","DOI":"10.1038\/lsa.2014.28","volume":"3","author":"K Wu","year":"2014","unstructured":"Wu K, Garc\u00eda de Abajo J, Soci C, et al. An optical fiber network oracle for NP-complete problems. Light Sci Appl, 2014, 3: e147","journal-title":"Light Sci Appl"},{"key":"3334_CR24","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1364\/AO.46.000711","volume":"46","author":"N T Shaked","year":"2007","unstructured":"Shaked N T, Messika S, Dolev S, et al. Optical solution for bounded NP-complete problems. Appl Opt, 2007, 46: 711\u2013724","journal-title":"Appl Opt"},{"key":"3334_CR25","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1038\/nphoton.2010.94","volume":"4","author":"H J Caulfield","year":"2010","unstructured":"Caulfield H J, Dolev S. Why future supercomputing requires optics. Nat Photon, 2010, 4: 261\u2013263","journal-title":"Nat Photon"},{"key":"3334_CR26","doi-asserted-by":"publisher","first-page":"eaay5853","DOI":"10.1126\/sciadv.aay5853","volume":"6","author":"X Y Xu","year":"2020","unstructured":"Xu X Y, Huang X L, Li Z M, et al. A scalable photonic computer solving the subset sum problem. Sci Adv, 2020, 6: eaay5853","journal-title":"Sci Adv"},{"key":"3334_CR27","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R Schroeppel","year":"1981","unstructured":"Schroeppel R, Shamir A. A T = O(2n\/2), S = O(2n\/4) algorithm for certain NP-complete problems. SIAM J Comput, 1981, 10: 456\u2013464","journal-title":"SIAM J Comput"},{"key":"3334_CR28","first-page":"364","volume-title":"Improved generic algorithms for hard knapsacks","author":"A Becker","year":"2011","unstructured":"Becker A, Coron J S, Joux A. Improved generic algorithms for hard knapsacks. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2011. 364\u2013385"},{"key":"3334_CR29","first-page":"235","volume-title":"New generic algorithms for hard knapsacks","author":"N Howgrave-Graham","year":"2010","unstructured":"Howgrave-Graham N, Joux A. New generic algorithms for hard knapsacks. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2010. 235\u2013256"},{"key":"3334_CR30","unstructured":"Childs A M, Eisenberg J M. Quantum algorithms for subset finding. 2003. ArXiv:quant-ph\/0311038"},{"key":"3334_CR31","first-page":"16","volume-title":"Quantum algorithms for the subset-sum problem","author":"D J Bernstein","year":"2013","unstructured":"Bernstein D J, Jeffery S, Lange T, et al. Quantum algorithms for the subset-sum problem. In: Proceedings of International Workshop on Post-Quantum Cryptography. Berlin: Springer, 2013. 16\u201333"},{"key":"3334_CR32","unstructured":"Helm A, May A. Subset sum quantumly in 1.17n. In: Proceedings of the 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018), 2018"},{"key":"3334_CR33","first-page":"633","volume-title":"Improved classical and quantum algorithms for subset-sum","author":"X Bonnetain","year":"2020","unstructured":"Bonnetain X, Bricout R, Schrottenloher A, et al. Improved classical and quantum algorithms for subset-sum. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Cham: Springer, 2020. 633\u2013666"},{"key":"3334_CR34","doi-asserted-by":"crossref","unstructured":"Chang W L, Ren T T, Feng M, et al. Quantum algorithms of the subset-sum problem on a quantum computer. In: Proceedings of WASE International Conference on Information Engineering, 2009. 54\u201357","DOI":"10.1109\/ICIE.2009.15"},{"key":"3334_CR35","unstructured":"Daskin A. A quantum approach to subset-sum and similar problems. 2017. ArXiv:1707.08730"},{"key":"3334_CR36","unstructured":"Aleksandrowicz G, Alexander T, Barkoutsos P, et al. Qiskit: an open-source framework for quantum computing. 2019. https:\/\/www.qiskit.org\/"},{"key":"3334_CR37","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1038\/s41534-019-0235-y","volume":"6","author":"G Garc\u00eda-P\u00e9rez","year":"2020","unstructured":"Garc\u00eda-P\u00e9rez G, Rossi M A C, Maniscalco S. IBM Q Experience as a versatile experimental test bed for simulating open quantum systems. npj Quantum Inf, 2020, 6: 10","journal-title":"npj Quantum Inf"},{"key":"3334_CR38","unstructured":"Kitaev A Y. Quantum measurements and the Abelian stabilizer problem. 1995. ArXiv:quant-ph\/9511026"},{"key":"3334_CR39","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1090\/conm\/305\/05215","volume":"305","author":"G Brassard","year":"2002","unstructured":"Brassard G, Hoyer P, Mosca M, et al. Quantum amplitude amplification and estimation. Contemporary Math, 2002, 305: 53\u201374","journal-title":"Contemporary Math"},{"key":"3334_CR40","doi-asserted-by":"crossref","unstructured":"Grover L K. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Philadelphia, 1996. 212\u2013219","DOI":"10.1145\/237814.237866"},{"key":"3334_CR41","doi-asserted-by":"publisher","first-page":"032328","DOI":"10.1103\/PhysRevA.100.032328","volume":"100","author":"A W Cross","year":"2019","unstructured":"Cross A W, Bishop L S, Sheldon S, et al. Validating quantum computers using randomized model circuits. Phys Rev A, 2019, 100: 032328","journal-title":"Phys Rev A"},{"key":"3334_CR42","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S1049-250X(05)52003-2","volume":"52","author":"J B Altepeter","year":"2005","unstructured":"Altepeter J B, Jeffrey E R, Kwiat P G. Photonic state tomography. Adv Atom Mol Opt Phys, 2005, 52: 105\u2013159","journal-title":"Adv Atom Mol Opt Phys"}],"container-title":["Science China Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-021-3334-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11432-021-3334-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-021-3334-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,3]],"date-time":"2023-09-03T21:01:55Z","timestamp":1693774915000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11432-021-3334-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,13]]},"references-count":42,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["3334"],"URL":"https:\/\/doi.org\/10.1007\/s11432-021-3334-1","relation":{},"ISSN":["1674-733X","1869-1919"],"issn-type":[{"value":"1674-733X","type":"print"},{"value":"1869-1919","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,13]]},"assertion":[{"value":"24 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"182501"}}