SVP · Quantum · worst case — CryptoRecords.info

Quantum · worst case

Exact Euclidean SVP; model must be specified per entry

12 results · 8 papers

QuantumProvableWorst case2^{c n + o(n)}

Results

#	PUBLICATION / AUTHORS	DATE	TIME BOUND	SPACE BOUND	EVIDENCE
1	Superlattice methods for the shortest vector problem and discrete Gaussian samplingMinki Hhan · Jiseung Kim · Sunyeop Kim · Thijs LaarhovenePrint 2026/2761Source BibTeX / detailsquantum worst-case Euclidean author-supplied precision	4 Nov 2026	2^{0.2469 n + o(n)}	2^{0.247 n + o(n)}	PreprintNot reviewed
2	Solving the Shortest Vector Problem in 2^(0.6039n) Time via Mid-point HessianMinki HhanePrint 2026/1597Source BibTeX / detailsarbitrary lattices Euclidean	3 Aug 2026	2^{0.5411 n + o(n)}	2^{0.5 n + o(n)}	PreprintSource checked
3	Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance DecodingDivesh Aggarwal · Yanlin Chen · Rajendra Kumar · Yixin ShenSIAM Journal on Computing 2025Source BibTeX / detailsprovable quantum QRAM size 2^{0.293n+o(n)}	10 May 2022	2^{0.835 n + o(n)}	2^{0.5 n + o(n)}	PublishedSource checked
4	Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance DecodingDivesh Aggarwal · Yanlin Chen · Rajendra Kumar · Yixin ShenSIAM Journal on Computing 2025Source BibTeX / detailsprovable quantum No QRAM	10 May 2022	2^{0.95 n + o(n)}	2^{0.5 n + o(n)}	PublishedSource checked
5	Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance DecodingDivesh Aggarwal · Yanlin Chen · Rajendra Kumar · Yixin ShenSTACS 2021Source BibTeX / detailsprovable quantum no QRAM	10 Mar 2021	2^{0.9533 n + o(n)}	2^{0.5 n + o(n)}	PublishedSource checked
6	Solving the Shortest Vector Problem in 2^n Time via Discrete Gaussian SamplingDivesh Aggarwal · Daniel Dadush · Oded Regev · Noah Stephens-DavidowitzSTOC 2015Source BibTeX / detailsclassical baseline worst-case	26 Dec 2014	2^{n + o(n)}	2^{n + o(n)}	PublishedSource checked
7	Space-efficient classical and quantum algorithms for the shortest vector problemYanlin Chen · Kai-Min Chung · Ching-Yi LaiQuantum Information and Computation 2018Source BibTeX / detailsquantum provable bounded memory	31 Aug 2017	2^{1.2553 n + o(n)}	2^{0.5 n + o(n)}	PublishedSource checked
8	Solving the Shortest Vector Problem in Lattices Faster Using Quantum SearchThijs Laarhoven · Michele Mosca · Joop van de PolPost-Quantum Cryptography 2013Source BibTeX / detailsquantum provable QCRAM	25 Jan 2013	2^{1.799 n + o(n)}	2^{1.286 n + o(n)}	PublishedSource checked
8	Finding shortest lattice vectors faster using quantum searchThijs Laarhoven · Michele Mosca · Joop van de PolDesigns, Codes and Cryptography 2015Source BibTeX / detailsquantum provable QCRAM	14 Apr 2015	2^{1.799 n + o(n)}	2^{1.286 n + o(n)}	PublishedSource checked
10	Finding shortest lattice vectors faster using quantum searchThijs Laarhoven · Michele Mosca · Joop van de PolDesigns, Codes and Cryptography 2015Source BibTeX / detailsquantum provable QCRAM	14 Apr 2015	2^{1.986 n + o(n)}	2^{1.324 n + o(n)}	PublishedSource checked
11	Finding shortest lattice vectors faster using quantum searchThijs Laarhoven · Michele Mosca · Joop van de PolDesigns, Codes and Cryptography 2015Source BibTeX / detailsquantum provable QCRAM	14 Apr 2015	2^{2.527 n + o(n)}	2^{1.351 n + o(n)}	PublishedSource checked
12	Finding shortest lattice vectors faster using quantum searchThijs Laarhoven · Michele Mosca · Joop van de PolDesigns, Codes and Cryptography 2015Source BibTeX / detailsquantum provable QCRAM	14 Apr 2015	2^{2.672 n + o(n)}	2^{1.877 n + o(n)}	PublishedSource checked

Comparison definition & assumptions

Regime: Exact Euclidean SVP; model must be specified per entry
Computation: Quantum
Rigor: Provable
Instances: Worst case
Cost scale: 2^{c n + o(n)}
Parameter: n
Description: Quantum upper bounds for exact Euclidean SVP on arbitrary lattices. Each result retains its memory and access model.
Comparison rules: Return an exact shortest vector on arbitrary full-rank lattices. The general list allows quantum random access where stated; it is not a no-QRAM ranking. Record classical memory, coherent access and quantum memory assumptions per result. The separate no-QRAM category excludes algorithms requiring quantum access to an exponential database. Publication, source checking and independent proof review are separate metadata.
Tags: arbitrary lattices, Euclidean