Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers

Abstract

The shortest vector problem (SVP) is central to the security of lattice-based cryptography, forming the foundation of two of the three NIST-standardized postquantum cryptosystems. Understanding how quantum algorithms perform on SVP is vital for assessing the long-term security of these schemes. In particular, variational quantum algorithms (VQAs) designed for noisy intermediate-scale quantum (NISQ) devices offer a heuristic yet practical approach. However, due to their heuristic nature, their performance and time complexity at nontrivial scales remain poorly understood. In this work, we propose angle pretraining for the quantum approximate optimization algorithm (QAOA) applied to SVP. We show that QAOA with fixed pretrained angles generalizes effectively to larger problem sizes, surpassing the scale limitations of prior training-based methods by eliminating dependence on classical optimizers, enabling to systematically extrapolate performance trends. Our results indicate that the probability of success scales as <inline-formula><tex-math notation="LaTeX">$2^{-0.695n}$</tex-math></inline-formula> for depth <inline-formula><tex-math notation="LaTeX">$p = 3$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> is the lattice dimension. Repetition of the algorithm thus yields an estimated heuristic time complexity of <inline-formula><tex-math notation="LaTeX">$O(2^{0.695n})$</tex-math></inline-formula> for solving SVP with high probability—slightly worse than the Grover-based fault-tolerant bound of <inline-formula><tex-math notation="LaTeX">$O(2^{0.5n})$</tex-math></inline-formula>, but achieved with far lower quantum resource requirements. Unlike Grover's algorithm, which requires exponential circuit depth, our constant-depth fixed-angle QAOA approach scales polynomially with qubit count. Additionally, we introduce a space-efficient encoding of SVP that avoids the zero-vector solution without extra logical qubits, improving prior NISQ implementations in both scalability and efficiency.