{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T19:59:41Z","timestamp":1773431981344,"version":"3.50.1"},"reference-count":41,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,3,2]],"date-time":"2023-03-02T00:00:00Z","timestamp":1677715200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/T001062\/1"],"award-info":[{"award-number":["EP\/T001062\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/T026715\/1"],"award-info":[{"award-number":["EP\/T026715\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/S020330\/1"],"award-info":[{"award-number":["EP\/S020330\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/S02087X\/1"],"award-info":[{"award-number":["EP\/S02087X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union Horizon 2020","award":["Research and Innovation Program Grant 780701"],"award-info":[{"award-number":["Research and Innovation Program Grant 780701"]}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/T517811\/1"],"award-info":[{"award-number":["EP\/T517811\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["d EP\/W02778X\/1"],"award-info":[{"award-number":["d EP\/W02778X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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<\/mml:mn>3<\/mml:mn><\/mml:msup><\/mml:math> noisy qubits such instances can be tackled.<\/jats:p>","DOI":"10.22331\/q-2023-03-02-933","type":"journal-article","created":{"date-parts":[[2023,3,2]],"date-time":"2023-03-02T15:58:18Z","timestamp":1677772698000},"page":"933","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":13,"title":["Variational quantum solutions to the Shortest Vector Problem"],"prefix":"10.22331","volume":"7","author":[{"given":"Martin R.","family":"Albrecht","sequence":"first","affiliation":[{"name":"King's College London and SandboxAQ. email: martin.albrecht@kcl.ac.uk"}]},{"given":"Milo\u0161","family":"Prokop","sequence":"additional","affiliation":[{"name":"University of Edinburgh. email: m.prokop@sms.ed.ac.uk"}]},{"given":"Yixin","family":"Shen","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London. email: yixin.shen@rhul.ac.uk"}]},{"given":"Petros","family":"Wallden","sequence":"additional","affiliation":[{"name":"University of Edinburgh. email: petros.wallden@ed.ac.uk"}]}],"member":"9598","published-online":{"date-parts":[[2023,3,2]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Whitfield Diffie and Martin E. Hellman. ``New directions in cryptography''. IEEE Transactions on Information Theory 22, 644\u2013654 (1976).","DOI":"10.1109\/TIT.1976.1055638"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Peter W. Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM J. Comput. 26, 1484\u20131509 (1997).","DOI":"10.1137\/S0097539795293172"},{"key":"2","unstructured":"NIST. ``Post-quantum cryptography standardization''. Available at https:\/\/csrc.nist.gov\/projects\/post-quantum-cryptography\/post-quantum-cryptography-standardization."},{"key":"3","doi-asserted-by":"publisher","unstructured":"L\u00e9o Ducas, Marc Stevens, and Wessel P. J. van Woerden. ``Advanced lattice sieving on GPUs, with tensor cores''. In Anne Canteaut and Fran\u00e7ois-Xavier Standaert, editors, EUROCRYPT 2021, Part II. Volume 12697 of LNCS, pages 249\u2013279. Springer, Heidelberg (2021).","DOI":"10.1007\/978-3-030-77886-6_9"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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\u201393. ACM Press (2005).","DOI":"10.1145\/1060590.1060603"},{"key":"5","doi-asserted-by":"publisher","unstructured":"A.K. Lenstra, H.W. Lenstra, and L\u00e1szlo Lov\u00e1sz. ``Factoring polynomials with rational coefficients''. Math. Ann. 261, 515\u2013534 (1982).","DOI":"10.1007\/BF01457454"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Claus Peter Schnorr. ``A hierarchy of polynomial time lattice basis reduction algorithms''. Theor. Comput. Sci. 53, 201\u2013224 (1987).","DOI":"10.5555\/2796561.2796598"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u2013367. Springer (2018).","DOI":"10.1007\/978-3-319-98113-0_19"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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\u2013206. STOC '83New York, NY, USA (1983). Association for Computing Machinery.","DOI":"10.1145\/800061.808749"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Guillaume Hanrot and Damien Stehl\u00e9. ``Improved analysis of kannan's shortest lattice vector algorithm''. In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007. Pages 170\u2013186. Berlin, Heidelberg (2007). Springer Berlin Heidelberg.","DOI":"10.1007\/978-3-540-74143-5_10"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Andr\u00e9 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\u201391. Cham (2021). Springer International Publishing.","DOI":"10.1007\/978-3-030-92068-5_3"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Quantum random access memory''. Phys. Rev. Lett. 100, 160501 (2008).","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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\u2013434. Springer, Heidelberg (2018).","DOI":"10.1007\/978-3-030-03326-2_14"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Martin R. Albrecht, Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehl\u00e9, 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\u2013212. Springer, Heidelberg (2020).","DOI":"10.1007\/978-3-030-56880-1_7"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/s42254-021-00348-9"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Ian Kivlichan, Jarrod Mcclean, Nathan Wiebe, Craig Gidney, Al\u00c3\u00a1n Aspuru-Guzik, Garnet Chan, and Ryan Babbush. ``Quantum simulation of electronic structure with linear depth and connectivity''. Physical review letters 120 (2017).","DOI":"10.1103\/PhysRevLett.120.110501"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PRXQuantum.1.020319"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Andrew Lucas. ``Ising formulations of many np problems''. Frontiers in Physics 2, 5 (2014).","DOI":"10.3389\/fphy.2014.00005"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Alba Cervera-Lierta, Jakob S. Kottmann, and Al\u00e1n Aspuru-Guzik. ``Meta-variational quantum eigensolver: Learning energy profiles of parameterized hamiltonians for quantum simulation''. PRX Quantum 2, 020329 (2021).","DOI":"10.1103\/PRXQuantum.2.020329"},{"key":"19","doi-asserted-by":"publisher","unstructured":"B Koczor, S Endo, T Jones, Y Matsuzaki, and SC Benjamin. ``Variational-state quantum metrology''. New Journal of Physics 22 (2020).","DOI":"10.1088\/1367-2630\/ab965e"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Al\u00e1n Aspuru-Guzik, and Jeremy L. O'Brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nature Communications 5 (2014).","DOI":"10.1038\/ncomms5213"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Al\u00e1n Aspuru-Guzik. ``The theory of variational hybrid quantum-classical algorithms''. New Journal of Physics 18, 023023 (2016).","DOI":"10.1088\/1367-2630\/18\/2\/023023"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.22331\/q-2022-07-07-759"},{"key":"23","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088\/1361-6633\/ab85b8"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, and Stefan Woerner. ``Improving variational quantum optimization using cvar''. Quantum 4, 256 (2020).","DOI":"10.22331\/q-2020-04-20-256"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Ioannis Kolotouros and Petros Wallden. ``Evolving objective function for improved variational quantum optimization''. Phys. Rev. Res. 4, 023225 (2022).","DOI":"10.1103\/PhysRevResearch.4.023225"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Sami Boulebnane and Ashley Montanaro. ``Solving boolean satisfiability problems with the quantum approximate optimization algorithm'' (2022). https:\/\/doi.org\/10.48550\/arXiv.2208.06909.","DOI":"10.48550\/arXiv.2208.06909"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.1412.6062"},{"key":"28","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevResearch.2.013361"},{"key":"29","doi-asserted-by":"publisher","unstructured":"David Joseph, Adam Callison, Cong Ling, and Florian Mintert. ``Two quantum ising algorithms for the shortest-vector problem''. Phys. Rev. A 103, 032433 (2021).","DOI":"10.1103\/PhysRevA.103.032433"},{"key":"30","doi-asserted-by":"publisher","unstructured":"G\u00e9rard Maze. ``Natural density distribution of hermite normal forms of integer matrices''. Journal of Number Theory 131, 2398\u20132408 (2010).","DOI":"10.1016\/j.jnt.2011.06.010"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Oscar Higgott, Daochen Wang, and Stephen Brierley. ``Variational Quantum Computation of Excited States''. Quantum 3, 156 (2019).","DOI":"10.22331\/q-2019-07-01-156"},{"key":"32","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.106.022435"},{"key":"33","doi-asserted-by":"publisher","unstructured":"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\u2013759. Virtual Event (2021). Springer, Heidelberg.","DOI":"10.1007\/978-3-030-84245-1_25"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Jinming Wen and Xiao-Wen Chang. ``On the KZ reduction''. IEEE Trans. Inf. Theory 65, 1921\u20131935 (2019).","DOI":"10.1109\/TIT.2018.2868945"},{"key":"35","unstructured":"``Svp challenge''. https:\/\/www.latticechallenge.org\/svp-challenge\/."},{"key":"36","doi-asserted-by":"publisher","unstructured":"Phong Q. Nguyen and Brigitte Vall\u00e9e, editors. ``The LLL algorithm - survey and applications''. ISC. Springer, Heidelberg. (2010).","DOI":"10.1007\/978-3-642-02295-1"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Mikl\u00f3s Ajtai. ``Generating hard instances of lattice problems (extended abstract)''. In 28th ACM STOC. Pages 99\u2013108. ACM Press (1996).","DOI":"10.1145\/237814.237838"},{"key":"38","doi-asserted-by":"publisher","unstructured":"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\u2013classical computing''. Quantum Science and Technology 5, 024002 (2020).","DOI":"10.1088\/2058-9565\/ab6bf6"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Tyson Jones, Anna Brown, Ian Bush, and Simon C. Benjamin. ``Quest and high performance simulation of quantum computers''. Scientific Reports 9 (2019).","DOI":"10.1038\/s41598-019-47174-9"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Herbert Robbins. ``A remark on stirling's formula''. The American Mathematical Monthly 62, 26\u201329 (1955).","DOI":"10.2307\/2308012"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-03-02-933\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,3,2]],"date-time":"2023-03-02T15:58:34Z","timestamp":1677772714000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-03-02-933\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,2]]},"references-count":41,"URL":"https:\/\/doi.org\/10.22331\/q-2023-03-02-933","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,2]]},"article-number":"933"}}