Finding dense sublattices as low energy states of a Hamiltonian

Abstract

Lattice-based cryptography has emerged as one of the most prominent candidates for postquantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest nonzero vector in a given lattice. It is fundamental to lattice-based cryptography and believed to be hard even for quantum computers. We study a natural generalization of the SVP known as the K-Densest Sublattice Problem (K-DSP): to find the densest K-dimensional sublattice of a given lattice. We formulate K-DSP as finding the first excited state of a Z-basis Hamiltonian, making K-DSP amenable to investigation via an array of quantum algorithms, including Grover search, quantum Gibbs sampling, adiabatic, and variational quantum algorithms. The complexity of the algorithms depends on the basis through which the input lattice is presented. We present a classical polynomial-time algorithm that takes an arbitrary input basis and preprocesses it into inputs suited to quantum algorithms. With preprocessing, we prove that O(KN^{2}) qubits suffice for solving K-DSP for N-dimensional input lattices. We empirically demonstrate the performance of a quantum approximate optimization algorithm K-DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of K-DSP in relation to the SVP, to see if there is a reason to build postquantum cryptography on K-DSP. We devise a quantum algorithm that solves K-DSP with runtime exponent (5KNlog_{2}N)/2. Therefore, for fixed K, K-DSP is no more than polynomially harder than the SVP. The central insight we use is similar in spirit to those underlying the best-known classical K-DSP algorithm due to Dadush and Micciancio. Whether the exponential dependence on K can be lowered remains an open question.