Variational quantum solutions to the Shortest Vector Problem

Martin R. Albrecht; Miloš Prokop; Yixin Shen; Petros Wallden

doi:10.22331/q-2023-03-02-933

Variational quantum solutions to the Shortest Vector Problem

Martin R. Albrecht¹, Miloš Prokop², Yixin Shen³, and Petros Wallden⁴

¹King's College London and SandboxAQ. email: martin.albrecht@kcl.ac.uk
²University of Edinburgh. email: m.prokop@sms.ed.ac.uk
³Royal Holloway, University of London. email: yixin.shen@rhul.ac.uk
⁴University of Edinburgh. email: petros.wallden@ed.ac.uk

Published:	2023-03-02, volume 7, page 933
Eprint:	arXiv:2202.06757v5
Doi:	https://doi.org/10.22331/q-2023-03-02-933
Citation:	Quantum 7, 933 (2023).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

A fundamental computational problem is to find a shortest non-zero vector in Euclidean lattices, a problem known as the Shortest Vector Problem (SVP). This problem is believed to be hard even on quantum computers and thus plays a pivotal role in post-quantum cryptography. In this work we explore how (efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to solve SVP. Specifically, we map the problem to that of finding the ground state of a suitable Hamiltonian. In particular, (i) we establish new bounds for lattice enumeration, this allows us to obtain new bounds (resp. estimates) for the number of qubits required per dimension for any lattices (resp. random q-ary lattices) to solve SVP; (ii) we exclude the zero vector from the optimization space by proposing (a) a different classical optimisation loop or alternatively (b) a new mapping to the Hamiltonian. These improvements allow us to solve SVP in dimension up to 28 in a quantum emulation, significantly more than what was previously achieved, even for special cases. Finally, we extrapolate the size of NISQ devices that is required to be able to solve instances of lattices that are hard even for the best classical algorithms and find that with approximately $10^3$ noisy qubits such instances can be tackled.

Popular summary

Quantum computers potentially offer speed-ups in solving many problems. Existing encryption schemes, used in everyday life, are based on the assumption that factoring a large number is hard. However, a quantum algorithm due to Shor, can solve this problem using a large fault-tolerant quantum computer efficiently. This would compromise the security of all these communications. Because of this threat, alternative encryption schemes are being considered, where their security relies on assumptions about the hardness of other mathematical problems that are believed to be hard for quantum computers. The most prominent such problem is the Shortest-Vector-Problem (SVP). While SVP is strongly believed to be hard for quantum computers, it is not clear how hard it is, or else, what is the best that a quantum computer (fault-tolerant or not) can do in solving this problem.

In our work we examine how to solve the SVP using quantum computers and algorithms that can be run on exiting or near-term, imperfect, devices. We significantly reduce the number of qubits required to run such algorithms by providing bounds on the coefficients of the shortest-vector and by excluding the zero vector in a more efficient way. We are able to solve SVP for dimension 28 in a simulation, and we extrapolate that the classical record for SVP can be tackled using quantum computers with around one thousand qubits. We note, however, that our results do not invalidate any security claims made by post-quantum candidates as part of current standardisation efforts to replace cryptographic algorithms.

► BibTeX data

@article{Albrecht2023variationalquantum,
  doi = {10.22331/q-2023-03-02-933},
  url = {https://doi.org/10.22331/q-2023-03-02-933},
  title = {Variational quantum solutions to the {S}hortest {V}ector {P}roblem},
  author = {Albrecht, Martin R. and Prokop, Milo{\v{s}} and Shen, Yixin and Wallden, Petros},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {933},
  month = mar,
  year = {2023}
}

► References

[1] Whitfield Diffie and Martin E. Hellman. ``New directions in cryptography''. IEEE Transactions on Information Theory 22, 644–654 (1976).
https://doi.org/10.1109/TIT.1976.1055638

[2] Peter W. Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM J. Comput. 26, 1484–1509 (1997).
https://doi.org/10.1137/S0097539795293172

[3] NIST. ``Post-quantum cryptography standardization''. Available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization.
https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization

[4] Léo Ducas, Marc Stevens, and Wessel P. J. van Woerden. ``Advanced lattice sieving on GPUs, with tensor cores''. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part II. Volume 12697 of LNCS, pages 249–279. Springer, Heidelberg (2021).
https://doi.org/10.1007/978-3-030-77886-6_9

[5] Oded Regev. ``On lattices, learning with errors, random linear codes, and cryptography''. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC. Pages 84–93. ACM Press (2005).
https://doi.org/10.1145/1060590.1060603

[6] A.K. Lenstra, H.W. Lenstra, and Lászlo Lovász. ``Factoring polynomials with rational coefficients''. Math. Ann. 261, 515–534 (1982).
https://doi.org/10.1007/BF01457454

[7] Claus Peter Schnorr. ``A hierarchy of polynomial time lattice basis reduction algorithms''. Theor. Comput. Sci. 53, 201–224 (1987).
https://doi.org/10.5555/2796561.2796598

[8] Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W. Postlethwaite, Fernando Virdia, and Thomas Wunderer. ``Estimate all the LWE, NTRU schemes!''. In Dario Catalano and Roberto De Prisco, editors, Security and Cryptography for Networks - 11th International Conference, SCN 2018, Amalfi, Italy, September 5-7, 2018, Proceedings. Volume 11035 of Lecture Notes in Computer Science, pages 351–367. Springer (2018).
https://doi.org/10.1007/978-3-319-98113-0_19

[9] Ravi Kannan. ``Improved algorithms for integer programming and related lattice problems''. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. Page 193–206. STOC '83New York, NY, USA (1983). Association for Computing Machinery.
https://doi.org/10.1145/800061.808749

[10] Guillaume Hanrot and Damien Stehlé. ``Improved analysis of kannan's shortest lattice vector algorithm''. In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007. Pages 170–186. Berlin, Heidelberg (2007). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-540-74143-5_10

[11] André Chailloux and Johanna Loyer. ``Lattice sieving via quantum random walks''. In Mehdi Tibouchi and Huaxiong Wang, editors, Lattice Sieving via Quantum Random Walks. Pages 63–91. Cham (2021). Springer International Publishing.
https://doi.org/10.1007/978-3-030-92068-5_3

[12] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Quantum random access memory''. Phys. Rev. Lett. 100, 160501 (2008).
https://doi.org/10.1103/PhysRevLett.100.160501

[13] Yoshinori Aono, Phong Q. Nguyen, and Yixin Shen. ``Quantum lattice enumeration and tweaking discrete pruning''. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part I. Volume 11272 of LNCS, pages 405–434. Springer, Heidelberg (2018).
https://doi.org/10.1007/978-3-030-03326-2_14

[14] Martin R. Albrecht, Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehlé, and Weiqiang Wen. ``Faster enumeration-based lattice reduction: Root hermite factor $k^{1/(2k)}$ time $k^{k/8+o(k)}$''. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II. Volume 12171 of LNCS, pages 186–212. Springer, Heidelberg (2020).
https://doi.org/10.1007/978-3-030-56880-1_7

[15] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. ``Variational quantum algorithms''. Nature Reviews Physics (2021).
https://doi.org/10.1038/s42254-021-00348-9

[16] Ian Kivlichan, Jarrod Mcclean, Nathan Wiebe, Craig Gidney, AlÃ¡n Aspuru-Guzik, Garnet Chan, and Ryan Babbush. ``Quantum simulation of electronic structure with linear depth and connectivity''. Physical review letters 120 (2017).
https://doi.org/10.1103/PhysRevLett.120.110501

[17] Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim, and Henry Yuen. ``Exploring entanglement and optimization within the hamiltonian variational ansatz''. PRX Quantum 1, 020319 (2020).
https://doi.org/10.1103/PRXQuantum.1.020319

[18] Andrew Lucas. ``Ising formulations of many np problems''. Frontiers in Physics 2, 5 (2014).
https://doi.org/10.3389/fphy.2014.00005

[19] Alba Cervera-Lierta, Jakob S. Kottmann, and Alán Aspuru-Guzik. ``Meta-variational quantum eigensolver: Learning energy profiles of parameterized hamiltonians for quantum simulation''. PRX Quantum 2, 020329 (2021).
https://doi.org/10.1103/PRXQuantum.2.020329

[20] B Koczor, S Endo, T Jones, Y Matsuzaki, and SC Benjamin. ``Variational-state quantum metrology''. New Journal of Physics 22 (2020).
https://doi.org/10.1088/1367-2630/ab965e

[21] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nature Communications 5 (2014).
https://doi.org/10.1038/ncomms5213

[22] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. ``The theory of variational hybrid quantum-classical algorithms''. New Journal of Physics 18, 023023 (2016).
https://doi.org/10.1088/1367-2630/18/2/023023

[23] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. ``The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size''. Quantum 6, 759 (2022).
https://doi.org/10.22331/q-2022-07-07-759

[24] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori, and William D Oliver. ``Perspectives of quantum annealing: methods and implementations''. Reports on Progress in Physics 83, 054401 (2020).
https://doi.org/10.1088/1361-6633/ab85b8

[25] Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, and Stefan Woerner. ``Improving variational quantum optimization using cvar''. Quantum 4, 256 (2020).
https://doi.org/10.22331/q-2020-04-20-256

[26] Ioannis Kolotouros and Petros Wallden. ``Evolving objective function for improved variational quantum optimization''. Phys. Rev. Res. 4, 023225 (2022).
https://doi.org/10.1103/PhysRevResearch.4.023225

[27] Sami Boulebnane and Ashley Montanaro. ``Solving boolean satisfiability problems with the quantum approximate optimization algorithm'' (2022). https://doi.org/10.48550/arXiv.2208.06909.
https://doi.org/10.48550/arXiv.2208.06909

[28] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem'' (2014). arXiv:1412.6062. https://doi.org/10.48550/arXiv.1412.6062.
https://doi.org/10.48550/arXiv.1412.6062
arXiv:1412.6062

[29] David Joseph, Alexandros Ghionis, Cong Ling, and Florian Mintert. ``Not-so-adiabatic quantum computation for the shortest vector problem''. Phys. Rev. Research 2, 013361 (2020).
https://doi.org/10.1103/PhysRevResearch.2.013361

[30] David Joseph, Adam Callison, Cong Ling, and Florian Mintert. ``Two quantum ising algorithms for the shortest-vector problem''. Phys. Rev. A 103, 032433 (2021).
https://doi.org/10.1103/PhysRevA.103.032433

[31] Gérard Maze. ``Natural density distribution of hermite normal forms of integer matrices''. Journal of Number Theory 131, 2398–2408 (2010).
https://doi.org/10.1016/j.jnt.2011.06.010

[32] Oscar Higgott, Daochen Wang, and Stephen Brierley. ``Variational Quantum Computation of Excited States''. Quantum 3, 156 (2019).
https://doi.org/10.22331/q-2019-07-01-156

[33] Yifeng Rocky Zhu, David Joseph, Cong Ling, and Florian Mintert. ``Iterative quantum optimization with an adaptive problem hamiltonian for the shortest vector problem''. Phys. Rev. A 106, 022435 (2022).
https://doi.org/10.1103/PhysRevA.106.022435

[34] Martin R. Albrecht, Shi Bai, Jianwei Li, and Joe Rowell. ``Lattice reduction with approximate enumeration oracles - practical algorithms and concrete performance''. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part II. Volume 12826 of LNCS, pages 732–759. Virtual Event (2021). Springer, Heidelberg.
https://doi.org/10.1007/978-3-030-84245-1_25

[35] Jinming Wen and Xiao-Wen Chang. ``On the KZ reduction''. IEEE Trans. Inf. Theory 65, 1921–1935 (2019).
https://doi.org/10.1109/TIT.2018.2868945

[36] ``Svp challenge''. https://www.latticechallenge.org/svp-challenge/.
https://www.latticechallenge.org/svp-challenge/

[37] Phong Q. Nguyen and Brigitte Vallée, editors. ``The LLL algorithm - survey and applications''. ISC. Springer, Heidelberg. (2010).
https://doi.org/10.1007/978-3-642-02295-1

[38] Miklós Ajtai. ``Generating hard instances of lattice problems (extended abstract)''. In 28th ACM STOC. Pages 99–108. ACM Press (1996).
https://doi.org/10.1145/237814.237838

[39] Alexander J McCaskey, Dmitry I Lyakh, Eugene F Dumitrescu, Sarah S Powers, and Travis S Humble. ``XACC: a system-level software infrastructure for heterogeneous quantum–classical computing''. Quantum Science and Technology 5, 024002 (2020).
https://doi.org/10.1088/2058-9565/ab6bf6

[40] Tyson Jones, Anna Brown, Ian Bush, and Simon C. Benjamin. ``Quest and high performance simulation of quantum computers''. Scientific Reports 9 (2019).
https://doi.org/10.1038/s41598-019-47174-9

[41] Herbert Robbins. ``A remark on stirling's formula''. The American Mathematical Monthly 62, 26–29 (1955).
https://doi.org/10.2307/2308012

Cited by

[1] Salahuddin Abdul Rahman, Özkan Karabacak, and Rafal Wisniewski, "Feedback-based quantum strategies for constrained combinatorial optimization problems", Future Generation Computer Systems 174, 107979 (2026).

[2] Christian Porter, Edmund Dable-Heath, and Cong Ling, "A new bound for the orthogonality defect of HKZ reduced lattices", Research in Number Theory 10 3, 65 (2024).

[3] Trevor Nestor, "Theoretical Approaches to Solving the Shortest Vector Problem in NP-Hard Lattice-Based Cryptography with Post-SUSY Theories of Quantum Gravity in Polynomial Time by Orch-Or", IPI Letters O1 (2025).

[4] Júlia Barberà-Rodríguez, Nicolas Gama, Anand Kumar Narayanan, and David Joseph, "Finding dense sublattices as low energy states of a Hamiltonian", Physical Review Research 6 4, 043279 (2024).

[5] Qiqi Xie, Hong Zhang, Liqiang Wang, Miao Wang, Wanqing Wu, and Yilong Liu, "SecureLoc: A fully homomorphic encryption-based privacy protection scheme for location-based services", Journal of Information Security and Applications 93, 104190 (2025).

[6] Mathieu Bozzio, Claude Crépeau, Petros Wallden, and Philip Walther, "Quantum cryptography beyond key distribution: Theory and experiment", Reviews of Modern Physics 97 4, 045006 (2025).

[7] Miloš Prokop, Petros Wallden, and David Joseph, "Grover's Oracle for the Shortest Vector Problem and Its Application in Hybrid Classical–Quantum Solvers", IEEE Transactions on Quantum Engineering 6, 1 (2025).

[8] Ben Priestley and Petros Wallden, "A practically scalable approach to the closest vector problem for sieving via QAOA with fixed angles", Quantum Science and Technology 11 2, 025018 (2026).

[9] Zi-Wen Huang, Xiao-Hui Ni, Jia-Cheng Fan, Su-Juan Qin, Wei Huang, Bing-Jie Xu, and Fei Gao, "Iterative partition-search variational quantum algorithm for solving the shortest-vector problem", Physical Review A 113 3, 032601 (2026).

[10] Matvii Kistaiev and Andrii Fesenko, 2024 IEEE 5th International Conference on Advanced Trends in Information Theory (ATIT) 252 (2024) ISBN:979-8-3315-1016-9.

[11] Xiaokai Hou, Guoqing Zhou, Shan Jin, Yang Li, Wei Huang, Ao Sun, Xiaoting Wang, and Bingjie Xu, "Efficient variational quantum Korkin-Zolotarev algorithm for solving shortest-vector problems", Physical Review A 113 4, 042611 (2026).

[12] Miloš Prokop and Petros Wallden, "Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers", IEEE Transactions on Quantum Engineering 6, 1 (2025).

[13] Muxi Zheng, Jinfeng Zeng, Wentao Yang, Pei-Jie Chang, Quanfeng Lu, Bao Yan, Haoran Zhang, Min Wang, ShiJie Wei, and Gui-Lu Long, "Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices", Communications Physics 8 1, 208 (2025).

[14] Yilong Liu, Hong Zhang, Miao Wang, Qiqi Xie, and Zhibo Sun, "AntidoteFL: Enhancing defense against poisoning attacks in federated learning", Computer Networks 269, 111427 (2025).

[15] Edmund Dable-Heath, Laura Casas, Victor Hertz, Christian Porter, Florian Mintert, and Cong Ling, "Quantum algorithmic solutions to the shortest vector problem on simulated coherent Ising machines", arXiv:2304.04075, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-17 08:11:03) and SAO/NASA ADS (last updated successfully 2026-07-16 18:47:42). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-07-17 08:11:08: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.