Quantum enumeration approaches to solving the shortest vector problem

Abstract

The Shortest Vector Problem (SVP) is a fundamental computational problem believed to be hard for both classical and quantum computers. Its hardness underpins security of lattice-based cryptographic (LBC) schemes, a leading class of post-quantum cryptographic proposals. The study of the computational hardness of SVP is therefore of crucial importance for assessing the resilience of cryptographic schemes of post-quantum era. Our focus is on enumeration approaches to SVP, algorithms that systematically explore lattice points within bounded regions to find the shortest vector, which are especially well-suited for optimisation frameworks with variational quantum algorithms (VQAs), the leading algorithmic candidates for Noisy-Intermediate Scale Quantum (NISQ) era. To overcome quantum resource scarcity of NISQ, we improve on a method to encode SVP as a ground state of an Ising spin Hamiltonian operator by (i.) providing theoretical analysis on quantum resource requirements, (ii.) proposing techniques to avoid convergence to a trivial, the zero solution, of SVP. Our results indicate that with 103 logical qubits, the SVP instances, which are at the limit of what classical algorithms could handle, can be addressed. However, the noise- and optimiser-related issues are expected to significantly impact the performance of algorithms in practice. For this reason, we use theoretical analysis and classical emulation to experimentally analyse its specifics and performance when SVP is being addressed by: (i.) the famous representatives of VQAs: on Variational Quantum Eigensolver (VQE), Quantum Approximate Optimisation Algorithm (QAOA) or its generalised Quantum Alternating Operator Ansatz relative, (ii.) The novel NISQ algorithm which mimics adiabatic quantum computation via parameterised quantum circuits by Kolotouros et al., (iii.) The Grover’s algorithm for the more distant fault-tolerant quantum era, (iv.) pre-trained VQAs for which we design a training and evaluation method that suits well the SVP problem. While our findings do not invalidate any LBC standards selected by US National Institute for Standards and Technology, we believe they serve an important foundation for future quantum cryptanalysis approaches to LBC. To facilitate further research we propose several useful techniques: e.g. novel techniques to map SVP into Hamiltonian formulations, Hermite-Korkine-Zolotarev (HKZ) basis reduction via NISQ enumeration for which we prove 3 2 log2 (n)−2.26n+O(logn) qubit requirements for n dimensional lattices, heuristical upper bound on performance of QAOA based SVP solver, generation of small-rank q-ary lattices (for any prime q) that preserve the scaled-down hardness of cryptographically relevant lattice instances, or practical construction of Grover’s algorithm oracle for SVP. All the relevant lattice operations and algorithmic quantum approaches are part of FastVQA and LattiQ software libraries that have been developed alongside the project. They offer fast clas sical emulation capabilities on possibly distributed, high memory computing clusters and provide a robust foundation for continuing works in the intersection of research directions of VQAs and LBC.