{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T00:47:32Z","timestamp":1776127652351,"version":"3.50.1"},"reference-count":31,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2022,10,8]],"date-time":"2022-10-08T00:00:00Z","timestamp":1665187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["61972413"],"award-info":[{"award-number":["61972413"]}]},{"name":"National Natural Science Foundation of China","award":["61901525"],"award-info":[{"award-number":["61901525"]}]},{"name":"National Natural Science Foundation of China","award":["62002385"],"award-info":[{"award-number":["62002385"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The variational quantum algorithm (VQA) is a hybrid classical\u2013quantum algorithm. It can actually run in an intermediate-scale quantum device where the number of available qubits is too limited to perform quantum error correction, so it is one of the most promising quantum algorithms in the noisy intermediate-scale quantum era. In this paper, two ideas for solving the learning with errors problem (LWE) using VQA are proposed. First, after reducing the LWE problem into the bounded distance decoding problem, the quantum approximation optimization algorithm (QAOA) is introduced to improve classical methods. Second, after the LWE problem is reduced into the unique shortest vector problem, the variational quantum eigensolver (VQE) is used to solve it, and the number of qubits required is calculated in detail. Small-scale experiments are carried out for the two LWE variational quantum algorithms, and the experiments show that VQA improves the quality of the classical solutions.<\/jats:p>","DOI":"10.3390\/e24101428","type":"journal-article","created":{"date-parts":[[2022,10,8]],"date-time":"2022-10-08T20:43:21Z","timestamp":1665261801000},"page":"1428","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Using Variational Quantum Algorithm to Solve the LWE Problem"],"prefix":"10.3390","volume":"24","author":[{"given":"Lihui","family":"Lv","sequence":"first","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"},{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"}]},{"given":"Bao","family":"Yan","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"},{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3947-337X","authenticated-orcid":false,"given":"Hong","family":"Wang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"},{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8946-3655","authenticated-orcid":false,"given":"Zhi","family":"Ma","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"},{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3209-821X","authenticated-orcid":false,"given":"Yangyang","family":"Fei","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"},{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"}]},{"given":"Xiangdong","family":"Meng","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"},{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"}]},{"given":"Qianheng","family":"Duan","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China"},{"name":"Henan Key Laboratory of Network Cryptography Technology, Zhengzhou 450001, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,10,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Ajtai, M. (1996, January 22\u201324). Generating hard instances of lattice problems (extended abstract). Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC \u201996), New York, NY, USA.","DOI":"10.1145\/237814.237838"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., and Dwork, C. (1997, January 4\u20136). A public-key cryptosystem with worst-case\/average-case equivalence. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC \u201997), New York, NY, USA.","DOI":"10.1145\/258533.258604"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Buhler, J.P. (1998). NTRU: A ring-based public key cryptosystem. Algorithmic Number Theory, Springer.","DOI":"10.1007\/BFb0054849"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Regev, O. (2005, January 22\u201324). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC \u201905), New York, NY, USA.","DOI":"10.1145\/1060590.1060603"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Halevi, S. (2009). Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. Advances in Cryptology-CRYPTO 2009, Springer.","DOI":"10.1007\/978-3-642-03356-8"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., and Vaikuntanathan, V. (2011, January 22\u201325). Efficient Fully Homomorphic Encryption from (Standard) LWE. Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, CA, USA.","DOI":"10.1109\/FOCS.2011.12"},{"key":"ref_7","unstructured":"Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., and Stehl\u00e9, D. (2022, February 15). CRYSTALS-KYBER: Algorithm Specifications and Supporting Documentation. Available online: https:\/\/pq-crystals.org\/kyber\/data\/kyber-specification-round3-20210804.pdf."},{"key":"ref_8","unstructured":"Bai, S., Ducas, L., Kiltz, E., Leopoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., and Stehl\u00e9, D. (2022, January 30). CRYSTALS-Dilithium: Algorithm Specifications and Supporting Documentation (Version 3.1). Available online: https:\/\/pq-crystals.org\/dilithium\/data\/dilithiumspecification-round3-20210208.pdf."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1145\/792538.792543","article-title":"Noise-tolerant learning, the parity problem, and the statistical query model","volume":"50","author":"Blum","year":"2003","journal-title":"J. ACM"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Aceto, L., Henzinger, M., and Sgall, J. (2011). New Algorithms for Learning in Presence of Errors. Automata, Languages and Programming. ICALP 2011, Springer.","DOI":"10.1007\/978-3-642-22006-7"},{"key":"ref_11","unstructured":"Mehlhorn, K. (1984). On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. STACS 1985, Springer."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kiayias, A. (2011). Better Key Sizes (and Attacks) for LWE-Based Encryption. Topics in Cryptology\u2014CT-RSA 2011, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-642-19074-2"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/978-3-319-12160-4_18","article-title":"On the Efficacy of Solving LWE by Reduction to Unique-SVP","volume":"Volume 8565","author":"Lee","year":"2014","journal-title":"Information Security and Cryptology\u2014ICISC 2013"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1287\/moor.12.3.415","article-title":"Minkowski\u2019s Convex Body Theorem and Integer Programming","volume":"12","author":"Kannan","year":"1987","journal-title":"Math. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Benaloh, J. (2014). An Improved Compression Technique for Signatures Based on Learning with Errors. Topics in Cryptology\u2014CT-RSA 2014, Springer.","DOI":"10.1007\/978-3-319-04852-9"},{"key":"ref_16","unstructured":"Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"4213","DOI":"10.1038\/ncomms5213","article-title":"A variational eigenvalue solver on a photonic quantum processor","volume":"5","author":"Peruzzo","year":"2014","journal-title":"Nat. Commun."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1486935","DOI":"10.34133\/2020\/1486935","article-title":"A Full Quantum Eigensolver for Quantum Chemistry Simulations","volume":"2020","author":"Wei","year":"2020","journal-title":"Research"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"032433","DOI":"10.1103\/PhysRevA.103.032433","article-title":"Two quantum Ising algorithms for the shortest-vector problem","volume":"103","author":"Joseph","year":"2021","journal-title":"Phy. Rev. A"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"013361","DOI":"10.1103\/PhysRevResearch.2.013361","article-title":"Not-so-adiabatic quantum computation for the shortest vector problem","volume":"2","author":"Joseph","year":"2020","journal-title":"Phys. Rev. Res."},{"key":"ref_21","first-page":"233","article-title":"Variational quantum solutions to the Shortest Vector Problem","volume":"2022","author":"Albrecht","year":"2022","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01581144","article-title":"Lattice basis reduction: Improved practical algorithms and solving subset sumproblems","volume":"66","author":"Schnorr","year":"1994","journal-title":"Math. Program."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1038\/s42254-021-00348-9","article-title":"Variational quantum algorithms","volume":"3","author":"Cerezo","year":"2021","journal-title":"Nat. Rev. Phys."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"015004","DOI":"10.1103\/RevModPhys.94.015004","article-title":"Noisy intermediate-scale quantum algorithms","volume":"94","author":"Bharti","year":"2022","journal-title":"Rev. Mod. Phys."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Halevi, S. (2009). On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem. Advances in Cryptology-CRYPTO 2009, Springer.","DOI":"10.1007\/978-3-642-03356-8"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"030503","DOI":"10.1088\/2058-9565\/aab822","article-title":"Quantum optimization using variational algorithms on near-term quantum devices","volume":"3","author":"Nikolaj","year":"2018","journal-title":"Quantum Sci. Technol."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"023023","DOI":"10.1088\/1367-2630\/18\/2\/023023","article-title":"The theory of variational hybrid quantum-classical algorithms","volume":"18","author":"Mcclean","year":"2016","journal-title":"New J. Phys."},{"key":"ref_29","unstructured":"Wen, J., and Chang, X.-W. (2015, January 14\u201319). On the KZ Reduction. Proceedings of the IEEE International Symposium on Information Theory (ISIT 2015), Hong Kong, China."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"10736","DOI":"10.1038\/s41598-019-47174-9","article-title":"QuEST and High Performance Simulation of Quantum Computers","volume":"9","author":"Jones","year":"2019","journal-title":"Sci. Rep."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"256","DOI":"10.22331\/q-2020-04-20-256","article-title":"Improving Variational Quantum Optimization using CVaR","volume":"4","author":"Barkoutsos","year":"2020","journal-title":"Quantum"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/10\/1428\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:47:59Z","timestamp":1760143679000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/10\/1428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,8]]},"references-count":31,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["e24101428"],"URL":"https:\/\/doi.org\/10.3390\/e24101428","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,8]]}}}