Shortest Vector Problem
Find a shortest nonzero lattice vector.
19 variants · 101 entries. Compare bounds only within the same variant.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
SVPClassical · worst caseClassical · ProvableExact Euclidean SVP on arbitrary full-rank latticesWorst case200.409 SVPClassical · heuristicClassical · HeuristicEuclidean SVP under sieve heuristicsHeuristic random lists140.292481 SVPQuantum · worst caseQuantum · ProvableExact Euclidean SVP; model must be specified per entryWorst case120.2469 SVPQuantum · heuristicQuantum · HeuristicQuantum lattice sieving with random accessHeuristic random lists100.2563 SVPClassical · Haar randomClassical · ProvableExact SVP on Haar–Siegel random unimodular latticesHaar random30.292481 SVPHeuristic · triple sievingClassical · HeuristicTriple lattice sieving; compare time and memory jointlyHeuristic spherical lists100.33 SVPConstant approximation · large-factor limitClassical · ProvableFor every fixed ε > 0, some constant μ(ε) yields μ-SVP on arbitrary Euclidean latticesWorst case50.409 SVPHeuristic · minimal list spaceClassical · HeuristicExact Euclidean SVP; space ≤ 2^{(½log₂(4/3)+o(1))n}Arbitrary input; heuristic analysis50.292481 SVPHeuristic · quantum · memory ≤ 0.1887nQuantum · HeuristicQuantum SVP; classical and quantum-addressable memory at most 2^{0.1887n+o(n)}Heuristic spherical lists50.2846 SVPHeuristic · quantum · minimal sieve-list spaceQuantum · HeuristicSequential quantum sieving; space ≤ 2^{(½log₂(4/3)+o(1))n}Arbitrary input; spherical-list heuristic50.265257 SVPEnumeration · superexponential scaleClassical · ProvableExact Euclidean SVP; specify basis reduction and preprocessingArbitrary lattices40.09197 SVPClassical · ℓ∞ normClassical · ProvableExact SVP on arbitrary rational full-rank lattices; ℓ∞ normWorst case22.443 SVPQuantum · no QRAMQuantum without QRAM · Model dependentExact Euclidean SVP without coherent random access to an exponential classical databaseArbitrary lattices20.95 SVPApproximate decision · EuclideanClassical · ProvableEuclidean GapSVP on arbitrary lattices; approximation factor γ is stated per resultWorst case1— SVPClassical · all ℓp normsClassical · ProvableExact SVP on arbitrary rational full-rank lattices; Every fixed ℓp norm, 1 ≤ p ≤ ∞Worst case12.751 SVPHeuristic · parallel quantum depthQuantum parallel · HeuristicParallel quantum circuit depth with 2^{0.2075n+o(n)} quantum memoryHeuristic spherical lists10.1037 SVPIdeal lattices · heuristicClassical · HeuristicExact Euclidean SVP in cyclotomic ideal latticesIdeal lattices10.2972 SVPHaar-random · quantumQuantum · ProvableHaar–Siegel random determinant-one lattices; specify coherent access and success guaranteeHaar random0— SVPKissing-constant assumptionsClassical · Conditional theoremFix a uniform kissing/point-counting bound and its exponent β before comparing c(β)Arbitrary lattices0—