Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers

Finding the shortest non-zero vector on a lattice is a fundamental problem in lattices that is believed to be hard both for classical and quantum computers. Two of the three standardised by NIST post-quantum cryptosystems rely on its hardness. Research on theoretical and practical performance of quantum algorithms to solve the Shortest Vector Problem (SVP) is crucial to establish confidence in those new standards. Exploring the capabilities that Variational Quantum Algorithms (VQA) that can run on Noisy Intermediate Scale Quantum (NISQ) devices have in solving SVP has been an active area of research. The qubit-requirement for doing so has been analysed and demonstrated that it is plausible to encode SVP on the ground state of a Hamiltonian in an efficient way. Due to the heuristic nature of VQAs no analysis of the performance and specifically of the time complexity of those approaches for scales beyond the non-interesting classically simulatable sizes has been performed. In this paper, motivated by Boulebnane and Montanaro [1] work on the k-SAT problem, we propose to use angle pretraining of the Quantum Approximate Optimisation Algorithm (QAOA) for SVP and we demonstrate that QAOA with fixed angles performs well on much larger instances than those used in training. Avoiding the limitations that arise due to the use of optimiser, we are able to extrapolate the observed performance and we observe the probability of success scaling as $2^{-0.695n}$ with $n$ being dimensionality of the search space for a depth $p=3$ pre-trained QAOA algorithm. By repeating the algorithm, we get heuristic time complexity $O(2^{0.695n})$ to solve the problem with high probability, a bit worse than the fault-tolerant Grover approach of $O(2^{0.5n})$ . On the other hand, both the number of qubits, and most importantly the depth of each quantum computation, are considerably better in our approach – Grover requires exponential depth, while each run of constant $p$ fixed-angles QAOA requires polynomial depth. Further, we analyse the performance of QAOA in solving approximate-SVP, a version of the problem that one seeks a multiplicative approximation to the shortest vector. As a side result, we propose a novel method to avoid the zero vector solution to SVP without introducing more logical qubits. This improves upon the previous works as it results in more space efficient encoding of SVP on NISQ architectures without ignoring the zero vector problem.