Abstract By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time 21.799n+o(n), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehle ́ and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.286n+o(n), improving upon the classical time complexity of 20.337n+o(n) of Laarhoven. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem. Keywords lattices · shortest vector problem · sieving · quantum search 1Abstract By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time 21.799n+o(n), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehle ́ and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.286n+o(n), improving upon the classical time complexity of 20.337n+o(n) of Laarhoven. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem. Keywords lattices · shortest vector problem · sieving · quantum search 1

Jan 1, 20141 citation

Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time $2^{1.799n + o(n)}$ , improving upon the classical time complexities of $2^{2.465n + o(n)}$ of Pujol and Stehlé and the $2^{2n + o(n)}$ of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time $2^{0.268n + o(n)}$ , improving upon the classical time complexity of $2^{0.298n + o(n)}$ of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time $$2^{1.799n + o(n)}$$ , improving upon the classical time complexities of $$2^{2.465n + o(n)}$$ of Pujol and Stehlé and the $$2^{2n + o(n)}$$ of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time $$2^{0.268n + o(n)}$$ , improving upon the classical time complexity of $$2^{0.298n + o(n)}$$ of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.

Designs Codes and CryptographyApr 13, 201591 citations

Analysis of the shortest vector problems with quantum annealing to search the excited states

Katsuki Ura, Takashi Imoto, Tetsuro Nikuni +2 more

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 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.

arXiv:2209.03721Japanese Journal of Applied PhysicsFeb 8, 20235 citations

2^{1.799n + o(n)}

, improving upon the classical time complexities of

2^{2.465n + o(n)}

of Pujol and Stehlé and the

2^{2n + o(n)}

of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time

2^{0.268n + o(n)}

, improving upon the classical time complexity of

2^{0.298n + o(n)}

of Laarhoven and De Weger. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.