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

ACM SIGACT News

Complexity theory

Lane A. Hemaspaandra

Published Sep 1, 2001• 12 citations
Publisher

Abstract

We present high-level technical summaries of five recent results on the computational complexity of the shortest lattice vector problem.
DOI
10.1145/500559.500560

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

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.

Designs Codes and Cryptography•Apr 13, 2015•97 citations

Theoretical Approaches to Solving the Shortest Vector Problem in NP-Hard Lattice-Based Cryptography with Post-SUSY Theories of Quantum Gravity in Polynomial Time by Orch-Or

Trevor Nestor

The Shortest Vector Problem (SVP) is a cornerstone of lattice-based cryptography, underpinning the security of numerous cryptographic schemes like NTRU. Given its NP-hardness, efficient solutions to SVP have profound implications for both cryptography and computational complexity theory. This paper presents an innovative framework that integrates concepts from quantum gravity, non-commutative geometry, spectral theory, and post-supersymmetry (post-SUSY) particle physics to address SVP. By mapping high-dimensional lattice points to spinfoam networks and by means of Hamiltonian engineering, it is theoretically possible to devise new algorithms that leverage the interactions topologically protected Majorana fermionparticles have with the gravitational field through the spectral action principle to loop through these spinfoam networks where SVP vectors could then be encoded onto the spectrum of the corresponding Dirac-like dilation operators within the system. We establish a novel approach that leverages post-SUSY physics and theories of quantum gravity to achieve algorithmic speedups beyond those expected by conventional quantum computers. This interdisciplinary methodology not only proposes potential polynomial-time algorithms for SVP, but also bridges gaps between theoretical physics and cryptographic applications, providing further insights into the Riemann Hypothesis (RH) and the Hilbert-P ´olya Conjecture. Possible directions for experimental realization through biologically inspired hardware or biological tissues by orchestrated objective reduction (Orch-Or) theory are discussed.

IPI Letters•Mar 10, 2025•3 citations

Quantum Complexity for Vector Domination Problem

Andris Ambainis, Ansis Zvirbulis

Lecture notes in computer science•Dec 19, 2022•0 citations

Hard combinatorial problems and minor embeddings on lattice graphs

Andrew Lucas

arXiv:1812.01789•Quantum Information Processing•May 16, 2019•24 citations

Upper bounds of complexity of quantum oracle for problem of finding shortest vector on integer lattice

Alexander Olegovich Bakharev

Due to the development of quantum computing, there is a need for development and analysis of cryptosystems resistant to attacks with using a quantum computer - post-quantum algorithms cryptography. The strength of many well-known post-quantum cryptosystems, based on the theory of lattices, is based on the complexity of solving the problem finding the shortest vector in the lattice (SVP). For the previously proposed models of the quantum oracle used in the hybrid quantum-classical algorithm for solving the SVP problem, new refined estimates of implementation complexity. Designed and analyzed a new quantum oracle model that uses classical memory to storing a list of vectors.

Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"•Jan 1, 2022•0 citations
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)2^{1.799n + o(n)}21.799n+o(n) , improving upon the classical time complexities of 22.465n+o(n)2^{2.465n + o(n)}22.465n+o(n) of Pujol and Stehlé and the 22n+o(n)2^{2n + o(n)}22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.268n+o(n)2^{0.268n + o(n)}20.268n+o(n) , improving upon the classical time complexity of 20.298n+o(n)2^{0.298n + o(n)}20.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.
The Shortest Vector Problem (SVP) is a cornerstone of lattice-based cryptography, underpinning the security of numerous cryptographic schemes like NTRU. Given its NP-hardness, efficient solutions to SVP have profound implications for both cryptography and computational complexity theory. This paper presents an innovative framework that integrates concepts from quantum gravity, non-commutative geometry, spectral theory, and post-supersymmetry (post-SUSY) particle physics to address SVP. By mapping high-dimensional lattice points to spinfoam networks and by means of Hamiltonian engineering, it is theoretically possible to devise new algorithms that leverage the interactions topologically protected Majorana fermionparticles have with the gravitational field through the spectral action principle to loop through these spinfoam networks where SVP vectors could then be encoded onto the spectrum of the corresponding Dirac-like dilation operators within the system. We establish a novel approach that leverages post-SUSY physics and theories of quantum gravity to achieve algorithmic speedups beyond those expected by conventional quantum computers. This interdisciplinary methodology not only proposes potential polynomial-time algorithms for SVP, but also bridges gaps between theoretical physics and cryptographic applications, providing further insights into the Riemann Hypothesis (RH) and the Hilbert-P ´olya Conjecture. Possible directions for experimental realization through biologically inspired hardware or biological tissues by orchestrated objective reduction (Orch-Or) theory are discussed.
Due to the development of quantum computing, there is a need for development and analysis of cryptosystems resistant to attacks with using a quantum computer - post-quantum algorithms cryptography. The strength of many well-known post-quantum cryptosystems, based on the theory of lattices, is based on the complexity of solving the problem finding the shortest vector in the lattice (SVP). For the previously proposed models of the quantum oracle used in the hybrid quantum-classical algorithm for solving the SVP problem, new refined estimates of implementation complexity. Designed and analyzed a new quantum oracle model that uses classical memory to storing a list of vectors.