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

Computational Complexity

Hardness of Approximating the Closest Vector Problem with Pre-Processing

Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi

Published Dec 1, 2011• 15 citations
Publisher
DOI
10.1007/s00037-011-0031-3

Related papers

Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle

Chandan K. Dubey, Thomas Holenstein

arXiv:1106.2619•Lecture notes in computer science•Jan 1, 2011•6 citations

Hardness of Euclidean Closest Vector within n1/8−ϵ and Binary Nearest Codeword within n1/4−ϵ

Zhao Song

•Jan 1, 2026•0 citations

A practically scalable approach to the closest vector problem for sieving via QAOA with fixed angles

Ben Priestley, Petros Wallden

Abstract The NP-hardness of the closest vector problem (CVP) is an important basis for quantum-secure cryptography, in much the same way that integer factorisation’s conjectured hardness is at the foundation of cryptosystems like RSA. Recent work with heuristic quantum algorithms (Yan et al 2022 arXiv: 2212.12372 [quant-ph]) indicates the possibility to find close approximations to (constrained) CVP instances that could be incorporated within fast sieving approaches for factorisation. This work explores both the practicality and scalability of the proposed heuristic approach to explore the potential for a quantum advantage for approximate CVP, without regard for the subsequent factoring claims. We also extend the proposal to include an antecedent ‘pre-training’ scheme to find and fix a set of parameters that generalise well to increasingly large lattices, which both optimises the scalability of the algorithm, and permits direct numerical analyses. Our results further indicate a noteworthy quantum speed-up for lattice problems obeying a certain ‘prime’ structure, approaching fifth order advantage for quantum approximate optimisation algorithm of fixed depth p = 10 compared to classical brute-force, motivating renewed discussions about the necessary lattice dimensions for quantum-secure cryptosystems in the near-term.

arXiv:2503.08403•Quantum Science and Technology•Mar 3, 2026•1 citation

Fine-Grained Hardness of Unique Shortest Vector Problem

Baolong Jin, Rui Xue

•Jan 1, 2023•0 citations

On the Limits of Nonapproximability of Lattice Problems

Oded Goldreich, Shafi Goldwasser

We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of n , of optimization problems in integer lattices, specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice (for CVP) and an interactive protocol showing that the shortest-lattice-vector is long (for SVP). Furthermore, these interactive proof systems are honest-verifier perfect zero-knowledge. We conclude that approximating CVP (resp., SVP) within a factor of n is in N P ∩co A M . Thus, it seems unlikely that approximating these problems to within a n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica 10 , 333–348), Håstad (1988, Combinatorica 8 , 75–81), and Banaszczyk (1993, Math. Annal. 296 , 625–635) showed that the gap problem corresponding to approximating CVP (resp., SVP) within n is in N P ∩co N P . On the other hand, Arora et al. (1997, J. Comput. System Sci. 54 , 317–331) showed that the gap problem corresponding to approximating CVP within 2 log 0.999 n is quasi-NP-hard.

Journal of Computer and System Sciences•Jan 1, 1998•231 citations

The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations

Sanjeev Arora, László Babai, Jacques Stern +1 more

Journal of Computer and System Sciences•Apr 1, 1997•346 citations
Abstract The NP-hardness of the closest vector problem (CVP) is an important basis for quantum-secure cryptography, in much the same way that integer factorisation’s conjectured hardness is at the foundation of cryptosystems like RSA. Recent work with heuristic quantum algorithms (Yan et al 2022 arXiv: 2212.12372 [quant-ph]) indicates the possibility to find close approximations to (constrained) CVP instances that could be incorporated within fast sieving approaches for factorisation. This work explores both the practicality and scalability of the proposed heuristic approach to explore the potential for a quantum advantage for approximate CVP, without regard for the subsequent factoring claims. We also extend the proposal to include an antecedent ‘pre-training’ scheme to find and fix a set of parameters that generalise well to increasingly large lattices, which both optimises the scalability of the algorithm, and permits direct numerical analyses. Our results further indicate a noteworthy quantum speed-up for lattice problems obeying a certain ‘prime’ structure, approaching fifth order advantage for quantum approximate optimisation algorithm of fixed depth p = 10 compared to classical brute-force, motivating renewed discussions about the necessary lattice dimensions for quantum-secure cryptosystems in the near-term.
We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of n , of optimization problems in integer lattices, specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice (for CVP) and an interactive protocol showing that the shortest-lattice-vector is long (for SVP). Furthermore, these interactive proof systems are honest-verifier perfect zero-knowledge. We conclude that approximating CVP (resp., SVP) within a factor of n is in N P ∩co A M . Thus, it seems unlikely that approximating these problems to within a n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica 10 , 333–348), Håstad (1988, Combinatorica 8 , 75–81), and Banaszczyk (1993, Math. Annal. 296 , 625–635) showed that the gap problem corresponding to approximating CVP (resp., SVP) within n is in N P ∩co N P . On the other hand, Arora et al. (1997, J. Comput. System Sci. 54 , 317–331) showed that the gap problem corresponding to approximating CVP within 2 log 0.999 n is quasi-NP-hard.