Paper 2022/233

Variational quantum solutions to the Shortest Vector Problem

Martin R. Albrecht, King’s College London and SandboxAQ
Miloš Prokop, University of Edinburgh
Yixin Shen, Royal Holloway University of London
Petros Wallden, University of Edinburgh
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 ≈ 10^3 noisy qubits such instances can be tackled.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Quantum Journal
Keywords
Shortest Vector ProblemVariational Quantum Algorithms
Contact author(s)
martin albrecht @ kcl ac uk
m prokop @ sms ed ac uk
yixin shen @ rhul ac uk
petros wallden @ ed ac uk
History
2023-02-21: last of 2 revisions
2022-02-25: received
See all versions
Short URL
https://ia.cr/2022/233
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/233,
      author = {Martin R.  Albrecht and Miloš Prokop and Yixin Shen and Petros Wallden},
      title = {Variational quantum solutions to the Shortest Vector Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2022/233},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/233}},
      url = {https://eprint.iacr.org/2022/233}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.