Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Quantum nested search for the shortest vector problem

Runxi Cao, Baocang Wang, Juntao Gao

Published Jul 3, 2025• 0 citations
Publisher
DOI
10.1103/dw23-dvr1

Related papers

Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

arXiv:1301.6176•Lecture notes in computer science•Jan 1, 2013•28 citations

Nested Quantum Search and NP-Hard Problems

Nicolas J. Cerf, Lov K. Grover, Colin P. Williams

Applicable Algebra in Engineering Communication and Computing•May 1, 2000•22 citations

On the Practicality of Quantum Sieving Algorithms for the Shortest Vector Problem

João Fernando Doriguello, George Giapitzakis, Alessandro Luongo +1 more

arXiv:2410.13759•Lecture notes in computer science•Jan 1, 2026•7 citations

Fine-Grained Hardness of Unique Shortest Vector Problem

Baolong Jin, Rui Xue

•Jan 1, 2023•0 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.

arXiv:2209.03721•Japanese Journal of Applied Physics•Feb 8, 2023•7 citations

Quantum Nested Search for Lattice Enumeration

Runxi Cao, Baocang Wang, Juntao Gao

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 \(\sqrt{T\cdot 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.

•Jan 24, 2024•0 citations
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\sqrt{T\cdot N}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.