Abstract The shortest vector problem (SVP) is one of the lattice problems and is the mathematical basis for lattice-based cryptography, which is expected to be post-quantum cryptography. The SVP can be mapped onto the Ising problem, which in principle can be solved by quantum annealing (QA). However, one issue in solving the SVP using QA is that the solution of the SVP corresponds to the first excited state of the problem Hamiltonian. Therefore, QA, which searches for ground states, cannot provide a solution with high probability. In this paper, we propose to adopt an excited-state search of the QA to solve the shortest vector problem. We numerically show that the excited-state search provides a solution with a higher probability than the ground-state search.
Abstract Lattice-based cryptographic regimes are the most promising quantum-resistant cryptographic algorithms, whose security depends on the difficulty of the SVP. Enumeration algorithms are the most basic and hopeful algorithms instantiated for solving SVPs, and are often used in public key cryptanalysis or as subroutines of lattice reduction algorithms. In this paper, we show how to speed up enumeration with the idea of nested search: if N is the number of nodes in the enumeration tree and T is the time required to process a node, our quantum enumeration can find the shortest vector on the lattice in time T⋅N . This is applied to the two most efficient types of enumeration: cylinder pruning as well as discrete pruning. The core idea of the algorithm is to reduce the size of the search space by transforming the original problem into a constraint-satisfiable problem, using the pruning conditions of the above two enumerations as constraints, and embedding the search for all possible solutions at the next level of the enumeration tree into the space of partially satisfied solutions at the previous level. Next, we accelerate this process using a quantum search algorithm. Compared to the work of bib24, we further reduce the time complexity of the algorithm with multiplication factor $\sqrt{T} $ by the quantum nested search algorithm.