Projects per year
Abstract / Description of output
A fundamental computational problem is to find a shortest nonzero 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 postquantum 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 qary 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.
10^3 noisy qubits such instances can be tackled.
Original language  English 

Pages (fromto)  116 
Number of pages  16 
Journal  Quantum 
Volume  7 
Issue number  933 
DOIs  
Publication status  Published  2 Mar 2023 
Fingerprint
Dive into the research topics of 'Variational quantum solutions to the Shortest Vector Problem'. Together they form a unique fingerprint.
EPSRC Hub in Quantum Computing and Simulation
Kashefi, E., Arapinis, M., Heunen, C. & Wallden, P.
1/12/19 → 30/11/24
Project: Research
