# Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Yixin Shen

► To cite this version:

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Yixin Shen. Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding. SIAM Journal on Computing, 2025, 54 (2), pp.233-278. 10.1137/22M1486959. hal-05406608

HAL Id: hal-05406608

https://hal.science/hal-05406608v1

Submitted on 9 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding*

Divesh Aggarwal<fnref n="1" />**, Yanlin Chen<fnref n="2" />, Rajendra Kumar<fnref n="3" />***, and Yixin Shen<fnref n="4" />†

**Abstract.** The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results.

1. A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer $4 \le q \le \sqrt{n}$, our algorithm takes $q^{13n+o(n)}$ time and requires $\text{poly}(n) \cdot q^{16n/q^2}$ memory. This tradeoff which ranges from enumeration ($q = \sqrt{n}$) to sieving ($q$ constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter.

2. A quantum algorithm for SVP that runs in time $2^{0.950n+o(n)}$ and requires $2^{0.5n+o(n)}$ classical memory and $\text{poly}(n)$ qubits. In Quantum Random Access Memory (QRAM) model this algorithm takes only $2^{0.835n+o(n)}$ time and requires a QRAM of size $2^{0.293n+o(n)}$, $\text{poly}(n)$ qubits and $2^{0.5n}$ classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ADRS15] that has a time and space complexity $2^{n+o(n)}$.

3. A classical algorithm for SVP that runs in time $2^{1.669n+o(n)}$ time and $2^{0.5n+o(n)}$ space. This improves over an algorithm of [CCL18] that has the same space complexity.

The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number which is $2^{0.402n}$. We conjecture that for most lattices this quantity is a $2^{o(n)}$. Assuming that this is the case, our classical algorithm runs in time $2^{1.292n+o(n)}$, our quantum algorithm runs in time $2^{0.750n+o(n)}$ and our quantum algorithm in QRAM model runs in time $2^{0.667n+o(n)}$.

As a direct application of our result, using the reduction in [Duc23], we obtain a provable quantum algorithm for the Lattice Isomorphism Problem in the case of the trivial lattice $\mathbb{Z}^n$ (ZLIP) that runs in time $2^{0.417n+o(n)}$. Our algorithm requires a QRAM of size $2^{0.147n+o(n)}$, $\text{poly}(n)$ qubits and $2^{0.25n}$ classical space.

**Keywords:** Lattices · Shortest Vector Problem · Discrete Gaussian Sampling · Time-Space Tradeoff · Quantum computation · Bounded distance decoding.

## 1 Introduction

A lattice $\mathcal{L} = \mathcal{L}(b_1, \dots, b_n) := \{\sum_{i=1}^n z_i b_i : z_i \in \mathbb{Z}\}$ is the set of all integer combinations of linearly independent vectors $b_1, \dots, b_n \in \mathbb{R}^n$. We call $n$ the rank of the lattice and $(b_1, \dots, b_n)$ a basis of the lattice.

<footnote n="1">¹ Centre for Quantum Technologies and National University of Singapore. email: dcsdiva@nus.edu.sg.</footnote>

<footnote n="2">² QuSoft and CWI, the Netherlands. email: yanlin@cwi.nl</footnote>

<footnote n="3">³ Centre for Quantum Technologies and National University of Singapore. email: rjndr2503@gmail.com</footnote>

<footnote n="4">⁴ Univ Rennes, Inria, CNRS, IRISA, Rennes, France. email: yixin.shen@inria.fr</footnote>

<footnote>* A preliminary version of this paper titled "Improved (Provable) algorithms for the Shortest Vector Problem via Bounded Distance Decoding" appeared in the proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) [ACKS21].</footnote>

<footnote>** This work was partially supported by the Singapore Ministry of Education under grant MOE2019-T2-1-145, National Research Foundation under grant R-710-000-012-135</footnote>

<footnote>*** This research has been supported in part by the National Research Foundation Singapore under its AI Singapore Programme [Award Number: AISG-RP-2018-005]</footnote>

<footnote>† This research was partially supported by EPSRC grant EP/W02778X/2 and by the French Agence Nationale de la Recherche through the France 2030 program under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.</footnote>
The most important computational problem on lattices is the Shortest Vector Problem (SVP). Given a basis for a lattice $\mathcal{L} \subseteq \mathbb{R}^n$, SVP asks us to compute a non-zero vector in $\mathcal{L}$ with the smallest Euclidean norm. Starting from the '80s, the use of approximate and exact solvers for SVP (and other lattice problems) gained prominence for their applications in algorithmic number theory [LLL82], convex optimization [Jr.83,Kan87,FT87], coding theory [dB89], and cryptanalysis tool [Sha84,Bri84,LO85]. The security of many cryptographic primitives is based on the worst-case hardness of (a decision variant of) approximate SVP to within polynomial factors [Ajt96,MR04,Reg09,Reg06,MR08,Gen09,BV14] in the sense that any crypt-analytic attack on these cryptosystems that runs in time polynomial in the security parameter implies a polynomial time algorithm to solve approximate SVP to within polynomial factors. Such cryptosystems have attracted a lot of research interest due to their conjectured resistance to quantum attacks.

The SVP is a well-studied computational problem in both its exact and approximate (decision) versions. By a randomized reduction, it is known to be NP-hard to approximate within any constant factor, and hard to approximate within a factor $n^{c/\log \log n}$ for some $c > 0$ under reasonable complexity-theoretic assumptions [VEB81,Mic98,Kho05,HR07]. For an approximation factor $2^{O(n)}$, one can solve SVP in time polynomial in $n$ using the celebrated LLL lattice basis reduction algorithm [LLL82]. In general, the fastest known algorithm(s) for approximating SVP within factors polynomial in $n$ rely on (a variant of) the BKZ lattice basis reduction algorithm [Sch87,SE94,AKS01,GN08,HPS11,ALNS19], which can be seen as a generalization of the LLL algorithm and gives an $r^{n/r}$ approximation in $2^{O(r)}$ poly($n$) time. All these algorithms internally use an algorithm for solving (near) exact SVP in lower-dimensional lattices. Therefore, finding faster algorithms to solve exact SVP is critical to choosing security parameters of cryptographic primitives.

As one would expect from the hardness results above, all known algorithms for solving exact SVP, including the ones we present here, require at least exponential time. In fact, the fastest known algorithms also require exponential space. There has been some recent evidence [AS18a] showing that one cannot hope to get a $2^{o(n)}$ time algorithm for SVP if one believes in complexity theoretic conjectures such as the (Gap) Exponential Time Hypothesis. Most of the known algorithms for SVP can be broadly classified into two classes: (i) the algorithms that require memory polynomial in $n$ but run in time $n^{O(n)}$ and (ii) the algorithms that require memory $2^{O(n)}$ and run in time $2^{O(n)}$.

The first class, initiated by Kannan [Kan87,Hel85,HS07,GNR10,MW15,ABF+20], combines basis reduction with exhaustive enumeration inside Euclidean balls. While enumerating vectors requires $2^{O(n \log n)}$ time, it is much more space-efficient than other kinds of algorithms for exact SVP.

Another class of algorithms, and currently the fastest, is based on sieving. First developed by Ajtai, Kumar, and Sivakumar [AKS01], they generate many lattice vectors and then divide-and-sieve to create shorter and shorter vectors iteratively. A sequence of improvements [Reg04,NV08,MV10,PS09,ADRS15,AS18b], has led to a $2^{n+o(n)}$ time and space algorithm by sieving the lattice vectors and carefully controlling the distribution of the output, thereby outputting a set of lattice vectors that contains the shortest vector with overwhelming probability.

An alternative approach using the Voronoi cell of the lattice was proposed by Micciancio and Voulgaris [MV13] and gives a deterministic $2^{2n+o(n)}$-time and $2^{n+o(n)}$-space algorithm for SVP (and many other lattice problems).

There are variants [NV08,MV10,LMV15,BDGL16] of the above mentioned sieving algorithms that, under some heuristic assumptions, have an asymptotically smaller (but still $2^{\Theta(n)}$) time and space complexity than their provable counterparts.

*Algorithms giving a time/space tradeoff.* Even though sieving algorithms are asymptotically the fastest known algorithms for SVP, the memory requirement, in high dimension, has historically been a limiting factor to run these algorithms. Some recent works [Duc18,ADH+19] have shown how to use new tricks to make it possible to use sieving on high-dimensional lattices in practice and benefit from their efficient running time [SVP].

Nevertheless, it would be ideal and has been a long standing open question to obtain an algorithm that achieves the "best of both worlds", i.e. an algorithm that runs in time $2^{O(n)}$ and requires memory polynomial in $n$. In the absence of such an algorithm, it is desirable to have a smooth tradeoff between
the time and memory requirement that interpolates between the current best sieving algorithms and the
current best enumeration algorithms.

To this end, Bai, Laarhoven, and Stehlé [BLS16] proposed the tuple sieving algorithm, providing such a tradeoff based on heuristic assumptions similar in nature to prior sieving algorithms. This algorithm was later proven to have time and space complexity $k^{O(n)}$ and $k^{O(n/k)}$, under the same heuristic assumptions [HK17]. One can vary the parameter $k$ to obtain a smooth time/space tradeoff. Nevertheless, it is still desirable to obtain a provable variant of this algorithm that does not rely on any heuristics.

Kirchner and Fouque [KF16] attempted to do this. They claim an algorithm for solving SVP in time $k^{\Theta(n)}$ and in space $k^{\Theta(n/k)}$ for any positive integer $k > 1$. Unfortunately, their analysis falls short of supporting their claimed result, and the correctness of the algorithm is not clear. We refer the reader to Section 1.3 for more details.

In addition to the above, Chen, Chung, and Lai [CCL18] propose a variant of the algorithm based on Discrete Gaussian sampling in [ADRS15]. Their algorithm runs in time $2^{2.05n+o(n)}$ and the memory requirement is $2^{0.5n+o(n)}$. The quantum variant of their algorithm runs in time $2^{1.2553n+o(n)}$ and has the same space complexity. Their algorithm has the best space complexity among known provably correct algorithms that run in time $2^{O(n)}$.

A number of works have also investigated the potential quantum speedups for lattice algorithms, and SVP in particular. A similar landscape to the classical one exists, although the quantum memory model has its importance. While quantum enumeration algorithms only require qubits [ANS18], sieving algorithms require more powerful QRAMs [LMV15,KMPM19].

## 1.1 Our results

We first present a new algorithm for SVP that provides a smooth tradeoff between the time complexity and memory requirement of SVP without any heuristic assumptions. This algorithm is obtained by giving a new algorithm for sampling lattice vectors from the Discrete Gaussian distribution that runs in time $k^{O(n)}$ and requires $k^{O(n/k)}$ space.

**Theorem 1 (Time-space tradeoff for smooth discrete Gaussian, informal).** There is an algorithm that takes as input a lattice $\mathcal{L} \subset \mathbb{R}^n$, a positive integer $q$, and a parameter $s$ above the smoothing parameter of $\mathcal{L}$, and outputs $q^{16n/q^2}$ samples from $D_{\mathcal{L},s}$ using $q^{13n+o(n)}$ time and poly($q$) $\cdot q^{16n/q^2}$ space.

Using the standard reduction from Bounded Distance Decoding (BDD) with preprocessing (where an algorithm solving the problem is allowed unlimited preprocessing time on the lattice before the algorithm receives the target vector) to Discrete Gaussian Sampling (DGS) from [DRS14] and a reduction from SVP to BDD given in [CCL18], we obtain the following.

**Theorem 2 (Time-space tradeoff for SVP).** Let $n \in \mathbb{N}$, $q \in [4, \sqrt{n}]$ be a positive integer. Let $\mathcal{L}$ be a lattice of rank $n$. There is a randomized algorithm that solves SVP in time $q^{13n+o(n)}$ and in space poly($n$) $\cdot q^{\frac{16n}{q^2}}$.

If we take $k = q^2$, then the time complexity of the previous SVP algorithm becomes $k^{6.5n+o(n)}$ and the space complexity poly($n$) $\cdot k^{(8n/k)}$. Our tradeoff is thus the same (up to a constant in the exponents) as what was claimed by Kirchner and Fouque [KF16] and proven in [HK17] under heuristic assumptions.

Our second result is a quantum algorithm for SVP that improves over the current fastest quantum algorithm for SVP [ADRS15] (Notice that the algorithm in [ADRS15] is still the fastest classical algorithm for SVP).

**Theorem 3 (Quantum Algorithm for SVP).** There is a quantum algorithm that solves SVP in $2^{0.950n+o(n)}$ time and classical $2^{0.5n+o(n)}$ space with an additional poly($N$) qubits. In the Quantum Random Access Memory (QRAM) model, there is an algorithm that solves SVP in $2^{0.8345n+o(n)}$ time and require a QRAM of size $2^{0.293n+o(n)}$, poly($n$) qubits and $2^{0.5n+o(n)}$ classical space.

Our third result is a classical algorithm for SVP that improves over the algorithm from [CCL18] and results in the fastest classical algorithm that has a space complexity $2^{0.5n+o(n)}$.
**Theorem 4 (Algorithm for SVP with $2^{0.5n+o(n)}$ space).** There is a classical algorithm that solves SVP in $2^{1.669n+o(n)}$ time and $2^{0.5n+o(n)}$ space.

The time complexity of our second and third results are obtained using a known upper bound on a quantity $\beta(\mathcal{L})^n$ related to the kissing number, which depends on the lattice and is always upper bounded by $2^{0.402n}$. We analysed the dependency of the running time of our algorithm in this quantity $\beta(\mathcal{L})$ and plotted (Figure 2) the graph of the complexity exponent as a function of $\beta(\mathcal{L})$. In practice, for most lattices, $\beta(\mathcal{L})^n$ is often a $2^{o(n)}$ $^5$. In this case, the running time of our algorithm is significantly better than when using the generic upper bound on $\beta(\mathcal{L})$.

**Theorem 5.** For any family $(\mathcal{L}_n)_n$ of full-rank lattices such that $\mathcal{L}_n \subseteq \mathbb{R}^n$ and $\beta(\mathcal{L}_n)^n = 2^{o(n)}$, there are algorithms to solve the SVP on $\mathcal{L}_n$:

- in classical time $2^{1.292n+o(n)}$ and space $2^{0.5n}$,

- in quantum time $2^{0.750n+o(n)}$, classical space $2^{0.5n}$ and poly(n) qubits,

- in quantum time $2^{0.667n+o(n)}$, classical space $2^{0.5n}$, poly(n) qubits and using a QRAM of size $2^{0.167n+o(n)}$.

Below in Table 1 and 2, we summarize known provable classical and quantum algorithms respectively. Note that all the classical algorithms are also quantum algorithms but they don't use any quantum power.

<table><caption>**Table 1.** Classical algorithms for Shortest vector problem.</caption><thead><tr><td>Time Complexity</td><td>Space Complexity</td><td>Reference</td></tr></thead><tbody><tr><td>$n^{\frac{n}{2e}+o(n)}$</td><td>poly(n)</td><td>[Kan87,HS07]</td></tr><tr><td>$2^{O(n)}$</td><td>$2^{O(n)}$</td><td>[AKS01]</td></tr><tr><td>$2^{2.465n+o(n)}$</td><td>$2^{1.233n+o(n)}$</td><td>[PS09]</td></tr><tr><td>$2^{2n+o(n)}$</td><td>$2^{n+o(n)}$</td><td>[MV10]</td></tr><tr><td>$2^{n+o(n)}$</td><td>$2^{n+o(n)}$</td><td>[ADRS15]</td></tr><tr><td>$2^{2.05n+o(n)}$</td><td>$2^{0.5n+o(n)}$</td><td>[CCL18]</td></tr><tr><td>$2^{1.669n+o(n)}$</td><td>$2^{0.5n+o(n)}$</td><td>This paper</td></tr></tbody></table>

<table><caption>**Table 2.** Quantum algorithms for Shortest vector problem.</caption><thead><tr><td>Time Complexity</td><td>Space Complexity</td><td>Reference</td></tr></thead><tbody><tr><td>$2^{1.799n+o(n)}$</td><td>$2^{1.286n+o(n)}$ QRAM</td><td>[LMV15]</td></tr><tr><td>$2^{1.2553n+o(n)}$</td><td>$2^{0.5n+o(n)}$</td><td>[CCL18]</td></tr><tr><td>$2^{0.950n+o(n)}$</td><td>$2^{0.5n+o(n)}$</td><td>This paper</td></tr><tr><td>$2^{0.835n+o(n)}$</td><td>$2^{0.5n+o(n)}$ Classical space and $2^{0.293n+o(n)}$ QRAM</td><td>This paper</td></tr></tbody></table>

<footnote n="5">⁵ Please refer to our discussion on kissing number in Section 2.</footnote>
**Roadmap.** We give a high-level overview of our proofs in Section 1.2. We compare our results with the previous known algorithms that claim/conjecture a time-space tradeoff for SVP in Section 1.3. Section 2 contain some preliminaries on lattices. The proofs of the time-space tradeoff for Discrete Gaussian sampling above the smoothing parameter and the time-space tradeoff for SVP are given in Section 3. In Section 4, we present a Quantum algorithm for BDD with preprocessing, that we will use later in our quantum Algorithm for SVP. In section 5, we present improved algorithms for BDD. Our quantum and classical algorithms for solving SVP with space complexity $2^{0.5n+o(n)}$ are presented in Section 6 respectively. Section 7 shows how the time complexity of our algorithms varies on a quantity related to the kissing number. Section 8 gives a direct application of our results to the Lattice Isomorphism Problem in the case of the trivial lattice $\mathbb{Z}^n$ (ZLIP).

*Remark 6.* The paper is an extended version of [ACKS21], published at the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Compared to [ACKS21], this paper gives a quantum speedup for Bounded distance decoding in processing using QRAM. Using this quantum speedup, we get a much faster quantum algorithm for SVP. We also realised that one of the conditions in Theorem 25 is unnecessary $^6$, this leads to a better time complexity in all our algorithms compared to the previous version. Furthermore, we study the dependency of our algorithms on a quantity related to the kissing number in Section 7.

## 1.2 Proof overview

We now include a high-level description of our proofs. Before describing our proof ideas, we emphasize that it was shown in [DRS14,ADRS15] that given an algorithm for DGS a constant factor $c$ above the smoothing parameter, we can solve the problem of BDD where the target vector is within distance $\alpha\lambda_1(\mathcal{L})$ of the lattice, where the constant $\alpha < 0.5$ depends on the constant $c$. Additionally, using [CCL18], one can enumerate all lattice points within distance $p\delta$ to a target $t$ by querying $p^n$ times a BDD oracle with decoding distance $\delta$ (or $p^{n/2}$ times if we are given a quantum BDD oracle). Thus, by choosing $p = \lceil \lambda_1(\mathcal{L})/\delta \rceil$ and $t = 0$, an algorithm for BDD immediately gives us an algorithm for SVP. Therefore, it suffices to give an algorithm for DGS above the smoothing parameter.

**Time-space tradeoff for DGS above smoothing.** Recall that efficient algorithms are known for sampling from a discrete Gaussian with a large enough parameter (width) [Kle00,GPV08,BLP$^+$13]. In [ADRS15], the authors begin by sampling $N = 2^{n+o(n)}$ vectors from the Discrete Gaussian distribution with (large) parameter $s$ and then look for pairs of vectors whose sum is in $2\mathcal{L}$, or equivalently pairs of vectors that lie in the same coset $c \in \mathcal{L}/2\mathcal{L}$. Since there are $2^n$ cosets, if we take $\Omega(2^n)$ samples from $D_{\mathcal{L},s}$, almost all of the resulting vectors (except at most $2^n$ vectors) will be paired and are statistically close to independent samples from the distribution $D_{\mathcal{L},s/\sqrt{2}}$, provided that the parameter $s$ is sufficiently above the smoothing parameter.

To reduce the space complexity, we modify the idea of the algorithm by generating random samples and checking if the summation of $d$ of those samples is in $q\mathcal{L}$ for some integer $q$. Intuitively, if we start with two lists of vectors ($L_1$ and $L_2$) of size $q^{O(n/d)}$ from $D_{\mathcal{L},s}$, where $s$ is sufficiently above the smoothing parameter, each of these vectors is contained in any coset $q\mathcal{L}+c$ for any $c \in \mathcal{L}/q\mathcal{L}$ with probability roughly $1/q^n$. We therefore expect that the coset of a uniformly random $d$-combination of vectors from $L_2$ is uniformly distributed in $\mathcal{L}/q\mathcal{L}$. The proof of this statement follows from the Leftover Hash Lemma [ILL89]. We therefore expect that for any vector $v \in L_1$, with high probability, there is a set of $d$ vectors $x_1, \dots, x_d$ in $L_2$ that sum to a vector in $q\mathcal{L}+v$, and hence $\frac{1}{q} \left( \sum_{i=1}^d (x_i - v) \right) \in \mathcal{L}$. A lemma by Micciancio and Peikert ([MP13]) shows that this vector is statistically close to a sample from the distribution, $D_{\mathcal{L},s\sqrt{d+1/q}}$. We can find such a combination by trying all subsets of $d$ vectors.

<footnote>$^6$ See Remark 26</footnote>
We would like to repeat this and find $q^{O(n/d)}$ (nearly) independent vectors in $q \mathcal{L}$. It is not immediately clear how to continue since, in order to guarantee independence, one would not want to reuse the already used vectors $x_1, \dots, x_d$ and conditioned on the choice of these vectors, the distribution of the cosets containing the remaining vectors is disturbed and is no longer nearly uniform. By using a simple combinatorial argument, we show that even after removing any 1/poly($d$) fraction of vectors from the list $L_2$, the $d$-combination of vectors in $L_2$ has at least $cq^n$ different cosets. This is sufficient to output $q^{O(n/d)}$ independent vectors in $q \mathcal{L}$ with overwhelming probability.

**Quantum algorithm for BDDP in QRAM.** In [DRS14], Dadush, Regev, and Stephens-Davidowitz gave an algorithm for BDD with preprocessing (or BDDP), which requires advice containing vectors sampled from discrete Gaussian sampling over the dual lattice. The idea is to use the *periodic Gaussian function f* (defined in Section 4) to go near to the closest lattice vector. The function *f* is periodic over the lattice, and its value depends only on the distance between the input vector and the lattice. Do the gradient ascent by iteratively updating the target vector using values of $\nabla f$ and *f* such that the distance of the target vector from the closest lattice vector decreases. In this work, we show that we can reduce the time complexity of this algorithm by using the quantum amplitude estimation technique (given in [BHMT02]) with the assumption that the advice string is stored in QRAM. More specifically, we show that just by using $O(\sqrt{N})$ arithmetic operations in QRAM, we can solve BDDP where *N* is the size of the advice string required in [DRS14].

**An improved algorithm for DGS at the smoothing parameter.** The BDD to DGS reduction from [DRS14] requires samples from $D_{\mathcal{L},\eta_{\varepsilon}(\mathcal{L})}$ for $\varepsilon = 2^{-cn}$ for some constant $c$. In [ADRS15], the authors gave an algorithm that runs in time $2^{n/2+o(n)}$ and outputs $2^{n/2+o(n)}$ samples from $D_{\mathcal{L},s}$ for any $s \ge \sqrt{2\eta_{0.5}(\mathcal{L})}$, i.e. a factor $\sqrt{2}$ above the smoothing parameter. In order to obtain samples at the smoothing parameter, we construct a dense lattice $\mathcal{L}'$ of smaller smoothing parameter than $\mathcal{L}$. We then sample $2^{0.5n+o(n)}$ vectors from $D_{\mathcal{L}',s}$ and reject those that are not in $\mathcal{L}$. This allows us to obtain an improved algorithm for BDD with preprocessing.

**Covering surface of a ball by spherical caps.** This result improves the quantum algorithm from [CCL18]. As we mentioned above, one can enumerate all lattice points within a $p\delta$ distance to a target $t$ by querying $p^n$ times a BDD oracle with decoding distance $\delta$. Our algorithm for BDD is obtained by preparing samples from the discrete Gaussian distribution. However, note that the decoding distance of BDD oracle built by discrete Gaussian samples as shown in [DRS14] is successful if the target vector is within a radius $\alpha\lambda_1(\mathcal{L})$ for $\alpha < 1/2$ (there is a tradeoff between $\alpha$ and the number of DGS samples needed), and therefore, if we choose $t$ to be 0, as we do in the other algorithms mentioned above, then $p$ has to be at least 3 to ensure that the shortest vector is one of the vectors output by the enumeration algorithm mentioned above. We observe here that if we choose a target $t$ to be a random vector on a sphere of a well-chosen radius centered at the origin, then the shortest vector will be within a radius $2\delta$ from the target $t$ with some probability $P$, and thus we can find the shortest vector by making $2^n/P$ calls to the BDD oracle. An appropriate$^7$ choice of the target $t$ and the factor $\alpha$ gives an algorithm that runs in time $2^n \cdot 2^{0.669n+o(n)}$. We then explain how to obtain a quantum quantum speed up of this algorithm (with its corresponding optimized value of $\alpha$ which is different from the classical one) that runs in time $2^{n/2} \cdot 2^{0.45n+o(n)}$ with a polynomial number of qubits. Finally, if we can store the DGS samples in a QRAM, we can obtain a further speed up and an algorithm that runs in time $2^{n/2} \cdot 2^{0.3345n+o(n)}$ and uses a QRAM of size $2^{0.293n+o(n)}$.

**Dependency on a quantity related to the kissing number.** The running time of the above algorithms crucially depends on a quantity related to the kissing number of the input lattice. This quantity plays a role in the BDD to DGS reduction when relating the decoding radius $\alpha$ to the $\varepsilon$ when sampling at the smoothing parameter $\eta_{\varepsilon}$. Our algorithms takes significantly less time for the smaller values of this quantity. However,

<footnote>$^7$ The optimal choice of $\alpha$ is obtained by numerically optimisation, see Section 7.</footnote>
the only known upper bound on this quantity seems to be very pessimistic for most lattices. Since we have
used this upper bound to derive the complexity of our algorithm (except in Section 7), this means that the
actual running time of this algorithm might be much better for most lattices. For a more elaborate discussion
on this, see Section 7. As far as we know, this is the first time that the time/space complexity dependency
on a quantity related to the input lattice has been investigated. For example, the time complexity of the
SVP algorithm in [MV10, PS09] depends on the geometric kissing number which is a universal quantity
depending only on the dimension $n$, for which we know a lower bound of $2^{0.2075n}$.

1.3 Comparison with previous algorithms giving a time/space tradeoff

Kirchner and Fouque [KF16] begin their algorithm by sampling an exponential number of vectors from the
discrete Gaussian distribution $D_{\mathcal{L},s}$ and then using a pigeon-hole principle, show that there are two distinct
sums of $d$ vectors (for an appropriate $d$) that are equal mod $q\mathcal{L}$, for some large enough integer $q$. This results
in a $\{-1, 0, 1\}$ combination of input lattice vectors (of Hamming weight at most $2d$) in $q\mathcal{L}$; a similar idea
was used in [BLS16] to construct their tuple sieving algorithm. In both algorithms, it is difficult to control
(i) the distribution of the resulting vectors, (ii) the dependence between resulting vectors.

Bai et al [BLS16] get around the above issues by making a heuristic assumption that the resulting vectors
behave like independent samples from a "nice enough" distribution. [HK17] proved that this heuristic
indeed leads to the time-memory tradeoff conjectured in [BLS16], but don't prove correctness.

Kirchner and Fouque, on the other hand, use the pigeon-hole principle to argue that there exist co-
efficients $\alpha_1, \dots, \alpha_{2d} \in \{-1, 0, 1\}$ and $2d$ lattice vectors in the set of input vectors $v_1, \dots, v_{2d}$ such that
$\frac{\sum_{i=1}^{2d} \alpha_i v_i}{q} \in \mathcal{L}$. It is then stated that $\frac{\sum_{i=1}^{2d} \alpha_i v_i}{q}$ has a nice enough Discrete Gaussian distribution. We observe
that while the resulting distribution obtained will indeed be close to a discrete Gaussian distribution, we
have no control over the parameter $s$ of this distribution and it can be anywhere between $1/q$ and $\sqrt{2d}/q$
depending on the number of nonzero coordinates in $(\alpha_1, \dots, \alpha_{2d})$. For instance, let $v_1, \dots, v_5$ be input vec-
tors which are all from $D_{\mathcal{L},s}$ for some large $s$ and we want to find the collision in $q\mathcal{L}$ for some positive
integer $q$. Suppose that we find a combination $w_1 = v_1 + v_2 - (v_1 + v_3) \in q\mathcal{L}$ and another combina-
tion $w_2 = v_2 + v_3 - (v_4 + v_5) \in q\mathcal{L}$, then by Theorem 17, one would expect that $w_1/q \sim D_{\mathcal{L}, \sqrt{2s}/q}$ and
$w_2/q \sim D_{\mathcal{L}, \sqrt{4s}/q}$. This means that the output of the exhaustive search algorithm by Kirchner and Fouque
will behave like samples taken from discrete Gaussian distributions with different parameters, making it
difficult to keep track of the standard deviation after several steps of the algorithm, and to obtain samples
from the Discrete Gaussian distribution at the desired parameter above the smoothing parameter. We over-
come this issue by showing that there is a combination of the input vectors with a fixed Hamming weight
that is in $q\mathcal{L}$ as mentioned in Section 1.2.

There are other technical details that were overlooked in [KF16]. In particular, one needs be careful
with respect to the errors, both in the probability of failure and the statistical distance of the input/output.
Indeed the algorithm performs an exponential number of steps, it is not enough to show that the algorithm
succeeds with "overwhelming probability" and that the output has a "negligible statistical distance" from
the desired output. However, many of the claimed error bounds in [KF16] are not proven making it difficult
to verify the proof of the Exhaustive Search (Theorem 3.4), and of Theorem 3.6.

## 2 Preliminaries

Let $\mathbb{N} = \{1, 2, \dots, \}$. We use bold letters $\mathbf{x}$ for vectors and denote a vector's coordinates with indices $x_i$. We use log to represent the logarithm base 2 and $\ln$ to represent the natural logarithm. Throughout the paper, $n$ will always be the dimension of the ambient space $\mathbb{R}^n$. We will denote the principal branch of Lambert's W function by $W(x)$, see [CGH$^{+96}$] for an introduction to this function.
**Lattices.** A lattice $\mathcal{L}$ is a discrete subgroup of $\mathbb{R}^m$, or equivalently the set

$$ \mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_n) = \left\{ \sum_{i=1}^{n} x_i \mathbf{b}_i : x_i \in \mathbb{Z} \right\} $$

of all integer combinations of $n$ linearly independent vectors $\mathbf{b}_1, \dots, \mathbf{b}_n \in \mathbb{R}^m$. Such $\mathbf{b}_i$'s form a basis of $\mathcal{L}$. The lattice $\mathcal{L}$ is said to be full-rank if $n = m$. We denote by $\lambda_1(\mathcal{L})$ the first minimum of $\mathcal{L}$, defined as the length of a shortest non-zero vector of $\mathcal{L}$.

For a rank $n$ lattice $\mathcal{L} \subset \mathbb{R}^n$, the dual lattice, denoted $\mathcal{L}^*$, is defined as the set of all points in $\mathrm{span}(\mathcal{L})$ that have integer inner products with all lattice points,

$$ \mathcal{L}^* = \{ \mathbf{w} \in \mathrm{span}(\mathcal{L}) : \forall \mathbf{y} \in \mathcal{L}, \langle \mathbf{w}, \mathbf{y} \rangle \in \mathbb{Z} \}. $$

Similarly, for a lattice basis $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$, we define the dual basis $\mathbf{B}^* = (\mathbf{b}_1^*, \dots, \mathbf{b}_n^*)$ to be the unique set of vectors in $\mathrm{span}(\mathcal{L})$ satisfying $\langle \mathbf{b}_i^*, \mathbf{b}_j \rangle = 1$ if $i = j$, and 0, otherwise. It is easy to show that $\mathcal{L}^*$ is itself a rank $n$ lattice and $\mathbf{B}^*$ is a basis of $\mathcal{L}^*$. Given a lattice $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$, we denote $\|\mathbf{B}\|_2 = \max_i \|\mathbf{b}_i\|$.

**Kissing number and related quantities.** For any lattice $\mathcal{L} \subset \mathbb{R}^n$ and $d > 0$, let $N(\mathcal{L}, r)$ denote the number of nonzero lattice vectors of length at most $r$. A natural question is to bound this quantity in terms of $r$. When $r < \lambda_1(\mathcal{L})$, only the origin lies inside the ball so $N(\mathcal{L}, r) = 0$. When $r = \lambda_1(\mathcal{L})$, this quantity is known as the kissing number $\tau(\mathcal{L})$ of the lattice:

$$ \tau(\mathcal{L}) = |\{\mathbf{x} \in \mathcal{L} : \|\mathbf{x}\| = \lambda_1(\mathcal{L})\}|. $$

Finally when $r \to \infty$, $N(\mathcal{L}, r) = \frac{r^n \mathrm{vol}(B_n(1))}{\det \mathcal{L}} + o(r^n)$ by the geometric interpretation of the determinant of a lattice. The precise behavior for intermediate values of $r$, however, is unclear and for that reason we introduce the quantity

$$ \gamma(\mathcal{L}) = \inf\{\gamma : \forall r \ge 1, N(\mathcal{L}, r\lambda_1(\mathcal{L})) \le \gamma \cdot r^n\}. \quad (1) $$

It is clear by the definition that $\gamma(\mathcal{L}) \ge \tau(\mathcal{L})$. The best known upper bound on this quantity comes from the breakthrough work of Kabatyanskii and Levenshtein [KL78] which implies [PS09] that

$$ \gamma(\mathcal{L}) \le 2^{0.402n}. \quad (2) $$

**Remark 7.** To the best of our knowledge, we do not know any family of lattices with kissing number $2^{\Omega(n)}$.<fnref n="8" /> Given this, it seems reasonable to conjecture that for any lattice that one would come across in practice, the kissing number is $2^{o(n)}$. Also, given the close connection between $\tau(\mathcal{L})$ and $\gamma(\mathcal{L})$, we conjecture that $\gamma(\mathcal{L})$ is also $2^{o(n)}$ for almost all lattices. We leave it as an open problem whether there exists a family of lattices for which $\gamma(\mathcal{L})$ is exponential in the dimension of the lattice. In view of the fact that $\gamma(\mathcal{L})$ can be anywhere between 1 and $2^{0.402n}$, we will study the dependence of the time complexity of our algorithms on $\gamma(\mathcal{L})$ by introducing

$$ \beta(\mathcal{L}) = \gamma(\mathcal{L})^{1/n}. \quad (3) $$

The upper bound above can then be reformulated as $\beta(\mathcal{L}) \le 2^{0.402}$ for any lattice $\mathcal{L}$.

**Probability distributions.** Given two random variables $X$ and $Y$ on a set $E$, we denote by $d_{\mathrm{SD}}$ the statistical distance between $X$ and $Y$, which is defined by

$$ d_{\mathrm{SD}}(X, Y) = \frac{1}{2} \sum_{z \in E} \left| \mathrm{Pr}[X = z] - \mathrm{Pr}[Y = z] \right| $$

<footnote n="8">⁸ Serge Vlăduț [Vlă19] gave a construction for a set of lattices and claimed their kissing number is $2^{0.0338n+o(n)}$, while Bennett, Golovnev, and Stephens-Davidowitz [BGS24] recently showed Vlăduț’s construction is invalid. Therefore, showing the existence of a family of lattices with exponential kissing numbers remains an open problem.</footnote>
$$ = \sum_{z \in E : \Pr_X[X=z] > \Pr_Y[Y=z]} \left( \Pr_X[X=z] - \Pr_Y[Y=z] \right). $$

We write $X$ is $\varepsilon$-close to $Y$ to denote that the statistical distance between $X$ and $Y$ is at most $\varepsilon$. Given a finite set $E$, we denote by $U_E$ a uniform random variable on $E$, i.e., for all $x \in E$, $\Pr_{U_E}[U_E = x] = \frac{1}{|E|}$.

**Discrete Gaussian Distribution.** For any $s > 0$, define $\rho_s(\mathbf{x}) = \exp(-\pi\|\mathbf{x}\|^2/s^2)$ for all $\mathbf{x} \in \mathbb{R}^n$. We write $\rho$ for $\rho_1$. For a discrete set $S$, we extend $\rho$ to sets by $\rho_s(S) = \sum_{\mathbf{x} \in S} \rho_s(\mathbf{x})$. Given a lattice $\mathcal{L}$, the discrete Gaussian $D_{\mathcal{L},s}$ is the distribution over $\mathcal{L}$ such that the probability of a vector $\mathbf{y} \in \mathcal{L}$ is proportional to $\rho_s(\mathbf{y})$:

$$ \Pr_{X \sim D_{\mathcal{L},s}} [X = \mathbf{y}] = \frac{\rho_s(\mathbf{y})}{\rho_s(\mathcal{L})}. $$

**Data processing inequality.** When analyzing the output distribution of an algorithm, it is often convenient to assume that the input distribution is ideal (e.g. uniform). On the other hand, we will want to run the algorithm on non-ideal input distribution (e.g. with a slight deviation from uniform). In this case, the output distribution will deviate from the ideal output distribution and it is important to quantify this divergence. The statistical distance satisfies the following useful inequality, known as the data processing inequality:

$$ d_{SD}(f(X), f(Y)) \le d_{SD}(X, Y) $$

for any two distributions $X$ and $Y$ and any (possibly randomized) algorithm $f$. In other words, the error does not increase under the application of $f$.

## 2.1 Lattice problems

The following problems play a central role in this paper. For convenience, when we discuss the running time of algorithms solving the problems below, we ignore polynomial factors in the bit-length of the individual input basis vectors (i.e. we assume that the input basis has bit-size polynomial in the ambient dimension $n$).

**Definition 8.** For $\delta = \delta(n) \ge 0$, $\sigma$ a function that maps lattices to non-negative real numbers, and $m = m(n) \in \mathbb{N}$, $\delta$-DGS$_\sigma^n$ (the Discrete Gaussian Sampling problem) is defined as follows: The input is a basis $\mathbf{B}$ for a lattice $\mathcal{L} \subset \mathbb{R}^n$ and a parameter $s > \sigma(\mathcal{L})$. The goal is to output a sequence of $m$ vectors whose joint distribution is $\delta$-close to $m$ independent samples from $D_{\mathcal{L},s}$.

We omit the parameter $\delta$ if $\delta = 0$, and the parameter $m$ if $m = 1$. We stress that $\delta$ bounds the statistical distance between the joint distribution of the output vectors and $m$ independent samples from $D_{\mathcal{L},s}$. We consider the following lattice problems.

**Definition 9.** The search problem SVP (Shortest Vector Problem) is defined as follows: The input is a basis $\mathbf{B}$ for a lattice $\mathcal{L} \subset \mathbb{R}^n$. The goal is to output a vector $\mathbf{y} \in \mathcal{L}$ with $\|\mathbf{y}\| = \lambda_1(\mathcal{L})$.

**Definition 10.** The search problem CVP (Closest Vector Problem) is defined as follows: The input is a basis $\mathbf{B}$ for a lattice $\mathcal{L} \subset \mathbb{R}^n$ and a target vector $\mathbf{t} \in \mathbb{R}^n$. The goal is to output a vector $\mathbf{y} \in \mathcal{L}$ with $\|\mathbf{y} - \mathbf{t}\| = \mathrm{dist}(\mathbf{t}, \mathcal{L})$.

**Definition 11.** For $\alpha = \alpha(n) < 1/2$, the search problem $\alpha$-BDD (Bounded Distance Decoding) is defined as follows: The input is a basis $\mathbf{B}$ for a lattice $\mathcal{L} \subset \mathbb{R}^n$ and a target vector $\mathbf{t} \in \mathbb{R}^n$ with $\mathrm{dist}(\mathbf{t}, \mathcal{L}) \le \alpha \cdot \lambda_1(\mathcal{L})$. The goal is to output a vector $\mathbf{y} \in \mathcal{L}$ with $\|\mathbf{y} - \mathbf{t}\| = \mathrm{dist}(\mathbf{t}, \mathcal{L})$.

Note that while our other problems become more difficult as the approximation factor $\gamma$ becomes smaller, $\alpha$-BDD becomes more difficult as $\alpha$ gets larger.
**Definition 12.** The search problems $\gamma$-CVPP and $\gamma$-BDDP are the preprocessing analogues of $\gamma$-CVP and $\gamma$-BDD respectively. The input for preprocessing is a basis $\mathbf{B}$ of lattice $\mathcal{L} \subset \mathbb{R}^n$. Given the advice from the preprocessing algorithm and the target vector $t \in \mathbb{R}^n$. The goal is to return solution of $\gamma$-CVP and $\gamma$-BDD respectively. The preprocessing algorithm is allowed to take arbitrary time.

For a lattice $\mathcal{L}$ and $\varepsilon > 0$, the smoothing parameter $\eta_{\varepsilon}(\mathcal{L})$ is the smallest $s$ such that $\rho_{1/s}(\mathcal{L}^*) = 1 + \varepsilon$. Recall that if $\mathcal{L}$ is a lattice and $v \in \mathcal{L}$ then $\rho_s(\mathcal{L} + v) = \rho_s(\mathcal{L})$ for all $s$. The smoothing parameter has the following well-known property.

**Lemma 13 ([Reg09, Claim 3.8]).** For any lattice $\mathcal{L} \subset \mathbb{R}^n$, $c \in \mathbb{R}^n$, $\varepsilon > 0$, and $s \ge \eta_{\varepsilon}(\mathcal{L})$,

$$ \frac{1 - \varepsilon}{1 + \varepsilon} \le \frac{\rho_s(\mathcal{L} + c)}{\rho_s(\mathcal{L})} \le 1. $$

**Corollary 14.** Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice, $q$ be a positive integer, and let $s \ge \eta_{\varepsilon}(q\mathcal{L})$. Let $C$ be a random coset in $\mathcal{L}/q\mathcal{L}$ sampled such that for any $c \in \mathcal{L}/q\mathcal{L}$, $\Pr[C = q\mathcal{L} + c] = \frac{\rho_s(q\mathcal{L} + c)}{\rho_s(\mathcal{L})}$. Also, let $U$ be a coset in $\mathcal{L}/q\mathcal{L}$ sampled uniformly at random. Then

$$ d_{SD}(C, U) \le 2\varepsilon. $$

*Proof.* By Lemma 13, we have that

$$ \rho_s(q\mathcal{L}) \ge \rho_s(q\mathcal{L} + c) \ge \frac{1 - \varepsilon}{1 + \varepsilon} \rho_s(q\mathcal{L}), $$

for any $c \in \mathcal{L}/q\mathcal{L}$ and hence,

$$ q^n \rho_s(q\mathcal{L}) \ge \sum_{c \in \mathcal{L}/q\mathcal{L}} \rho_s(q\mathcal{L} + c) = \rho_s(\mathcal{L}) $$

Therefore,

$$ \frac{\rho_s(q\mathcal{L} + c)}{\rho_s(\mathcal{L})} \ge \frac{1 - \varepsilon}{1 + \varepsilon} \cdot \frac{\rho_s(q\mathcal{L})}{\rho_s(\mathcal{L})} \ge \frac{1 - \varepsilon}{1 + \varepsilon} \cdot \frac{1}{q^n}. $$

We conclude that

$$ \begin{aligned} d_{SD}(C, U) &= \sum_{c \in \mathcal{L}/q\mathcal{L} : \Pr[C=c] < \Pr[U=c]} (\Pr[U=c] - \Pr[C=c]) \\ &\le \sum_{c \in \mathcal{L}/q\mathcal{L} : \Pr[C=c] < \Pr[U=c]} \Pr[U=c] \left(1 - \frac{1-\varepsilon}{1+\varepsilon}\right) \\ &\le \sum_{c \in \mathcal{L}/q\mathcal{L}} \Pr[U=c] \frac{2\varepsilon}{1+\varepsilon} \\ &\le \frac{2\varepsilon}{1+\varepsilon}, \end{aligned} $$

as needed.

We will need the following lemma which is initially proved in [Ban93].

**Lemma 15 ([DRS14, Lemma 2.13]).** For any lattice $\mathcal{L} \subset \mathbb{R}^n$, $s > 0$ and any $t \ge 1$,

$$ \Pr_{y \sim D_{\mathcal{L},s}} \left[ \|y\| \ge t \sqrt{\frac{n}{2\pi}} \cdot s \right] \le e^{-\frac{n}{2}(t-1)^2}. $$

The following lemma gives a bound on the smoothing parameter.

**Lemma 16 ([ADRS15, Lemma 2.7]).** For any lattice $\mathcal{L} \subset \mathbb{R}^n$, $\varepsilon \in (0, 1)$ and $k > 1$, we have $k\eta_{\varepsilon}(\mathcal{L}) > \eta_{\varepsilon k^2}(\mathcal{L})$
Micciancio and Peikert [MP13] showed the following result about the resulting distribution from the sum of many Gaussian samples.

**Theorem 17 ([MP13, Theorem 3.3]).** Let $\mathcal{L}$ be an $n$ dimensional lattice, $z \in \mathbb{Z}^m$ a nonzero integer vector, $s_i \ge \sqrt{2}\|z\|_{\infty} \cdot \eta_{\varepsilon}(\mathcal{L})$, and $\mathcal{L}+c_i$ arbitrary cosets of $\mathcal{L}$ for $i = 1, \dots, m$. Let $\mathbf{y}_i$ be independent vectors with distributions $D_{\mathcal{L}+c_i, s_i}$, respectively. Then the distribution of $\mathbf{y} = \sum_i z_i \mathbf{y}_i$ is $\varepsilon m$ close to $D_{Y,s}$, where $Y = \gcd(\mathbf{z}) \mathcal{L} + \sum_i z_i c_i$, and
$$s = \sqrt{\sum (z_i s_i)^2}.$$

We need to recall the definition of the honest Discrete Gaussian Sampling problem, introduced in [ADRS15].

**Definition 18 ([ADRS15, Definition 5.1]).** For $\varepsilon \ge 0$, $\sigma$ a function that maps lattices to non-negative real numbers, and $m \in \mathbb{N}$, the honest Discrete Gaussian Sampling problem $\varepsilon$-hDGS$_{\sigma}^m$ is defined as follows: the input is a basis $B$ for a lattice $\mathcal{L} \subset \mathbb{R}^n$ and a parameter $s > 0$. The goal is for the output distribution to be $\varepsilon$-close to $D_{\mathcal{L},s}$ for some independent random variable $m' \ge 0$. If $s > \sigma(\mathcal{L})$ then $m'$ must be equal to $m$.

**Theorem 19 ([ADRS15, Theorem 5.11]).** Let $\sigma$ be the function that maps a lattice $\mathcal{L}$ to $\sqrt{2}\eta_{1/2}(\mathcal{L})$. Then, there is an algorithm that solves $\exp(-\Omega(\kappa))$-hDGS$_{\sigma}^{2n/2}$ in time $2^{n/2+\text{polylog}(\kappa)+o(n)}$ for an $\kappa \ge \Omega(n)$.

We will need the following reduction from $\alpha$-BDD to DGS that was shown in [DRS14].

**Theorem 20 ([DRS14, Theorem 3.1]).** For any $\varepsilon \in (0, 1/200)$, lattice $\mathcal{L} \subset \mathbb{R}^n$, and $\alpha \le \frac{\sqrt{\ln(1/\varepsilon)/\pi - o(1)}}{2\eta_{\varepsilon}(\mathcal{L}^*)\lambda_1 \mathcal{L}}$. There exists an algorithm that solves $\alpha$-BDDP using $m \cdot \text{poly}(n)$ arithmetic operations where $m = O(\frac{n \log(1/\varepsilon)}{\sqrt{\varepsilon}})$. Moreover, the preprocessing advice only consists of $m$ vectors sampled from $D_{\mathcal{L}^*, \eta_{\varepsilon}(\mathcal{L}^*)}$.

**Remark 21.** We are going to use this reduction in the superpolynomial regime: typically $m$ will be exponential in $n$. This leaves unclear the space complexity of the reduction. The reduction works by evaluating a polynomial number of times functions of the form $\sum_{i=1}^m f_i(x)$ where each $f_i$ is a polynomial time computable function that depends on the $i^{th}$ DGS sample. Furthermore, all the complexities above are in terms of arithmetic operations, not bit complexity. If we assume that all the DGS samples have $\text{poly}(n)$ bit-size then the reduction has time complexity $m \cdot \text{poly}(n)$ and space complexity $O(\text{poly}(n) + \log m)$ excluding the storage space of the $m$ vectors provided by the DGS. Finally, as noted in the proof of the theorem in [DRS14], only the preprocessing is probabilistic and with probability at least $1 - 2^{-\Omega(n)}$ over the choice of the samples, the algorithm will deterministically solve all $\alpha$-BDD instances.

We need the following relation between the first minimum of lattice and the smoothing parameter of dual lattice. We will use this to compute the decoding distance of the BDD oracle.

**Lemma 22 (Variant of [ADRS15, Lemma 6.1]).** For any lattice $\mathcal{L} \subset \mathbb{R}^n$ and $\varepsilon \in (0, 1)$,

$$\sqrt{\frac{\ln(1/\varepsilon)}{\pi}} < \lambda_1(\mathcal{L})\eta_{\varepsilon}(\mathcal{L}^*) < \sqrt{\frac{\beta(\mathcal{L})^2 n}{2\pi e}} \cdot \varepsilon^{-1/n} \cdot (1 + o(1)), \quad (4)$$

and if $\varepsilon \le (e/\beta(\mathcal{L})^2 + o(1))^{-n/2}$, we also have

$$\sqrt{\frac{\ln(1/\varepsilon)}{\pi}} < \lambda_1(\mathcal{L})\eta_{\varepsilon}(\mathcal{L}^*) < \sqrt{\frac{\ln(1/\varepsilon) + n \ln \beta(\mathcal{L}) + o(n)}{\pi}}. \quad (5)$$

as $n$ tends to infinity.

**Remark 23.** As noted in [ADRS15] below Lemma 6.1, the inequality (4) actually holds for all $\varepsilon \in (0, 1)$ so we dropped the condition in the first case.
**Remark 24.** In Lemma 6.1 of [ADRS15], $\beta$ comes from Lemma 4.2 of the same paper and only needs to satisfy the equation $|\mathcal{L} \cap T_r| \le \beta^{n+o(n)}r^n$ for all $r$ where $T_r = \{x \in \mathbb{R}^n : r \le \|x\| \le (1+\frac{1}{n})r\}$, assuming the lattice is normalized so that $\lambda_1(\mathcal{L}) = 1$. A trivial upper bound on $|\mathcal{L} \cap T_r|$ is $N(\mathcal{L}, r')$, the number of point in $\mathcal{L}$ of radius at most $r' = (1+\frac{1}{n})r$. By our definitions (1) and (3), this is bounded by $\gamma(\mathcal{L})((1+\frac{1}{n})r)^n \le \beta(\mathcal{L})^{n\epsilon r}$ and therefore we can replace $\beta$ by our $\beta(\mathcal{L})$.

The following theorem proved in [CCL18], is required to solve SVP by an exponential number of calls to $\alpha$-BDD oracle.

**Theorem 25 ([CCL18, Theorem 8]).** Given a basis matrix $\mathbf{B} \in \mathbb{R}^{n \times n}$ for lattice $\mathcal{L}(\mathbf{B}) \subset \mathbb{R}^n$, a target vector $\mathbf{t} \in \mathbb{R}^n$, an $\alpha$-BDD oracle $\mathcal{BDD}_\alpha$ with $\alpha < 0.5$, and an integer scalar $p > 0$. Let $f_p^\alpha : \mathbb{Z}_p^n \to \mathbb{R}^n$ be $f_p^\alpha(\mathbf{s}) = -p \cdot \mathcal{BDD}_\alpha(\mathcal{L}, (\mathbf{B}\mathbf{s} - \mathbf{t})/p) + \mathbf{B}\mathbf{s}$, then the list $m = \{f_p^\alpha(\mathbf{s}) | \mathbf{s} \in \mathbb{Z}_p^n\}$ contains all lattice points within distance $p\alpha\lambda_1(\mathcal{L})$ to $\mathbf{t}$.

**Remark 26.** In the original Theorem 8 from [CCL18], there is an extra condition on the target vector $\mathbf{t}$, ie, $\mathbf{t}$ needs to satisfy $\mathrm{dist}(\mathcal{L}, \mathbf{t}) \le \alpha\lambda_1(\mathcal{L})$. However, a thorough inspection of the proof reveals that this condition is unnecessary, and essentially the same proof follows without it.

We will need the following theorems to sample the DGS vectors with a large width.

**Theorem 27 ([ADRS15], Proposition 2.17).** For any $\varepsilon \le 0.99$, there is an algorithm that takes as input a lattice $\mathcal{L} \in \mathbb{R}^n$, $M \in \mathbb{Z}_{>0}$ (the desired number of output vectors), and $s > 2^{n \log \log n / \log n} \cdot \eta_\varepsilon(\mathcal{L})$, and outputs $M$ independent samples from $D_{\mathcal{L},s}$ in time $M \cdot \mathrm{poly}(n)$.

**Lemma 28 ([ADRS15, Lemma 5.12]).** There is a probabilistic polynomial-time algorithm that takes as input a lattice $\mathcal{L} \subset \mathbb{R}^n$ of rank $n$ and an integer $a$ with $n/2 \le a < n$ and returns a super lattice $\mathcal{L}' \supset \mathcal{L}$ of index $2^a$ with $\mathcal{L}' \subseteq \mathcal{L}/2$ such that for any $\varepsilon \in (0, 1)$, we have $\eta_{\varepsilon'}(\mathcal{L}') \le \eta_\varepsilon(\mathcal{L})/\sqrt{2}$ with probability at least $1/2$ where $\varepsilon' := 2\varepsilon^2 + 2^{(n/2)+1-a}(1+\varepsilon)$.

## 2.2 Quantum Computation

In this paper we use the Dirac ket-bra notation. A qubit is a unit vector in $\mathbb{C}^2$ with two (ordered) basis vectors $\{|0\rangle, |1\rangle\}$. The following gates form a universal set of gates

$$ H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, \quad S = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix}, \quad T = e^{i\pi/8} \begin{bmatrix} e^{-i\pi/8} & 0 \\ 0 & e^{i\pi/8} \end{bmatrix}, \\ \mathrm{CNOT} = |0\rangle\langle 0| \otimes I + |1\rangle\langle 1| \otimes X. $$

The Toffoli gate, a three-qubit gate, is defined by

$$ \text{Toffoli}|a\rangle|b\rangle|c\rangle = \begin{cases} |a\rangle|b\rangle|1 \oplus c\rangle, & \text{if } a = b = 1; \\ |a\rangle|b\rangle|c\rangle, & \text{otherwise,} \end{cases} $$

for $a, b, c \in \{0, 1\}$. Toffoli gate can be efficiently decomposed into $\mathrm{CNOT}, H, S$, and $T$ gates [NC16] and hence it is considered as an elementary quantum gate in this paper. It is easy to see that a NAND gate can be implemented by a Toffoli gate: $\mathrm{Toffoli}|a\rangle|b\rangle|1\rangle = |a\rangle|b\rangle|\mathrm{NAND}(a, b)\rangle$, where $\mathrm{NAND}(a, b) = 0$, if $(a, b) = (1, 1)$, and $\mathrm{NAND}(a, b) = 1$, otherwise. In particular, Toffoli gate together with ancilla preparation are universal for classical computation, that is for any classical function, we can implement it as (controlled) quantum one, although at a non-negligible cost due to the reversibility of quantum circuits.

**Theorem 29 ([Ben89,LS90]).** Given any $\varepsilon > 0$ and any classical computation with running time $T$ and space complexity $S$, there exists an equivalent reversible classical computation with running time $O(T^{1+\varepsilon}/S^\varepsilon)$ and space complexity $O(S(1 + \ln(T/S)))$.

**Corollary 30.** Given any $\varepsilon > 0$ and any classical computation with running time $T$ and space complexity $S$, there exists an equivalent quantum circuit of size $O(T^{1+\varepsilon}/S^\varepsilon)$ using $O(S(1 + \ln(T/S)))$ qubits.
**Search problem.** One of the most well-known quantum algorithms is Grover's unstructured search algorithm [Gro96a]. Suppose we have a set of objects named {0, 1, ..., N − 1}, of which some are targets. We say that an oracle O identifies the targets if, in the classical (resp. quantum) setting, O ( i ) = 1 (resp. O | i 〉 = − | i 〉 ) when i is a target and O ( i ) = 0 (resp. O | i 〉 = | i 〉 ) otherwise. Given such an oracle O , the goal is to find a target j ∈ { 0 , 1 , ..., N − 1 } by making queries to the oracle O .

In the search problem, one will try to minimize the number of queries to the oracle. In the classical setting, one need O ( N ) queries to solve this problem. Grover, on the other hand, provided a quantum algorithm, that solves the search problem with only O ( √ N ) queries [Gro96b]. When the number of targets is unknown, Brassard et al. provided a modified Grover algorithm that solves the search problem with O ( √ N ) queries [BBHT98], which is of the same order as the query complexity of the Grover search. Moreover, Dürr and Høyer showed given an unsorted table of N values, there exists a quantum algorithm that finds the index of minimum with only O ( √ N ) queries [DH96], with constant probability of error.

**Theorem 31 ([DH96], Theorem 1).** Let T [1 , 2 , ..., N ] be an unsorted table of N items, each holding a value from an ordered set. Suppose that we have a quantum oracle O$_{T}$ such that O$_{T}$ | i 〉| 0 〉 = | i 〉| T [ i ] 〉 . Then there exists a quantum algorithm that finds the index y such that T [ y ] is the minimum with probability at least 1 / 2 and O ( √ N ) queries to O$_{T}$ .

2.3 Probability

We need the following lemma on the distribution of vector inner product which directly follows from the
Leftover Hash Lemma [ILL89].

**Lemma 32.** Let $\mathbb{G}$ be a finite abelian group, and let $f$ be a positive integer. Let $\mathcal{Y} \subseteq \{0, 1\}^f$. Define the inner product
$\langle \cdot, \cdot \rangle : \mathbb{G}^f \times \mathcal{Y} \to \mathbb{G}$ by $\langle x, y \rangle = \sum_i x_i y_i$ for all $x \in \mathbb{G}^f$, $y \in \mathcal{Y}$. Let $X, Y$ be independent and uniformly random
variables on $\mathbb{G}^f$, $\mathcal{Y}$, respectively. Then

$$
d_{SD}((\langle X, Y \rangle, X), (U_{\mathbb{G}}, X)) \leq \frac{1}{2} \cdot \sqrt{\frac{|\mathbb{G}|}{|\mathcal{Y}|}},
$$

where $U_{\mathbb{G}}$ is uniform in $\mathbb{G}$ and independent of $X$.

We will also need the Chernoff-Hoeffding bound [Hoe63].

**Lemma 33.** Let $X_1, \dots, X_M$ be the independent and identically distributed random boolean variables of expectation $p$. Then for $\epsilon > 0$,

$$
\mathrm{Pr} \left[ \frac{1}{M} \sum_{i=1}^{M} X_i \leq p(1 - \delta) \right] \leq \left( \frac{e^{-\delta}}{(1 - \delta)^{1 - \delta}} \right)^{pM} .
$$

3 Algorithms with a time-memory tradeoff for lattice problems

In this section, we present a new algorithm for Discrete Gaussian sampling above the smoothing parameter.

3.1 Algorithm for Discrete Gaussian Sampling

We now present the main result of this section.

**Theorem 34.** Let $n \in \mathbb{N}$, $q \ge 2$, $d \in [1, n]$ be positive integers, and let $\epsilon > 0$. Let $C$ be any positive integer. Let $\mathcal{L}$ be a lattice of rank $n$, and let $s \ge 2\sqrt{dq\eta_e(\mathcal{L})}$. There is an algorithm that, given $N = 160d^2 \cdot C \cdot q^{n/d}$ independent samples from $D_{\mathcal{L},s}$, outputs a list of vectors that is $(4\epsilon^{2d}N + 11Cq^{-5n/2})$-close to $Cq^{n/d}$ independent vectors from $D_{\mathcal{L}, \frac{\sqrt{8d+1}}{q}s}$.
The algorithm runs in time $C \cdot (10e \cdot d)^{8d} \cdot q^{8n+n/d+o(n)}$ and requires memory poly($d$) $\cdot q^{n/d}$.
**Require:** $L = \{x_1, \dots, x_N\}$ is a list of $N$ vectors in $\mathcal{L}$

1: $L_1 \leftarrow \{x_1, \dots, x_N\}$

2: $L_2 \leftarrow \{x_{\frac{N}{2}+1}, \dots, x_N\}$

3: $Q \leftarrow 0$

4: **while** $Q < q^{n/d}$ and $L_1$ is not empty **do**

5: $v \leftarrow$ be the first vector in $L_1$.

6: Find $8d$ vectors (by trying all $8d$-tuples) $x_{i_1}, \dots, x_{i_{8d}}$ from $L_2$ s.t. $c_{i_1} + \dots + c_{i_{8d}} - v \in q\mathcal{L}$.

7: **if** such vectors exist **then**

8: Output the vector $\frac{x_{i_1} + \dots + x_{i_{8d}} - v}{q} \in \mathcal{L}$

9: $Q \leftarrow Q + 1$.

10: Remove vectors $x_{i_1}, \dots, x_{i_{8d}}$ from $L_2$

11: **end if**

12: Remove vector $v$ from $L_1$

13: **end while**

<caption>**Algorithm 1:** TradeOffSieve($L$)</caption>

*Proof.* We prove the result for $C = 1$, and the general result follows by repeating the algorithm. Let $\{x_1, \dots, x_N\}$ be the $N$ input vectors and let $\{c_1, \dots, c_N\}$ be the corresponding cosets in $\mathcal{L}/q\mathcal{L}$. We will analyze Algorithm 1; note that it produces samples in a streaming fashion. The time complexity of the algorithm is

$$ \frac{N}{2} \cdot \binom{N/2}{8d} \le \frac{N}{2} \left( \frac{eN}{16d} \right)^{8d} \le (10e \cdot d)^{8d} \cdot q^{8n+n/d+o(n)}, $$

and memory requirement of the algorithm is immediate. We now show correctness: we will make repeated use of the data processing inequality (see Section 2) and accumulate the error terms until the end of the proof.

Let $\varepsilon' = \varepsilon^{2d}$ so that $s \ge \sqrt{2\eta\varepsilon'}(q\mathcal{L})$ by Lemma 16. First, we can assume that the vectors $x_i$ for $i \in [N]$ are obtained by first sampling $c_i \in \mathcal{L}/q\mathcal{L}$ such that $\Pr[c_i = c] = \Pr[D_{\mathcal{L},s} \in q\mathcal{L} + c]$ and then sampling the vector $x_i$ according to $D_{q\mathcal{L}+c_i,s}$. Indeed, let $X \sim D_{\mathcal{L},s}$ and $C$ be a random coset in $\mathcal{L}/q\mathcal{L}$ sampled such that $\Pr[C = q\mathcal{L} + c] = \frac{\rho_s(q\mathcal{L} + c)}{\rho_s(\mathcal{L})}$, then for any $x \in \mathcal{L}$,

$$ \Pr[X = x] = \frac{\rho_s(x)}{\rho_s(\mathcal{L})} = \frac{\rho_s(q\mathcal{L} + c)}{\rho_s(\mathcal{L})} \frac{\rho_s(x)}{\rho_s(q\mathcal{L} + c)} = \Pr[C = c] \underset{Y \sim D_{q\mathcal{L}+c,s}}{\Pr} [Y = x] $$

where $c = q\mathcal{L} + x$. Moreover, by Corollary 14, this distribution is $2\varepsilon'N$-close to sampling $c_i$ for $i \in [N]$, independently and uniformly from $\mathcal{L}/q\mathcal{L}$, and then sampling the vectors $x_i$ according to $D_{q\mathcal{L}+c_i,s}$. We now assume that the input is sampled from this distribution.

Second, we can assume that the algorithm initially gets only the corresponding cosets as input, and the vectors $x_{i_j} \in q\mathcal{L} + c_{i_j}$ for $j \in [8d]$, and $v \in q\mathcal{L} + c$ are sampled from $D_{q\mathcal{L}+c_{i_j},s}$ and $D_{q\mathcal{L}+c,s}$ only before such a tuple is needed in Step 8 of the algorithm. Indeed, notice that the test at line 6 does not actually depend on the particular value of the $x_{i_j}$ and $v$ but only on their cosets. Since any input vector is used only once in Step 8, these samples are independent of all prior steps. This implies, by Theorem 17, that the vector obtained in Step 8 of the algorithm is $2\varepsilon'$-close to being distributed as $D_{\mathcal{L},s} \frac{\sqrt{8d+1}}{q}$.

It remains to show that our algorithm finds $q^{n/d}$ vectors (with high probability). Let $N' = \frac{N}{2}$ be an integer, $X$ be a random variable uniform over $(\mathcal{L}/q\mathcal{L})^{N'}$, and let $Y$ be a random variable independent of $X$ and uniform over vectors in $\{0, 1\}^{N'}$ with Hamming weight $8d$. The number of such vectors is

$$ \binom{N'}{8d} \ge \left( \frac{N'}{8d} \right)^{8d} \ge q^{8n}. \qquad (6) $$
Let $U$ be a uniformly random coset of $\mathcal{L}/q\mathcal{L}$. By Lemma 32 and (6), we have

$$d_{\mathrm{SD}}(((\langle X, Y \rangle, X), (U, X))) \leq \frac{1}{2} \cdot \sqrt{\frac{q^n}{q^{8n}}} = \frac{1}{2} q^{-7n/2}.$$

By Markov inequality we have

$$ \begin{aligned} \mathrm{Pr}_{x \leftarrow X} \left[ d_{\mathrm{SD}}(\langle x, Y \rangle, U) \ge \frac{q^{-n}}{10} \right] &\le \frac{10}{q^{-n}} \mathrm{E}_{x \leftarrow X} \left[ d_{\mathrm{SD}}(\langle x, Y \rangle, U) \right] \\ &= \frac{20}{q^{-n}} d_{\mathrm{SD}}((\langle X, Y \rangle, X), (U, X)) \\ &\le \frac{20}{q^{-n}} \cdot \frac{1}{2} q^{-7n/2} = 10q^{-5n/2}. \end{aligned} $$

Hence, with probability at least $1 - 10q^{-5n/2}$ over the choice of $x \leftarrow X$, we have that $d_{\mathrm{SD}}(\langle x, Y \rangle, U) \le \frac{q^{-n}}{10}$ and thus for any $v \in \mathcal{L}/q\mathcal{L}$,

$$q^{-n} + \frac{q^{-n}}{10} > \mathrm{Pr}[\langle x, Y \rangle = v \bmod q\mathcal{L}] > q^{-n} - \frac{q^{-n}}{10}. \quad (7)$$

It follows that, by introducing a statistical distance of at most $10q^{-5n/2}$ on the input, we can assume that the input vectors in list $L_2$ satisfy (7). Notice that after the algorithm found $i$ vectors for any $i < q^{n/d}$, it has removed $8id$ vectors from $L_2$. We will show that for each vector from $L_1$ (which is uniformly sampled from $\mathcal{L}/q\mathcal{L}$) with constant probability we will find $8d$-vectors in Step 6.

After $i < q^{n/d}$ output vectors have been found, there are $M = N' - 8id$ vectors remaining in the list $L_2$. There are $\binom{M}{8d}$ different $8d$-combinations possible with vectors remaining in $L_2$.

$$ \begin{aligned} \binom{N'}{8d} / \binom{M}{8d} &= \frac{N' \cdots (N' - 8d + 1)}{M \cdots (M - 8d + 1)} \\ &< \left( \frac{N' - 8d}{N' - 8d(i+1)} \right)^{8d} \\ &< \left( 1 + \frac{8dq^{n/d}}{N' - 8dq^{n/d} - 8d} \right)^{8d} \\ &= \left( 1 + \frac{1}{10d - 1 - \frac{1}{q^{n/d}}} \right)^{8d} \quad \text{since } N' = 80d^2 q^{n/d} \text{ for } C = 1 \\ &\le \left( 1 + \frac{1}{10d - 3/2} \right)^{8d} < \frac{5}{2}. \end{aligned} \quad (8) $$

At the beginning of the algorithm, there are $\binom{N'}{8d}$ combinations, and hence by (7), each of the $q^n$ cosets appears at least $0.9q^{-n} \binom{N'}{8d}$ times. After $i < q^{n/d}$ output vectors have been found, there are only $\binom{M}{8d}$ combinations left, and $\binom{N'}{8d} - \binom{M}{8d}$ possible combinations have been removed. We say that a coset $c$ disappears if there is no set of $8d$ vectors in $L_2$ that add to $c$. In order for a coset to disappear, all of the at least $0.9q^{-n} \binom{N'}{8d}$ combinations from the initial list must be removed. Hence, the number of cosets that disappear is at most

$$ \frac{\binom{N'}{8d} - \binom{M}{8d}}{0.9q^{-n} \binom{N'}{8d}} < \frac{3/5}{0.9} q^n = \frac{2}{3} q^n \text{ distinct cosets by (8). Hence with probability at least } 1/3, \text{ we find } 8d \text{ vectors } \boldsymbol{x}_{i_1}, \dots, \boldsymbol{x}_{i_{8d}} \text{ from } L_2 \text{ such that } \boldsymbol{x}_{i_1} + \dots + \boldsymbol{x}_{i_{8d}} - \boldsymbol{v} \in q\mathcal{L}. \text{ By Chernoff-Hoeffding bound with probability greater than } 1 - e^{-d^2 q^{n/d}}, \text{ the algorithm finds at least } q^{n/d} \text{ vectors. In total, the statistical distance from the desired distribution is} $$

$$2\varepsilon' N + 2\varepsilon' q^{n/d} + 10 \cdot q^{-5n/2} + e^{-d^2 q^{n/d}} \le 4\varepsilon' N + 11 \cdot q^{-5n/2}.$$
**Corollary 35.** Let $n \in \mathbb{N}$, $q \in [4, \sqrt{n}]$ be an integer, and let $\varepsilon = q^{-32n/q^2}$. Let $\mathcal{L}$ be a lattice of rank $n$, and let $s \ge \eta_{\varepsilon}(\mathcal{L})$. There is an algorithm that outputs a list of vectors that is $q^{-\Omega(n)}$-close to $q^{16n/q^2}$ independent vectors from $D_{\mathcal{L},s}$. The algorithm runs in time $q^{13n+o(n)}$ and requires memory poly($n$) $\cdot q^{16n/q^2}$.

*Proof.* Choose $d$ so that $16d - 16 < q^2 \le 16d$, which is possible when $q \ge 4$, and let $\alpha = q/\sqrt{8d+1}$ — this is the ratio by which we decrease the Gaussian width in Theorem 34 — and note that $\alpha \ge 1.2$.

Let $p = [2\sqrt{dq}] < q^2$ and $k$ be the smallest integer such that $\alpha^k \cdot p \ge 2^{n \log \log n / \log n}$. Thus $k = O(n \log \log n / \log n)$. Let $g = \alpha^k \psi s \ge 2^{n \log \log n / \log n} \cdot \eta_{\varepsilon}(\mathcal{L})$. By Theorem 27, in time $N_0 \cdot \text{poly}(n)$, we get $N_0 = (160d^2)^k q^{n/d}$ samples from $D_{\mathcal{L},g}$.

We now iterate $k$ times the algorithm from Theorem 34. Initially we have $N_0$ vectors. At the beginning of the $i$-th iteration for $i \le k-1$, we have $N_i := N_0 \cdot (160d^2)^{-i}$ vectors that are $\Delta_i$-close to being independently distributed from $D_{\mathcal{L},\alpha^{-i}g}$, where $\alpha^{-i}g \ge \alpha p \cdot \eta_{\varepsilon}(\mathcal{L})$. Hence, we can apply Theorem 34 and get $N_{i+1} = N_i/160d^2$ vectors that are $\Delta_{i+1}$-close to being independently distributed from $D_{\mathcal{L},\alpha^{-(i+1)}g}$, where $\Delta_{i+1} \le \Delta_i + 4\varepsilon^{2d}N_i + 11(160d^2)^{k-i}q^{-5n/2}$. At each iteration we had $N_i \ge 160d^2 q^{n/d}$ vectors, a necessary condition to apply Theorem 34. Therefore after $k$ iterations, we have at least $N_k = N_0/(160d^2)^k = q^{n/d}$ samples that are $\Delta_k$-close to being independently distributed from $D_{\mathcal{L},\alpha^{-k}g}$, where

$$ 
\begin{aligned}
\Delta_k &\le 11q^{-5n/2} \sum_{i=1}^{k} (160d^2)^{k-i} + \sum_{i=0}^{k-1} 10d\varepsilon^{2d} N_i \\
&\le 11(160d^2)^k q^{-5n/2} + 10dq^{-4n} q^{n/d} \sum_{i=0}^{k-1} (160d^2)^{k-i} && \text{since } 16d \ge q^2 \\
&\le (11q^{-5n/2} + 10dq^{-4n+n/d}) (160d^2)^{k+1} = q^{-5n/2+o(n)} && \text{since } (160d^2)^{k+1} = q^{o(n)}.
\end{aligned}
$$

Any vector distributed as $D_{\mathcal{L},ps}$ is in $p\mathcal{L}$ with probability at least $p^{-n}$. We repeat the algorithm $2p^n = O(q^{2n})$ times to obtain $p^n \cdot 2 \cdot q^{n/d}$ vectors that are $2p^n q^{-5n/2+o(n)} = q^{-n/2+o(n)}$ close to $2p^n \cdot q^{n/d}$ independent samples from $D_{\mathcal{L},ps}$. Of these samples obtained, we only keep vectors that fall in $p\mathcal{L}$ and divide them by $p$. Let $M = p^n \cdot 2 \cdot q^{n/d}$. By Chernoff-Hoeffding (Lemma 33) with $P = p^{-n}$, and $\delta = \frac{1}{2}$, the probability to obtain less than $(1-\delta)PM = q^{n/d}$ samples is at most $(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}})^{PM} \le e^{-\frac{1}{10}q^{n/d}}$. Furthermore, $d \le \frac{q^2+16}{16}$ and $q \mapsto \frac{\ln q}{16+q^2}$ is decreasing for $q \ge 4$, hence for $q \le \sqrt{n}$,

$$ q^{n/d} \ge e^{16n \frac{\ln q}{16+q^2}} \ge e^{16n \frac{\ln \sqrt{n}}{16+n}} \ge e^{16 \ln \sqrt{n-o(1)}} = \Omega(n^8). $$

Hence with probability greater than $1 - e^{-\frac{1}{10}q^{n/d}} = 1 - q^{-\Omega(n^8)}$, we get $q^{n/d}$ vectors from the distribution $D_{\mathcal{L},s}$. The statistical distance from the desired distribution is $q^{-\Omega(n^8)} + q^{-n/2+o(n)} \le q^{-n/2+o(n)}$. We repeat this for $\frac{q^{16n/q^2}}{q^{n/d}}$ times, to get $q^{16n/q^2}$ vectors. The total statistical distance from the desired distribution is $\frac{q^{16n/q^2}}{q^{n/d}} \cdot q^{-n/2+o(n)} \le q^{-\Omega(n)}$. The total running time is bounded by

$$ q^{2n} \left( \frac{q^{16n/q^2}}{q^{n/d}} \right) \left( \text{poly}(n) \cdot N_0 + \sum_{i=0}^{k-1} (10ed)^{8d} \cdot (160d^2)^{k-i} q^{8n+n/d+o(n)} \right) \le q^{13n+o(n)}. $$

The memory usage is slightly more involved: we can think of the $k$ iterations as a pipeline with $k$ intermediate lists and we observe that as soon as a list (at any level) has more than $160d^2 q^{16n/q^2}$ elements, we can apply Theorem 34 to produce $q^{16n/q^2}$ vectors at the next level. Hence, we can ensure that at any time, each level contains at most $160d^2 q^{16n/q^2}$ vectors, so in total we only need to store at most $k \cdot 160d^2 q^{16n/q^2} = \text{poly}(n)q^{16n/q^2}$ vectors, to which we add the memory usage of the algorithm of Theorem 34 which is bounded by $\text{poly}(n) \cdot q^{n/d} \le \text{poly}(n) \cdot q^{16n/q^2}$. Finally, we run the filter $(p\mathcal{L})$ on the fly at the end of the $k$ iterations to avoid storing useless samples. $\square$
This tradeoff works for any $q \ge 4$, and the running time can be bounded by $c_1^{n+o(n)} \cdot q^{c_2n}$ for some constants $c_1$ and $c_2$ that we have not tried to optimize.

## 3.2 Algorithms for BDD and SVP

**Theorem 36.** Let $n \in \mathbb{N}$, $q \in [4, \sqrt{n}]$ be a positive integer. Let $\mathcal{L}$ be a lattice of rank $n$. There is a randomized algorithm that solves $0.1/q$-BDD in time $q^{13n+o(n)}$ and requires memory poly($n$) $\cdot q^{16n/q^2}$.

*Proof.* Let $\varepsilon = q^{-32n/q^2}$ and $s \ge \eta_{\varepsilon}(\mathcal{L}^*)$. From Corollary 35, there exists an algorithm that outputs $q^{16n/q^2}$ vectors whose distribution is statistically close to $D_{\mathcal{L}^*,s}$ in time $q^{13n+o(n)}$ and space poly($n$) $\cdot q^{16n/q^2}$. By repeating this algorithm poly($n$) times, we can therefore build a DGS$_{\eta_{\varepsilon}}^{\text{poly}(n)q^{16n/q^2}}$ oracle such that each call takes time $q^{13n+o(n)}$ and space poly($n$) $\cdot q^{16n/q^2}$.

By Theorem 56 we can construct a $\alpha$-BDD such that each call takes time $m \cdot \text{poly}(n)$ and space poly($n$), where $\alpha = \phi(\mathcal{L})/\lambda_1(\mathcal{L}) = \frac{\sqrt{\ln(1/\varepsilon)/\pi-o(1)}}{2\eta_{\varepsilon}(\mathcal{L}^*)\lambda_1(\mathcal{L})}$ and $m = O(\frac{n \log(1/\varepsilon)}{\sqrt{\varepsilon}}) = O(\frac{n^2}{q^2} q^{16n/q^2} \log q) \le \text{poly}(n)q^{16n/q^2}$. The preprocessing consists of poly($n$) calls to the DGS$_{\eta_{\varepsilon}}^m$ sampler described above and requires space $m \cdot \text{poly}(n)$. Hence the total complexity is $\text{poly}(n)q^{13n+o(n)} = q^{13n+o(n)}$ in time and $m \cdot \text{poly}(n) = \text{poly}(n)q^{16n/q^2}$ in space. By using inequality (4), in Lemma 22, we have that

$$ \lambda_1(\mathcal{L})\eta_{\varepsilon}(\mathcal{L}^*) < \sqrt{\frac{\beta(\mathcal{L})^2 n}{2\pi e}} \cdot \varepsilon^{-1/n}(1+o(1)). $$

Hence we can guarantee that

$$ \alpha(\mathcal{L}) \ge \sqrt{\frac{\ln(1/\varepsilon)}{2n(\beta^2/e)\varepsilon^{-2/n}}} \cdot (1-o(1)) \ge \frac{1}{q} \sqrt{\frac{32 \cdot e \cdot \ln q}{2\beta^2 q^{64/q^2}}} \cdot (1-o(1)) \ge (10q)^{-1}. $$

**Theorem 37.** Let $n \in \mathbb{N}$, $q \in [4, \sqrt{n}]$ be a positive integer. Let $\mathcal{L}$ be a lattice of rank $n$. There is a randomized algorithm that solves SVP in time $q^{13n+o(n)}$ and in space poly($n$) $\cdot q^{16n/q^2}$.

*Proof.* By Theorem 36, we can construct a $\frac{0.1}{q}$-BDD oracle in time $q^{13n+o(n)}$ and in space poly($n$) $\cdot q^{16n/q^2}$. Each execution of the BBD oracle now takes $m = O(\frac{n^2}{q^2} q^{16n/q^2})$ time. By Theorem 25, with $(10q)^n$ queries to $\frac{0.1}{q}$-BDD oracle, we can find the shortest vector. The total time complexity is $q^{13n+o(n)} + \frac{n^2}{q^2} q^{16n/q^2} \cdot (10q)^n = q^{13n+o(n)}$. $\square$

*Remark 38.* If we take $q = \sqrt{n}$, Theorem 37 gives a SVP algorithm that takes $n^{O(n)}$ time and poly($n$) space. The constant in the exponent of time complexity is worse than the best enumeration algorithms. When $q$ is a large enough constant, for any constant $\varepsilon > 0$, there exists a constant $C = C(\varepsilon) > 2$, such that there is a $2^{Cn}$ time and $2^{\varepsilon n}$ space algorithm for DGS, and SVP. In particular, the time complexity of the algorithm in this regime is worse than the best sieving algorithms.

*Remark 39.* In [ACK$^+$21], authors gave $2^{\varepsilon n}$ time reductions between the lattice problems in different $\ell_p$ norms. Their reduction increases the approximation factor by a constant that depends on $\varepsilon$. Combining their results with the above theorem gives an algorithm with a time-memory tradeoff for the constant-factor approximation of all lattice problems.

# 4 Quantum speedup for BDDP using QRAM

The goal of this section is to obtain a quantum speedup of Theorem 20. We improve the time complexity of the algorithm by almost the square root factor, but we also require the advice string to be stored in QRAM. Before presenting our contribution, we will give an overview of the known algorithms for BDDP.
Most of the known BDDP algorithms (including the one in [DRS14]) are based on the algorithm for decision-CVPP by Aharonov and Regev [AR05]. We first revisit the algorithm for decision-CVPP. In this work, the authors introduced the periodic Gaussian function $f: \mathbb{R}^n \to \mathbb{R}^+$,

$$f(t) := \frac{\rho(t + \mathcal{L})}{\rho(\mathcal{L})}$$

towards giving an algorithm for $O(\sqrt{n/\log n})$ approximation of decision-CVPP. They observed that by the Poisson summation formula, we get the identity

$$f(t) = \mathbb{E}_{w \sim \mathcal{D}_{\mathcal{L}^*}} [\cos(2\pi \langle w, t \rangle)]. \quad (9)$$

They also showed that when distance of the target vector $t$ from lattice $\mathcal{L}$ is at least $\sqrt{n}$, then $f(t)$ is negligible, and when distance between $t$ and lattice $\mathcal{L}$ is at most $\sqrt{\log n}$, then $f(t)$ is non-negligible. This function $f$ evaluated on any vector $t$ is an infinite sum, and is not easy to evaluate efficiently. Their algorithm crucially relied on the observation in Equation 9 that shows that the function $f$ can be estimated by using a polynomial size advice string with at most 1/poly($n$) error. They gave the estimator

$$f_W(t) = \frac{1}{N} \sum_{i=1}^{N} \cos(2\pi \langle w_i, t \rangle) \quad (10)$$

where $W = (w_1, \dots, w_N) \in \mathcal{L}^*$ are i.i.d. samples from $\mathcal{D}_{\mathcal{L}^*}$; and showed that $f_W \approx f$ with at most 1/poly($n$) error when $N$ is a large enough number bounded by a polynomial in $n$.

Later, Liu, Lyubashevsky, and Micciancio [LLM06] gave an algorithm for the approximation of search BDDP. The idea is to iteratively update the target vector $t$ such that its distance from the closest lattice vector decreases and eventually, it is easy to efficiently find the closest lattice vector. They are able to solve the $\alpha$-BDDP for $\alpha \le \mathcal{O}(\sqrt{\log n})$. Dadush, Regev and Stephens-Davidowitz, gave an improvement by a careful analysis of the function $f(t)$. They proposed that by iteratively updating $t$ by an approximation of

$$t + \frac{\nabla f(t)}{2\pi f(t)},$$

we can go near the closest lattice vector. Their algorithm solves $\alpha$-BDDP, for $\alpha = \frac{\sqrt{\ln(1/\epsilon)/\pi-\epsilon(1)}}{2\eta_{\epsilon}(\mathcal{L}^*)\lambda_1(\mathcal{L})}$. The advice string consists of $N$ vectors from $\mathcal{D}_{\mathcal{L}^*, \eta_{\epsilon}(\mathcal{L}^*)}$ and the algorithm performs $O(N + \text{poly}(n))$ arithmetic operations where $N = \mathcal{O}(\frac{n \log(1/\epsilon)}{\sqrt{\epsilon}})$. In this section, we will show that if the advice string is stored in QRAM then we can achieve the same approximation of BDDP by using only $O(\sqrt{N} + \text{poly}(n))$ arithmetic operations.

We will start with listing some of the lemmas and theorems from [DRS14] that we will directly use in our proof. After that, we will show the quantum improvement in the estimation of function $f_W$ and $\nabla f_W$. In the last part of this section, we will present the main result of this section.

## 4.1 Results from [DRS14]

**Lemma 40.** [DRS14][Lemma 2.14] Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice of rank $n$. Then, for all $t \in \mathbb{R}^n$, $f(t) \ge \rho(t)$.

**Lemma 41.** [DRS14][Lemma 4.7] Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice with $\rho(\mathcal{L}) = 1 + \epsilon$ for $\epsilon \in (0, 1/400)$. Let $W = (w_1, \dots, w_N)$ be sampled independently from $\mathcal{D}_{\mathcal{L}^*}$ with $N \ge \Omega(n/\sqrt{\epsilon})$. Then,

$$\Pr[\exists t, \|t\| \le \epsilon^{1/8}/(1000n) : \|\nabla f_W(t)/(2\pi f_W(t)) + t\| > \epsilon^{0.25}\|t\|] \le 2^{-\Omega(n)}.$$
**Lemma 42.** [DRS14][Lemma 4.10] Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice with $\rho(\mathcal{L}) = 1 + \varepsilon$ with $\varepsilon \in (0, 1/400)$. Let $s_\varepsilon = \left(\frac{1}{\pi} \ln \frac{2(1+\varepsilon)}{\varepsilon}\right)^{0.5}$. Let $W = (\mathbf{w}_1, \dots, \mathbf{w}_N)$ be sampled independently from $\mathcal{D}_{\mathcal{L}^*}$. Then, for $\varepsilon^2 \le s \le 10$, if $N \ge \Omega(n \ln(1/\varepsilon)/s^2)$,

$$ \mathrm{Pr}[\exists \mathbf{t} \in \mathbb{R}^n, \varepsilon^{1/8}/(1000n) \le \|\mathbf{t}\| \le s_\varepsilon : \|\nabla f_W(\mathbf{t}) - \nabla f(\mathbf{t})\| > s \|\mathbf{t}\|] \le 2^{-\Omega(N \cdot s^2)}. $$

**Lemma 43.** [DRS14][Lemma 4.12] Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice with $\rho(\mathcal{L}) = 1 + \varepsilon$ with $\varepsilon \in (0, 1/400)$. Let $s_\varepsilon = (\frac{1}{\pi} \ln \frac{2(1+\varepsilon)}{\varepsilon})^{0.5}$. Let $W = (\mathbf{w}_1, \dots, \mathbf{w}_N)$ be sampled independently from $\mathcal{D}_{\mathcal{L}^*}$. Then, for $\varepsilon^2 \le s \le 10$, if $N \ge \Omega(n \ln(1/\varepsilon)/s^2)$, then

$$ \mathrm{Pr}[\exists \mathbf{t} \in \mathbb{R}^n, \|\mathbf{t}\| \le s_\varepsilon : \|f_W(\mathbf{t}) - f(\mathbf{t})\| > s] \le 2^{-\Omega(N \cdot s^2)}. $$

**Lemma 44.** [DRS14][Part 1 of Lemma 4.5] Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice with $\rho(\mathcal{L}) = 1 + \varepsilon$ for some $\varepsilon > 0$, and let $W = (\mathbf{w}_1, \dots, \mathbf{w}_N)$ be sampled independently from $\mathcal{D}_{\mathcal{L}^*}$. Then, for $s \ge 0$, $N \min(s, s^2) \ge \Omega(n)$, and $\Delta_\varepsilon = \frac{4\pi\varepsilon}{1+\varepsilon} (\ln \frac{2+2\varepsilon}{\varepsilon} + 1)$, we have

$$ \mathrm{Pr}[\|H f_W(\mathbf{0}) + 2\pi \mathbf{I}_n\| > \Delta_\varepsilon + s] \le 2^{-\Omega(N \min s, s^2)}, $$

where $H f_W$ denote the Hessian matrix of $f_W$.

**Lemma 45.** [DRS14][Part 1 of Lemma 4.7] Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice with $\rho(\mathcal{L}) = 1 + \varepsilon$ for some $\varepsilon > 0$, and let $W = (\mathbf{w}_1, \dots, \mathbf{w}_N)$ be sampled independently from $\mathcal{D}_{\mathcal{L}^*}$. Then we have

$$ \mathrm{Pr} \left[ \exists \mathbf{t} \in \mathbb{R}^n, \|\mathbf{t}\| \le \frac{\varepsilon^{1/8}}{1000n} : \|\nabla f_W(\mathbf{t})\| > (2\pi + 4\varepsilon^{0.25}) \|\mathbf{t}\| \right] \le 2^{-\Omega(n)}, $$

and

$$ \mathrm{Pr} \left[ \exists \mathbf{t} \in \mathbb{R}^n, \|\mathbf{t}\| \le \frac{\varepsilon^{1/8}}{1000n} : |f_W(\mathbf{t})| < 1 - \frac{\varepsilon^{0.25}}{100} \right] \le 2^{-\Omega(n)}. $$

The following theorem tells us that if we can compute $f(\mathbf{t})$ and its gradient, and suppose that $t$ is sufficiently close to the lattice, then we can simply apply the gradient ascent algorithm to find a vector $t' = \frac{\nabla f(\mathbf{t})}{2\pi f(\mathbf{t})} + \mathbf{t}$ such that the new vector $t'$ is even closer to the closest lattice vector of $\mathbf{t}$.

**Theorem 46.** [DRS14][Corollary 4.3] Let $\varepsilon \in (0, 1/400)$ and $\mathcal{L} \subset \mathbb{R}^n$ a lattice with $\rho(\mathcal{L}) = 1 + \varepsilon$. Let $s_\varepsilon = \left(\frac{1}{\pi} \ln \frac{2(1+\varepsilon)}{\varepsilon}\right)^{1/2}$. Then for all $\mathbf{t} \in \mathbb{R}^n$ satisfying $\|\mathbf{t}\| \le s_\varepsilon/2$,

$$ \left\| \frac{\nabla f(\mathbf{t})}{2\pi f(\mathbf{t})} + \mathbf{t} \right\| \le 12(\varepsilon/2)^{1-2\delta(\mathbf{t})} \|\mathbf{t}\|, $$

where $\delta(\mathbf{t}) = \max(1/8, \|\mathbf{t}\|/s_\varepsilon)$. In particular, for $\delta(\mathbf{t}) \le 1/2 - 2/(\pi s_\varepsilon^2)$,

$$ \left\| \frac{\nabla f(\mathbf{t})}{2\pi f(\mathbf{t})} + \mathbf{t} \right\| \le \|\mathbf{t}\|/4. $$

## 4.2 Estimation of $f_W$ and $\nabla f_W$ in QRAM

**Theorem 47 (Amplitude estimation [BHMT02], follows from Theorem 12).** Let $\delta > 0$. Given natural number $M$ and access to an $(n+1)$-qubit unitary $U$ satisfying

$$ U|0^n\rangle|0\rangle = \sqrt{a}|\phi_1\rangle|1\rangle + \sqrt{1-a}|\phi_0\rangle|0\rangle, $$
where $|\phi_1\rangle$ and $|\phi_0\rangle$ are arbitrary n-qubit states and $0 < a < 1$, there exists a quantum algorithm that uses $O(M \cdot \log(1/\delta))$ applications of $U$ and $U^\dagger$ and $\tilde{O}(M \cdot \log(1/\delta))$ time, outputs an estimate $\tilde{a}$ that with probability $\ge 1 - \delta$ satisfies<fnref n="9" />

$$|a - \tilde{a}| \le \frac{1}{M}.$$

**Theorem 48.** Let $N$ be a positive integer, lattice $\mathcal{L} \subset \mathbb{R}^n$ and $W = \{w_1, \dots, w_N\}$ be the set of vectors from $\mathcal{L}^*$. Let $O_W : |j\rangle|0\rangle \to |j\rangle|w_j\rangle$. For any $\varepsilon, \delta > 0$, there exists a quantum algorithm that given target $t \in \mathbb{R}^n$ outputs $\tilde{f}_W(t)$ which satisfy $|\tilde{f}_W(t) - f_W(t)| \le \varepsilon$ with probability $1 - \delta$. The algorithm makes $O(\varepsilon^{-1} \cdot \log \frac{1}{\delta})$ queries to $O_W$ and requires $\varepsilon^{-1} \cdot \log \frac{1}{\delta} \cdot \text{poly}(\log n)$ elementary quantum gates.

*Proof.* We define the positive controlled rotation oracle as, for any $a \in [-1, 1]$

$$O_{CR^+} : |a\rangle|0\rangle \to \begin{cases} |a\rangle(\sqrt{a}|1\rangle + \sqrt{1-a}|0\rangle), & \text{if } a \ge 0 \\ |a\rangle|0\rangle, & \text{otherwise,} \end{cases}$$

which can be implemented up to negligible error by poly($\log n$) quantum elementary gates. Also, we define the cosine inner product oracle as for any $t, w \in \mathbb{R}^n$

$$O_{\cos} : |w\rangle|t\rangle|0\rangle \to |w\rangle|t\rangle|\cos(2\pi\langle w, t\rangle)\rangle,$$

which can also be implemented by poly($\log n$) quantum elementary gates. Prepare the state $\frac{1}{\sqrt{N}} \sum_{j=1}^N |j\rangle|0\rangle|t\rangle|0\rangle|0\rangle$,

and then we apply $O_W$ on the first and second registers, apply $O_{\cos}$ on the second, third, fourth registers, and apply $O_{CR^+}$ on the fourth and fifth registers, we have

$$\frac{1}{\sqrt{N}} \sum_{\substack{j \in [N] \text{ and} \\ \cos(2\pi \langle w_j, t \rangle) > 0}} |j\rangle|w_j\rangle|t\rangle|\cos(2\pi \langle w_j, t \rangle)\rangle \left( \sqrt{\cos(2\pi \langle w_j, t \rangle)}|1\rangle + \sqrt{1 - \cos(2\pi \langle w_j, t \rangle)}|0\rangle \right) \\ + \frac{1}{\sqrt{N}} \sum_{\substack{j \in [N] \text{ and} \\ \cos(2\pi \langle w_j, t \rangle) \le 0}} |j\rangle|w_j\rangle|t\rangle|\cos(2\pi \langle w_j, t \rangle)\rangle|0\rangle.$$

By rearranging the equation, we have

$$\frac{1}{\sqrt{N}} \sum_{\substack{j \in [N] \text{ and} \\ \cos(2\pi \langle w_j, t \rangle) > 0}} \sqrt{\cos(2\pi \langle w_j, t \rangle) |j\rangle |w_j\rangle |t\rangle |\cos(2\pi \langle w_j, t \rangle) |1\rangle} \\ + \frac{1}{\sqrt{N}} \left( \sum_{\substack{j \in [N] \text{ and} \\ \cos(2\pi \langle w_j, t \rangle) > 0}} \sqrt{1 - \cos(2\pi \langle w_j, t \rangle)} |j\rangle |w_j\rangle |t\rangle |\cos(2\pi \langle w_j, t \rangle) \rangle + \sum_{\substack{j \in [N] \text{ and} \\ \cos(2\pi \langle w_j, t \rangle) \le 0}} |j\rangle |w_j\rangle |t\rangle |\cos(2\pi \langle w_j, t \rangle) \rangle \right) |0\rangle \\ = \sqrt{a^+} |\phi_1\rangle |1\rangle + \sqrt{1 - a^+} |\phi_0\rangle |0\rangle,$$

where $a^+ = \sum_{\substack{j \in [N] \text{ and} \\ \cos(2\pi \langle w_j, t \rangle) > 0}} \frac{\cos(2\pi \langle w_j, t \rangle)}{N}$. By applying Theorem 47, we can estimate $a^+$ with additive error

$\varepsilon/2$ by using $O(\varepsilon^{-1})$ applications of $O_W$, $O_W^\dagger$, and $\varepsilon^{-1} \cdot \text{poly}(\log n)$ elementary quantum gates. Following the same strategy, we can also estimate $a^- = \sum_{\substack{j \in [N] \text{ and} \\ \cos(2\pi \langle w_j, t \rangle) < 0}} \frac{\cos(2\pi \langle w_j, t \rangle)}{N}$ with same additive error and by

<footnote n="9">⁹ The original Theorem 12 in [BHMT02] considered an estimator that output $\tilde{a}$ with additive error at most $1/M$ with probability $\ge 2/3$. One can repeat this process for $O(\log(1/\delta))$ times and take the median number to increase the success probability to $\ge 1 - \delta$.</footnote>
using same amount of queries and quantum elementary gates. Therefore, we can estimate $a^+ + a^- = \sum_{j \in [N]} \frac{\cos(2\pi \langle w_j, t \rangle)}{N}$ with additive error $\epsilon$. By repeating the procedure $\Theta(\log \frac{1}{\delta})$ times and take the median among them, we finish the proof.

**Theorem 49.** Let $N$ be a positive integer, lattice $\mathcal{L} \subset \mathbb{R}^n$, and $W = \{w_1, \dots, w_N\}$ be the set of vectors in $\mathcal{L}^*$. Let $O_W : |j\rangle|0\rangle \to |j\rangle|w_j\rangle$. For any $\epsilon, \delta > 0$, there exist a quantum algorithm that given target $t \in \mathbb{R}^n$ and $w_{max} \ge \max_{j \in [N]} \|w_j\|$, output $\nabla_i \tilde{f}_W(t)^{10}$ for any $i \in [n]$, which satisfy $|\nabla_i \tilde{f}_W(t) - \nabla_i f_W(t)| \le 2\pi\epsilon \|t\| \cdot w_{max}^2$, with probability $1 - \delta$. The algorithm makes $O(\epsilon^{-1} \cdot \log \frac{1}{\delta})$ queries to $O_W$ and requires $\epsilon^{-1} \cdot \log \frac{1}{\delta} \cdot \text{poly}(\log n)$ elementary quantum gates.

*Proof.* From Equation 10, we get $\nabla_i f_W(t) = \frac{-1}{N} \sum_{j=1}^{N} \sin(2\pi \langle w_j, t \rangle) \cdot (w_j)_i$ for $i \in [n]$. We observe that for all $i \in [n]$ and $j \in [N]$,

$$|\sin(2\pi \langle w_j, t \rangle) \cdot (w_j)_i| \le |2\pi \langle w_j, t \rangle \cdot w_{max}| \le 2\pi \|t\| \cdot w_{max}^2,$$

and hence $\left| \frac{\sin(2\pi \langle w_j, t \rangle) \cdot (w_j)_i}{2\pi \|t\| \cdot w_{max}^2} \right| \le 1$ for all $i \in [n]$ and $j \in [N]$. For simplicity, we define $g_i(w, t) = \frac{\sin(2\pi \langle w, t \rangle) \cdot (w)_i}{2\pi \|t\| \cdot w_{max}^2}$. Then we define the sine inner product oracle as for any $t, w \in \mathbb{R}^n$ and $i \in [n]$

$$O_{\sin} : |w\rangle|t\rangle|i\rangle|0\rangle \to |w\rangle|t\rangle|i\rangle|g_i(w, t)\rangle,$$

which can be implemented by $\text{poly}(\log n)$ quantum elementary gates. Also, we define the positive controlled rotation oracle as, for any $a \in \mathbb{R}$

$$O_{CR^+} : |a\rangle|0\rangle \to \begin{cases} |a\rangle(\sqrt{a}|1\rangle + \sqrt{1-a}|0\rangle), & \text{if } a \ge 0 \\ |a\rangle|0\rangle, & \text{otherwise,} \end{cases}$$

which can be implemented by $\text{poly}(\log n)$ quantum elementary gates.

Prepare the state $\frac{1}{\sqrt{N}} \sum_{j=1}^{N} |j\rangle|0\rangle|t\rangle|i\rangle|0\rangle|0\rangle$, and then we apply $O_W$ on the first and second registers, apply $O_{\sin}$ on the second, third, fourth, fifth registers, and apply $O_{CR^+}$ on the fifth and sixth registers, we have

$$\begin{aligned} & \frac{1}{\sqrt{N}} \sum_{\substack{j \in [N] \text{ and} \\ g_i(w_j, t) > 0}} |j\rangle|w_j\rangle|t\rangle|i\rangle|g_i(w_j, t)\rangle (\sqrt{g_i(w_j, t)}|1\rangle + \sqrt{1-g_i(w_j, t)}|0\rangle) \\ & + \frac{1}{\sqrt{N}} \sum_{\substack{j \in [N] \text{ and} \\ g_i(w_j, t) \le 0}} |j\rangle|w_j\rangle|t\rangle|i\rangle|g_i(w_j, t)\rangle|0\rangle \\ & = \frac{1}{\sqrt{N}} \sum_{\substack{j \in [N] \text{ and} \\ g_i(w_j, t) > 0}} \sqrt{g_i(w_j, t)}|j\rangle|w_j\rangle|t\rangle|i\rangle|g_i(w_j, t)\rangle|1\rangle \\ & + \frac{1}{\sqrt{N}} \left( \sum_{\substack{j \in [N] \text{ and} \\ g_i(w_j, t) > 0}} \sqrt{1-g_i(w_j, t)}|j\rangle|w_j\rangle|t\rangle|i\rangle|g_i(w_j, t)\rangle + \sum_{\substack{j \in [N] \text{ and} \\ g_i(w_j, t) \le 0}} |j\rangle|w_j\rangle|t\rangle|i\rangle|g_i(w_j, t)\rangle \right) |0\rangle \\ & = \sqrt{a^+} |\phi_1\rangle|1\rangle + \sqrt{1-a^+} |\phi_0\rangle|0\rangle, \end{aligned}$$

where $a^+ = \sum_{\substack{j \in [N] \text{ and} \\ g_i(w_j, t) > 0}} \frac{g_i(w_j, t)}{N}$. By applying Theorem 47, we can estimate $a^+$ with additive error $\epsilon/2$ by using $O(\epsilon^{-1})$ applications of $O_W$, $O_W^\dagger$, and $\epsilon^{-1} \cdot \text{poly}(\log n)$ elementary quantum gates. Follow the same

<footnote n="10">10 We are abusing the notation here, $\nabla_i \tilde{f}_W(t)$ just represent an estimated value of $\nabla_i f_W(t)$.</footnote>
strategy, we can also estimate $a^{-} = \sum_{\substack{j \in [N] \\ g_i(w_j, t) < 0}} \frac{g_i(w_j, t)}{N}$ with same additive error and by using same amount

of queries and quantum elementary gates. Therefore, we can estimate $a^{+} + a^{-} = \sum_{j \in [N]} \frac{g_i(w_j, t)}{N} = \frac{-\nabla_i f_W(t)}{2\pi \|t\| \cdot w_{max}^2}$ with additive error $\varepsilon$. By repeating the procedure $\Theta(\log \frac{1}{\delta})$ times and taking the median among them, we finish the proof.

We get the following corollary.

**Corollary 50.** Let $\varepsilon \in (0, 1/100)$, and $N = \lceil(n^8/\sqrt{\varepsilon})\rceil$ be a positive integer, lattice $\mathcal{L} \subset \mathbb{R}^n$ and $W = \{w_1, \dots, w_N\}$ be the set of vectors from $\mathcal{L}^*$ such that $\forall i \in [N], \|w_i\| \le 2n + 1$. Let $O_W: |j\rangle|0\rangle \to |j\rangle|w_j\rangle$. There exists a quantum algorithm that given target $t \in \mathbb{R}^n$ outputs $\tilde{f}_W(t)$ and $\nabla \tilde{f}_W(t)$ which satisfy

$$|\tilde{f}_W(t) - f_W(t)| \le \frac{\varepsilon^{1/4}}{100} \quad \text{and} \quad \|\nabla \tilde{f}_W(t) - \nabla f_W(t)\| \le \frac{\varepsilon^{1/4}}{100} \|t\|$$

with probability $1 - 2^{-\Omega(n)}$. The algorithm make $O(\varepsilon^{-1/4} \cdot n^4)$ queries to $O_W$ and require $\varepsilon^{-1/4} \cdot n^4 \cdot \text{poly}(\log n)$ elementary quantum gates.

## 4.3 BDDP in QRAM

From previous subsection, given $t$, we can estimate $f_W(t)$ with small additive error. In this subsection, we will replace $f_W(t)$ with the approximation function $\tilde{f}_W(t)$, and show that doing gradient ascent on the approximation function $\tilde{f}_W(t)$ still helps us to find the closest vector, and hence we can use $\tilde{f}_W$ to solve BDDP.

**Theorem 51.** Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice with $\rho(\mathcal{L}) = 1 + \varepsilon$ with $\varepsilon \in (0, 1/400)$ and $N$ be a positive integer. Let $s_\varepsilon = \left(\frac{1}{\pi} \ln \frac{2(1+\varepsilon)}{\varepsilon}\right)^{0.5}$, $\delta_{\max} = 0.5 - \frac{2}{\pi s_\varepsilon^2}$, and $W = (w_1, \dots, w_N)$ be a set of vectors from $\mathcal{L}^*$. Suppose that for some $\gamma > 0$, $t \in \mathbb{R}^n$, we can compute $\tilde{f}_W(t)$ and $\nabla \tilde{f}_W(t)$, and it holds that

1. $\|t\| \le \min\{\delta_{\max}s_\varepsilon, \sqrt{\ln(1/(4\gamma))/\pi}\}$,

2. $\|\nabla f_W(t) - \nabla f(t)\| \le \frac{\pi}{2}\gamma\|t\|$,

3. $\|\nabla f_W(t) - \nabla \tilde{f}_W(t)\| \le \frac{\pi}{2}\gamma\|t\|$,

4. $|f_W(t) - \tilde{f}_W(t)| \le \gamma$,

5. $|f_W(t) - \tilde{f}_W(t)| \le \gamma$.

Then,

$$\left\| \frac{\nabla \tilde{f}_W(t)}{2\pi \tilde{f}_W(t)} - \frac{\nabla f(t)}{2\pi f(t)} \right\| \le \frac{6\gamma}{\rho(t)} \|t\|.$$

*Proof.* It's easy to see that above conditions imply

$$\|\nabla \tilde{f}_W(t) - \nabla f(t)\| \le \pi\gamma\|t\|, \qquad (11)$$

and

$$|\tilde{f}_W(t) - f(t)| \le 2\gamma. \qquad (12)$$

From Lemma 40 and the condition on length of $t$, we get $f(t) \ge \rho(t) \ge 4\gamma$. From triangle inequality, we get

$$\begin{aligned} \left\| \frac{\nabla \tilde{f}_W(t)}{2\pi \tilde{f}_W(t)} - \frac{\nabla f(t)}{2\pi f(t)} \right\| &= \left\| \frac{\nabla \tilde{f}_W(t) - \nabla f(t)}{2\pi f(t)} \frac{f(t)}{\tilde{f}_W(t)} + \frac{\nabla f(t)}{2\pi f(t)} \left( \frac{f(t)}{\tilde{f}_W(t-1)} \right) \right\| \\ &\le \left\| \frac{\nabla \tilde{f}_W(t) - \nabla f(t)}{2\pi f(t)} \right\| \left\| \frac{f(t)}{\tilde{f}_W(t)} \right\| + \left\| \frac{\nabla f(t)}{2\pi f(t)} \right\| \left\| \frac{f(t)}{\tilde{f}_W(t)} - 1 \right\| \end{aligned} \qquad (13)$$
For the first term in 13, by using Equation (11) and Equation (12), we get

$$ \left\| \frac{\nabla \tilde{f}_W(\mathbf{t}) - \nabla f(\mathbf{t})}{2\pi f(\mathbf{t})} \right\| \frac{f(\mathbf{t})}{\tilde{f}_W(\mathbf{t})} \le \frac{\pi\gamma \|\mathbf{t}\|}{2\pi f(\mathbf{t})} \frac{f(\mathbf{t})}{f(\mathbf{t}) - 2\gamma} = \frac{\gamma \|\mathbf{t}\|}{2(f(\mathbf{t}) - 2\gamma)}. \quad (14) $$

For the second term in 13, by using Theorem 46 and Equation (12), we get

$$ \left\| \frac{\nabla f(\mathbf{t})}{2\pi f(\mathbf{t})} \right\| \left| \frac{f(\mathbf{t})}{\tilde{f}_W(\mathbf{t})} - 1 \right| \le \frac{5}{4} \|\mathbf{t}\| \left( \frac{f(\mathbf{t})}{f(\mathbf{t}) - 2\gamma} - 1 \right) = \frac{10\gamma}{4(f(\mathbf{t}) - 2\gamma)} \|\mathbf{t}\|. \quad (15) $$

From Equation (13), Equation (14) and Equation (15), we get

$$ \left\| \frac{\nabla \tilde{f}_W(\mathbf{t})}{2\pi \tilde{f}_W(\mathbf{t})} - \frac{\nabla f(\mathbf{t})}{2\pi f(\mathbf{t})} \right\| \le \frac{3\gamma \cdot \|\mathbf{t}\|}{f(\mathbf{t}) - 2\gamma} \le \frac{6\gamma}{\rho(\mathbf{t})} \|\mathbf{t}\|. $$

**Lemma 52.** Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice with $\rho(\mathcal{L}) = 1 + \varepsilon$ for $\varepsilon \in (0, 1/400)$. Let $W = (w_1, \dots, w_N)$ be sampled independently from $D_{\mathcal{L}^*}$ with $N \ge n^8/\sqrt{\varepsilon}$. Suppose that for some $\mathbf{t} \in \mathbb{R}^n$ such that $\|\mathbf{t}\| \le \varepsilon^{1/8}/(1000n)$, we can compute $\tilde{f}_W(\mathbf{t})$ and $\nabla \tilde{f}_W(\mathbf{t})$ which satisfy

$$ 1. \quad |\tilde{f}_W(\mathbf{t}) - f_W(\mathbf{t})| \le \frac{\varepsilon^{1/4}}{100}, $$

$$ 2. \quad \|\nabla \tilde{f}_W(\mathbf{t}) - \nabla f_W(\mathbf{t})\| \le \frac{\varepsilon^{1/4}}{100} \|\mathbf{t}\|. $$

Then with probability $1 - 2^{-\Omega(n)}$, $\left\| \frac{\nabla \tilde{f}_W(\mathbf{t})}{2\pi \tilde{f}_W(\mathbf{t})} + \mathbf{t} \right\| \le 3\varepsilon^{1/4} \|\mathbf{t}\|$ holds.

*Proof.* By Corollary 45, with at least $1 - 2^{-\Omega(n)}$ probability, $\|\nabla f_W(\mathbf{t})\| \le (2\pi + 4\varepsilon^{1/4})\|\mathbf{t}\|$ and $|f_W(\mathbf{t})| > 1 - \frac{\varepsilon^{1/4}}{100}$. By triangle inequality and both the assumptions, with probability at least $1 - 2^{-\Omega(n)}$, we have

$$ \|\nabla \tilde{f}_W(\mathbf{t})\| \le (2\pi + 5\varepsilon^{1/4})\|\mathbf{t}\| \quad \text{and} \quad |\tilde{f}_W(\mathbf{t})| > 1 - \frac{\varepsilon^{1/4}}{50}. \quad (16) $$

It implies that,

$$ \begin{aligned} \left\| \frac{\nabla \tilde{f}_W(\mathbf{t})}{2\pi \tilde{f}_W(\mathbf{t})} - \frac{\nabla f_W(\mathbf{t})}{2\pi f_W(\mathbf{t})} \right\| &\le \left\| \frac{\nabla \tilde{f}_W(\mathbf{t}) - \nabla f_W(\mathbf{t})}{2\pi \tilde{f}_W(\mathbf{t})} \right\| + \frac{\|\nabla f_W(\mathbf{t})\|}{2\pi} \left| \frac{1}{\tilde{f}_W(\mathbf{t})} - \frac{1}{f_W(\mathbf{t})} \right| \\ &\le \frac{\varepsilon^{1/4} \|\mathbf{t}\|}{2\pi(1 - \varepsilon^{1/4}/50)} + \frac{(2\pi + 5\varepsilon^{1/4}) \|\mathbf{t}\|}{2\pi} \cdot \frac{\varepsilon^{1/4}/100}{(1 - \varepsilon^{1/4}/100)(1 - \varepsilon^{1/4}/50)} \\ &\le 2\varepsilon^{1/4} \|\mathbf{t}\|, \end{aligned} $$

By Lemma 41, we know that, with at least $1 - 2^{-\Omega(n)}$ probability we have $\left\| \frac{\nabla f_W(\mathbf{t})}{2\pi f_W(\mathbf{t})} + \mathbf{t} \right\| \le \varepsilon^{1/4} \|\mathbf{t}\|$. Hence, by triangle inequality and union bound, we have $\left\| \frac{\nabla \tilde{f}_W(\mathbf{t})}{2\pi \tilde{f}_W(\mathbf{t})} + \mathbf{t} \right\| \le 3\varepsilon^{1/4} \|\mathbf{t}\|$ with probability greater than $1 - 2^{-\Omega(n)}$.

**Theorem 53.** Let $\mathcal{L} \subset \mathbb{R}^n$ be a lattice with $\rho(\mathcal{L}) = 1 + \varepsilon$ with $\varepsilon \in (0, 1/400)$. Let $s_\varepsilon = (\frac{1}{\pi} \ln \frac{2(1+\varepsilon)}{\varepsilon})^{0.5}$, $\delta_{\max} = 0.5 - \frac{2}{\pi s_\varepsilon^2}$, $\delta(\mathbf{t}) = \max\{1/8, \|\mathbf{t}\|/s_\varepsilon\}$ and $W = (w_1, \dots, w_N)$ be sampled independently from $D_{\mathcal{L}^*}$ where $N \ge n^8 \ln(1/\varepsilon)/\sqrt{\varepsilon}$. Suppose that for some $\mathbf{t} \in \mathbb{R}^n$ such that $\|\mathbf{t}\| \le \delta_{\max}s_\varepsilon$, we can compute $\tilde{f}_W(\mathbf{t})$ and $\nabla \tilde{f}_W(\mathbf{t})$ which satisfy

$$ 1. \quad |\tilde{f}_W(\mathbf{t}) - f_W(\mathbf{t})| \le \frac{\varepsilon^{1/4}}{100}, $$

$$ 2. \quad \|\nabla \tilde{f}_W(\mathbf{t}) - \nabla f_W(\mathbf{t})\| \le \frac{\|\mathbf{t}\| \cdot \varepsilon^{1/4}}{100}. $$
Then with probability at least $1 - 2^{-\Omega(n)}$, $\left\| \frac{\nabla \tilde{f}_W(\mathbf{t})}{2\pi \tilde{f}_W(\mathbf{t})} + \mathbf{t} \right\| \le \varepsilon^{(1-2\delta(\mathbf{t}))/4} \|\mathbf{t}\|$.

**Proof.** Lemma 52 shows that the theorem is satisfied for all $\mathbf{t}$ with $\|\mathbf{t}\| \le \varepsilon^{1/8}/(1000n)$. So we consider the case when $\varepsilon^{1/8}/(1000n) < \|\mathbf{t}\| \le \delta_{\max}s_{\varepsilon}$. By Lemma 40, for such $\mathbf{t}$,

$$f(\mathbf{t}) \ge \rho(\mathbf{t}) \ge e^{-\pi \delta_{\max}^2 s_{\varepsilon}^2} > \varepsilon^{\delta_{\max}^2/2} \ge \varepsilon^{1/4}/2.$$

Also we know that

- By Lemma 42, $\|\nabla f_W(\mathbf{t}) - \nabla f(\mathbf{t})\| \le \varepsilon^{1/4} \|\mathbf{t}\|/100$ holds with probability $\ge 1 - 2^{-\Omega(\varepsilon^{1/2}N/100^2)} = 1 - 2^{-\Omega(n)}$.

- By Lemma 43, $\|f(\mathbf{t}) - f(\mathbf{t}')\| \le \varepsilon^{1/4}/100$ holds with probability $\ge 1 - 2^{-\Omega(\varepsilon^{1/2}N/100^2)} = 1 - 2^{-\Omega(n)}$.

Therefore, by using Theorem 51 with $\gamma = \varepsilon^{1/4}/50\pi$, we have that with probability $\ge 1 - 2^{-\Omega(n)}$,

$$ \begin{aligned} \left\| \frac{\nabla \tilde{f}_W(\mathbf{t})}{2\pi \tilde{f}_W(\mathbf{t})} + \mathbf{t} \right\| & \le \frac{6\gamma}{\rho(\mathbf{t})} \|\mathbf{t}\| + \left\| \frac{\nabla f(\mathbf{t})}{2\pi f(\mathbf{t})} + \mathbf{t} \right\| \\ & \le \frac{\varepsilon^{1/4}}{25} \cdot e^{\pi \|\mathbf{t}\|^2} \|\mathbf{t}\| + 12(\varepsilon/2)^{1-2\delta(\mathbf{t})} \|\mathbf{t}\| \quad \text{(by Theorem 46)} \\ & \le \frac{3\varepsilon^{1/4}}{25} \left( \frac{2(1+\varepsilon)}{\varepsilon} \right)^{\delta(\mathbf{t})^2} \|\mathbf{t}\| + 12(\varepsilon/2)^{1-2\delta(\mathbf{t})} \|\mathbf{t}\| \\ & \le \frac{\varepsilon^{0.25-\delta(\mathbf{t})^2}}{6} \cdot \|\mathbf{t}\| + \frac{4}{5}(\varepsilon)^{(1-2\delta(\mathbf{t}))/4} \|\mathbf{t}\| \\ & \le \varepsilon^{(1-2\delta(\mathbf{t}))/4} \|\mathbf{t}\|. \end{aligned} $$

**Theorem 54.** For any integer $n > 0$, $\varepsilon \in (e^{-n^2}, 1/400)$ and lattice $\mathcal{L} \subset \mathbb{R}^n$, let $\phi(\mathcal{L}) = \frac{\sqrt{\ln(1/\varepsilon)/\pi-o(1)}}{2\eta_{\varepsilon}(\mathcal{L}^*)}$ and $N = \frac{n^8 \ln(1/\varepsilon)}{\sqrt{\varepsilon}}$. Given $N$ vectors sampled from $\mathcal{D}_{\mathcal{L}^*, \eta_{\varepsilon}(\mathcal{L}^*)}$ stored in QRAM, there exists an algorithm that solves $\frac{\phi(\mathcal{L})}{\lambda_1(\mathcal{L}^*)}$-BDD with probability greater than $1 - 2^{-\Omega(n)}$ using $\sqrt{N} \cdot \text{poly}(n)$ arithmetic operations, require $\mathcal{O}(\text{poly}(n) + \log N)$ classical space, $\text{poly}(n)$ qubits and QRAM of size $N \cdot \text{poly}(n)$.

**Proof.** Let $s_{\varepsilon} = (\frac{1}{\pi} \log(\frac{2(1+\varepsilon)}{\varepsilon}))^{1/2}$ and $\delta_{\max} = \frac{1}{2} - \frac{2}{\pi s_{\varepsilon}^2}$. Let $W = (w_1, \dots, w_N)$ be the given set of vectors sampled from $\mathcal{D}_{\mathcal{L}^*, \eta_{\varepsilon}(\mathcal{L}^*)}$.

The algorithm takes target $\mathbf{t} \in \mathbb{R}^n$ and set of vectors $W$. It then iteratively updates $\mathbf{t} \leftarrow \mathbf{t} + \frac{\nabla \tilde{f}_W(\mathbf{t})}{2\pi \tilde{f}_W(\mathbf{t})}$ for $1 + \lceil 8 \log(\sqrt{n}s_{\varepsilon})/\log(1/\varepsilon) \rceil$ times. It then scans the first $\sqrt{N}$ vectors from $W$ and take the first $n$ linearly independent vectors of length bounded by $\sqrt{n} \cdot \eta_{\varepsilon}(\mathcal{L}^*)$ as set $V^* = (v_1^*, \dots, v_n^*) \subset W$, if no such set exists then abort. Compute $V = (v_1, \dots, v_n)$ such that $v_i \cdot v_j^* = \delta_{i,j}$ and return $\sum c_i v_i$ where $c_i = \lceil v_i^* \cdot \mathbf{t} \rceil$.

By scaling the lattice appropriately, we can assume that $\rho(\mathcal{L}) = 1 + \varepsilon$, so that $\eta_{\varepsilon}(\mathcal{L}^*) = 1$. Let $\mathbf{t}' = \mathbf{t} - w$ such that $\|\mathbf{t}'\| \le \delta_{\max} s_{\varepsilon}$ for some $w \in \mathcal{L}$. There exists such a vector $\mathbf{t}'$ because of the promise of the $\phi(\mathcal{L})/\lambda_1(\mathcal{L})$-BDD and the fact that $\phi(\mathcal{L}) \le \delta_{\max} s_{\varepsilon}$. From Lemma 15, we get that with probability $1 - N \cdot e^{-2n^2} \ge 1 - 2^{\Omega(n)}$, $\forall i \in [N]$, $\|w_i\| \le 2n + 1$. Hence by using Corollary 50, we can estimate $\tilde{f}_W(\mathbf{t})$ and $\nabla \tilde{f}_W(\mathbf{t})$ which satisfy

$$|\tilde{f}_W(\mathbf{t}) - f_W(\mathbf{t})| \le \frac{\varepsilon^{1/4}}{100} \quad \text{and} \quad \|\nabla \tilde{f}_W(\mathbf{t}) - \nabla f_W(\mathbf{t})\| \le \frac{\varepsilon^{1/4}}{100} \|\mathbf{t}\|$$

with probability $1 - 2^{-\Omega(n)}$. The algorithm make $\mathcal{O}(\sqrt{N})$ arithmetic operations. Corollary 50 also says that the distribution of $\tilde{f}_W(\mathbf{t})$ and $\nabla \tilde{f}_W(\mathbf{t})$ is periodic over the lattice. Therefore, by using Theorem 53 we can say that by every update of $\mathbf{t}$ by $\mathbf{t} \leftarrow \mathbf{t} + \frac{\nabla \tilde{f}_W(\mathbf{t})}{2\pi \tilde{f}_W(\mathbf{t})}$, the output vector is of form $w + \mathbf{t}^*$ where $\|\mathbf{t}^*\|$ shrinks by factor of at least $\varepsilon^{(1-2(1/4))/4} = \varepsilon^{1/8}$ with probability $1 - 2^{-\Omega(n)}$. Hence by $1 + \lceil 8 \log(\sqrt{n}s_{\varepsilon})/\log(1/\varepsilon) \rceil$ updates, we get $\mathbf{t} = w + \mathbf{t}^*$ such that $\|\mathbf{t}^*\| \le 1/(2\sqrt{n})$. For the correctness of the proof, it is sufficient to show
that $w = \sum_i c_i v_i$. Note that $\langle v_i^*, t \rangle = \langle v_i^*, t^* \rangle + \langle v_i^*, w \rangle$. By Cauchy-Schwarz, we get $\langle v_i^*, t^* \rangle = 0$. Hence, we get the vector $w$ as the output with probability greater than $1 - 2^{-\Omega(n)}$.

Now, we will show that there exist a set $V^* \subset \{w_1, \dots, w_{n^2}\}$ containing $n$ linearly independent vectors of length at most $\sqrt{n}$ and algorithm will abort with probability at most $2^{-\Omega(n^2)}$ over the given set $W$. Let $W' = (w_1, \dots, w_{n^2})$. By Lemma 15, with at least $1 - n^2 \cdot e^{-n}$ probability all the vectors in set $W'$ has length at most $\sqrt{n} \cdot \eta_{\varepsilon}(\mathcal{L}^*)$. From the Lemma 44, we know that

$$ \|H f_{W'}(0) + 2\pi \mathbf{I}_n\| \le \frac{4\pi\varepsilon}{1+\varepsilon} \left( \log \left( \frac{2(1+\varepsilon)}{\varepsilon} + 1 \right) + 1 \right) < 2\pi $$

with probability at least $1 - 2^{-\Omega(n^2)}$. Hence, we have $H f_{W'}(0)$ is invertible and $H f_{W'}(0) = \frac{-4\pi^2}{m} \sum_{i=1}^m w_i w_i^T$ (from Equation 10). It implies that $W'$ spans $\mathbb{R}^n$ and completes the proof.

# 5 Improved algorithms for BDD

We obtain a BDD oracle with decoding distance $\alpha$ by using the same reduction as above but making each call cheaper. This is achieved by building a sampler that directly samples at the smoothing parameter, hence avoiding the $\sqrt{2}$ factor, allowing us to take a bigger $\varepsilon$. In [ADRS15], it was shown how to construct a dense lattice $\mathcal{L}'$ whose smoothing parameter $\eta(\mathcal{L}')$ is $\sqrt{2}$ times smaller than the original lattice, and that contains all lattice points of the original lattice. Suppose that we first use such a dense lattice to construct a corresponding discrete Gaussian sampler with standard deviation equal to $s = \sqrt{2\eta(\mathcal{L}')}$. We then do the rejection sampling on condition that the output is in the original lattice $\mathcal{L}$. We thus have constructed a discrete Gaussian sampler of $\mathcal{L}$ whose standard deviation is $\sqrt{2\eta(\mathcal{L}')}$, which implies that this procedure needs at least $2^{0.5n}$ input vectors to produce an output vector. $\mathcal{L}'$

The complexity of our BDD algorithms heavily depends on the quantity $\beta(\mathcal{L})$ which is related to the kissing number of the lattice (see Section 2). For this reason, we first provide complexity bounds that depend on $\beta(\mathcal{L})$ and then obtain complexity bounds in the worst case ($\beta(\mathcal{L}) \le 2^{0.402}$) as corollaries. We first show how to efficiently sample a discrete Gaussian at the smoothing parameter.

**Lemma 55.** There is a probabilistic algorithm that, given a lattice $\mathcal{L} \subset \mathbb{R}^n$, $m \in \mathbb{Z}_+$ and $s \ge \eta_{1/3}(\mathcal{L})$ as input, outputs $m$ samples from a distribution $(m \cdot 2^{-\Omega(n^2)}$)-close to $D_{\mathcal{L},s}$ in expected time $m \cdot 2^{n/2+o(n)}$ and space $(m + 2^{n/2}) \cdot 2^{o(n)}$. Furthermore, all samples have poly(n) bit-size.

*Proof.* Let $a = \frac{n}{2} + 4$. We repeat the following until we output $m$ vectors. We use the algorithm in Lemma 28 to obtain a lattice $\mathcal{L}' \supset \mathcal{L}$ of index $2^a$. We then run the algorithm from Theorem 19 with input $(\mathcal{L}', s)$ to obtain a list of vectors from $\mathcal{L}'$. We output the vectors in this list that belong to $\mathcal{L}$. The correctness of the algorithm, assuming it outputs anything, is clear as long as the samples obtained from Theorem 19 are (sufficiently) independent, which we will prove below.

By Theorem 19, we obtain, in time and space $2^{(n/2)+o(n)}$, $M \le 2^{n/2}$ vectors that are $2^{-\Omega(n^2)}$-close to $M$ vectors independently sampled from $D_{\mathcal{L}',s}$. The theorem guarantees that $M = 2^{n/2}$ if $s \ge \sqrt{2\eta_{1/2}(\mathcal{L}')}$.
Also, by Lemma 28, with probability at least $1/2$, we have $s \ge \eta_{1/3}(\mathcal{L}) \ge \sqrt{2\eta_{1/2}(\mathcal{L}')}$.
Note that when $s < \sqrt{2\eta_{1/2}(\mathcal{L}')}$, the samples obtained from Theorem 19 are still $2^{-\Omega(n^2)}$-close to $M$ vectors independently sampled from $D_{\mathcal{L}',s}$ but $M$ could be much lower than $2^{n/2}$ or even 0. On the other hand, if $s \ge \sqrt{2\eta_{1/2}(\mathcal{L}')}$ then $M = 2^{n/2}$.

Assume that $s \ge \sqrt{2\eta_{1/2}(\mathcal{L}')}$, which happens with probability at least $1/2$. From these $M = 2^{n/2}$ vectors, we will reject the vectors which are not in lattice $\mathcal{L}$. It is easy to see that the probability that a vector sampled from the distribution $D_{\mathcal{L}',s}$ is in $\mathcal{L}$ is at least $\rho_s(\mathcal{L})/\rho_s(\mathcal{L}') \ge \frac{1}{2^a}$ using Lemma 13. Thus, the probability that we obtain at least one vector from $\mathcal{L}$ (which is distributed as $D_{\mathcal{L}',s}$) is at least

$$ \frac{1}{2} \left( 1 - \left( 1 - \frac{1}{2^{2^a}} \right)^{2^{n/2}} \right) = \frac{1}{2} \left( 1 - \left( 1 - \frac{1}{2^{n/2+4}} \right)^{2^{n/2}} \right) \ge \frac{1}{2} \cdot \left( 1 - e^{-2^{n/2}/2^{n/2+4}} \right) = \frac{1}{2} \left( 1 - e^{-1/16} \right). $$
It implies that after rejection of vectors, with constant probability we will get at least one vector from $D_{\mathcal{L},s}$. Thus, the expected number of times we need to repeat the algorithm is $O(m)$ until we obtain vectors $y_1, \dots, y_m$ whose distribution is statistically close to being independently distributed from $D_{\mathcal{L},s}$. The time and space complexity is clear from the algorithm.

We can ensure that all samples have poly(n) bit-size by first generating more samples (say twice the amount) and throwing away all samples of norm larger than $\exp(\Omega(n^2))$. Since the vectors are sampled from a Gaussian with width at most$^{11}$ $\exp(O(n))$, the error induced by throwing away the tail of the distribution is smaller than $2^{-\Omega(n^2)}$.

## 5.1 Reduction from BDD to DGS

In [DRS14], authors gave an algorithm for BDDP which requires a sampler from the discrete Gaussian distribution *exactly at the smoothing parameter $\eta_\epsilon(\mathcal{L})$* which is generally not known. As BDDP allows preprocessing on the input lattice for arbitrary time, they are able to assume that preprocessing advice strings contains vectors sampled exactly at smoothing parameter. In this section, we present a modification of their algorithm, that gives a reduction from BDD to DGS. In this paper, our goal is to solve BDD so we will be very precise with the runtime and not assume any preprocessing.

**Theorem 56.** For any $\alpha > 0$, any $e^{-n^2} \le \epsilon \le \min(e^{-n^\alpha}, 1/200)$. There exists an algorithm that, on input $\mathcal{L}$ and with constant probability, constructs a classical and a quantum (with QRAM) $\frac{\phi(\mathcal{L})}{\lambda_1(\mathcal{L})}$-BDD oracle for $\mathcal{L}$ by doing poly(n) calls to a 0.5-hDGS$_{\eta_\epsilon}^m$ sampler on the lattice $\mathcal{L}^*$ and requires storage space $m \cdot \text{poly}(n)$, where $m = O\left(\frac{n \ln(1/\epsilon)}{\sqrt{\epsilon}}\right)$ and $\phi(\mathcal{L}) \equiv \frac{\sqrt{\ln(1/\epsilon)/\pi-o(1)}}{2\eta_\epsilon(\mathcal{L}^*)}$. Each call to the classical oracle takes time $m \cdot \text{poly}(n)$ and space $O(\text{poly}(n) + \ln m)$ excluding the storage space of the preprocessing. Every call to the quantum oracle with QRAM takes time $\sqrt{m} \cdot \text{poly}(n)$, classical space $O(\text{poly}(n) + \ln m)$, poly(n) qubits and requires a QRAM of size $m \cdot \text{poly}(n)$ that contains the preprocessed data$^{12}$.

The proof follows from Theorems 20 and 54. For completeness a detailed proof is given in Section A.

## 5.2 BDD when $\epsilon$ is small

In order to go further, we will make heavy use of Theorem 56 and Lemma 22 to relate the smoothing parameter to other parameters of the lattice. A small difficulty when applying Lemma 22 is the case distinction on $\epsilon$. We will start by using inequality (5) which will require to take very small values of $\epsilon$ when sampling the discrete Gaussian.

**Lemma 57.** For any sufficiently large $n$, any lattice $\mathcal{L} \subset \mathbb{R}^n$ and any $A$ such that $\frac{1}{2\ln 2} - b + o(1) \le A \le 1$, there exists a randomized algorithm that creates a classical and a quantum (with QRAM) $\alpha$-BDD oracle in time $2^{(A+1)n/2+o(n)}$ and space $2^{0.5n+o(n)}$, where $\alpha = \frac{1}{2}\sqrt{\frac{A}{A+b}}$ and $b = \log_2 \beta(\mathcal{L})$. Every call to the classical oracle takes time $2^{An/2+o(n)}$ and space poly(n), excluding the space of the preprocessed data. Every call to the quantum oracle with QRAM takes time $2^{An/4+o(n)}$, classical space poly(n), poly(n) qubits and requires a QRAM of size $2^{An/2+o(n)}$ that contains the preprocessed data.

*Proof.* Let $\epsilon = 2^{-An}$, $A \le 1$ to be fixed later. We know that $\eta_\epsilon(\mathcal{L}^*) > \eta_{1/3}(\mathcal{L}^*)$ for any sufficiently large $n$ ($n > \frac{1}{A} \log_2 3$) by the monotonicity of the smoothing parameter function. Hence the DGS$_{\eta_{1/3}}^m$ sampler from Lemma 55 can be used as a DGS$_{\eta_\epsilon}^m$ sampler, for any $m \in \mathbb{N}$.

By Theorem 56 we can construct a $\alpha$-BDD such that each call takes time $m \cdot \text{poly}(n) = 2^{An/2+o(n)}$ and space poly(n), where $\alpha = \phi(\mathcal{L})/\lambda_1(\mathcal{L}) = \frac{\sqrt{\ln(1/\epsilon)/\pi-o(1)}}{2\eta_\epsilon(\mathcal{L}^*)\lambda_1(\mathcal{L})}$ and $m = O\left(\frac{n \log(1/\epsilon)}{\sqrt{\epsilon}}\right) = 2^{An/2+o(n)}$. The

<footnote>$^{11}$ Here we are using our assumption that the basis vectors have size at most $2^{o(n)}$.</footnote>

<footnote>$^{12}$ Here, we are assuming that the Gaussian samples appear in the streaming fashion.</footnote>
preprocessing consists of poly(n) calls to the DGS<sub>η<sub>ε</sub></sub><sup>m</sup> sampler described above and requires space m·poly(n). Hence the total complexity is poly(n)·m·2<sup>n/2+o(n)</sup> = 2<sup>(A+1)n/2+o(n)</sup> in time and 2<sup>An/2+o(n)</sup> ≤ 2<sup>n/2+o(n)</sup> in space. By using Lemma 22, inequality (5), only valid when ε ≤ (e/β(L)<sup>2</sup> + o(1))<sup>-n/2</sup>, we have that

$$ \lambda_1(\mathcal{L})\eta_{\varepsilon}(\mathcal{L}^*) < \sqrt{\frac{\ln(1/\varepsilon) + n \ln \beta(\mathcal{L}) + o(n)}{\pi}} $$

Hence we can guarantee that

$$ \alpha = \frac{\sqrt{\ln(1/\varepsilon)/\pi - o(1)}}{2\eta_{\varepsilon}(\mathcal{L}^*)\lambda_1} > \frac{\sqrt{\ln(1/\varepsilon)/\pi - o(1)}}{2\sqrt{\frac{\ln(1/\varepsilon)+n \ln \beta(\mathcal{L})+o(n)}{\pi}}} = \frac{1}{2}\sqrt{\frac{\ln(1/\varepsilon)+o(1)}{\ln(1/\varepsilon)+n \ln \beta(\mathcal{L})}} = \frac{1}{2}\sqrt{\frac{A}{A+b}} + o(1) $$

where $b = \log_2 \beta(\mathcal{L})$. Furthermore, as noted above, this inequality is only valid when $\varepsilon \le (e/\beta^2 + o(1))^{-n/2}$, that is $A \ge \frac{1}{2\ln 2} - b + o(1)$. Finally, note that since $b \le 0.402$, we must have $A \ge 0.32$ and the inequality holds as soon as $n \ge 5 \ge \frac{1}{A} \log_2 3$. Finally note that Theorem 56 requires $\varepsilon \le 1/200$ which holds as soon as $n \ge 17 \ge \frac{1}{A} \ln 200$.

The quantum algorithm is exactly the same but using the quantum oracle of Theorem 56 which then has running time $\sqrt{m} \cdot \text{poly}(n) = 2^{An/4+o(n)}$ and requires a QRAM of size $m \cdot \text{poly}(n) = 2^{An/2+o(n)}$.

We can reformulate the previous lemma by expressing the complexity in terms of $\alpha$ instead of some arbitrary constant $A$.

**Corollary 58.** For any $n \ge 5$, any lattice $\mathcal{L} \subset \mathbb{R}^n$ and any $\alpha$ such that $\frac{1}{2}\sqrt{1-2b\ln 2} + o(1) \le \alpha < \frac{1}{2}\sqrt{\frac{1}{1+b}}$, there exists a randomized algorithm that creates a classical and a quantum (with QRAM) $\alpha$-BDD oracle in time $2^{(A+1)n/2+o(n)}$ and space $2^{0.5n+o(n)}$. Every call to the classical oracle takes time $2^{An/2+o(n)}$ and space poly(n), excluding the space of the preprocessed data; and every call to the quantum oracle with QRAM takes time $2^{An/4+o(n)}$, classical space poly(n), poly(n) qubits and requires a QRAM of size $2^{An/2+o(n)}$ that contains the preprocessed data, where $A = \frac{4b\alpha^2}{1-4\alpha^2}$ and $b = \log_2 \beta(\mathcal{L})$.

*Proof.* Apply Lemma 57 for some $A$ to be fixed later. Observe that $\alpha = \frac{1}{2}\sqrt{\frac{A}{A+b}}$ so $A = \frac{4b\alpha^2}{1-4\alpha^2}$. Now the constraints $\frac{1}{2\ln 2} - b + o(1) \le A \le 1$ become

$$ \begin{align*} \frac{1}{2\ln 2} - b + o(1) \le \frac{4b\alpha^2}{1-4\alpha^2} &\Leftrightarrow (\frac{1}{2\ln 2} - b + o(1))(1 - 4\alpha^2) \le 4b\alpha^2 \\ &\Leftrightarrow \frac{1}{4\ln 2} - \frac{b}{2} + o(1) \le \frac{\alpha^2}{\ln 2} \\ &\Leftrightarrow \frac{1}{2}\sqrt{1 - 2b\ln 2} + o(1) \le \alpha \end{align*} $$

and

$$ \frac{4b\alpha^2}{1-4\alpha^2} \le 1 \Leftrightarrow 4(1+b)\alpha^2 \le 1 \Leftrightarrow \alpha \le \frac{1}{2}\sqrt{\frac{1}{1+b}}. $$

## 5.3 BDD when $\varepsilon$ is large

The inequality (5) in Lemma 22 tells us that if we take an extremely small $\varepsilon$ to compute the BDD oracle, we can find a BDD oracle with $\alpha(\mathcal{L})$ almost $1/2$. However the time complexity for each call of the oracle will be very costly. On the other hand, if we use the inequality (4) in Lemma 22 with a larger $\varepsilon$, each call of the oracle will take much less time, but the constraint on the decoding coefficient $\alpha$ will be different. It is therefore important to study this second regime as well. Note that inequality (4) actually applies to all $\varepsilon \in (0, 1)$ but is mostly useful when $\varepsilon$ is large.
**Lemma 59.** For any sufficiently large $n$, any lattice $\mathcal{L} \subset \mathbb{R}^n$ and any $\frac{1}{n}\log_2 3 \le A \le 1$, there exists a randomized algorithm that creates a classical and a quantum (with QRAM) $\alpha$-BDD oracle in time $2^{(A+1)n/2+o(n)}$ and space $2^{0.5n+o(n)}$, where $\alpha = \frac{2^{-A}\sqrt{A\sqrt{2e\ln 2}}}{2\beta(\mathcal{L})} - o(1)$. Every call to this oracle takes time $2^{An/2+o(n)}$ and space poly($n$), excluding the space of the preprocessed data. Every call to the quantum oracle with QRAM takes time $2^{An/4+o(n)}$, classical space poly($n$), poly($n$) qubits and requires a QRAM of size $2^{An/2+o(n)}$ that contains the preprocessed data.

*Proof.* Let $\varepsilon = 2^{-An}$, $A \le 1$ to be fixed later. We know that $\eta_{\varepsilon}(\mathcal{L}^*) > \eta_{1/3}(\mathcal{L}^*)$ for any sufficiently large $n$ ($n > \frac{1}{A}\log_2 3$) by the monotonicity of the smoothing parameter function. Hence the $\text{DGS}_{\eta_{1/3}}^m$ sampler from Lemma 55 can be used as a $\text{DGS}_{\eta_{\varepsilon}}^m$ sampler, for any $m \in \mathbb{N}$.

By Theorem 56 we can construct an $\alpha$-BDD such that each call takes time $m \cdot \text{poly}(n) = 2^{An/2+o(n)}$ and space poly($n$), where $\alpha = \phi(\mathcal{L})/\lambda_1(\mathcal{L}) = \frac{\sqrt{\ln(1/\varepsilon)/\pi-o(1)}}{2\eta_{\varepsilon}(\mathcal{L}^*)\lambda_1(\mathcal{L})}$ and $m = O(\frac{n\log(1/\varepsilon)}{\sqrt{\varepsilon}}) = 2^{An/2+o(n)}$. The preprocessing consists of poly($n$) calls to the $\text{DGS}_{\eta_{\varepsilon}}^m$ sampler described above and requires space $m \cdot \text{poly}(n)$. Hence the total complexity is $\text{poly}(n) \cdot m \cdot 2^{n/2+o(n)} = 2^{(A+1)n/2+o(n)}$ in time and $2^{An/2+o(n)} \le 2^{n/2+o(n)}$ in space. By using inequality (4), in Lemma 22, we have that

$$ \lambda_1(\mathcal{L})\eta_{\varepsilon}(\mathcal{L}^*) < \sqrt{\frac{\beta(\mathcal{L})^2 n}{2\pi e}} \cdot \varepsilon^{-1/n}(1 + o(1)). $$

Hence we can guarantee that

$$ \alpha = \frac{\sqrt{\ln(1/\varepsilon)/\pi - o(1)}}{2\eta_{\varepsilon}(\mathcal{L}^*)\lambda_1(\mathcal{L})} > \frac{1}{2}\sqrt{\frac{2e \ln \frac{1}{\varepsilon} - o(1)}{n}} \cdot \beta(\mathcal{L})^{-1} \varepsilon^{\frac{1}{n}} \cdot (1 - o(1)) = \frac{2^{-A}\sqrt{A} \cdot \sqrt{2e \ln 2}}{2\beta(\mathcal{L})} - o(1). $$

The quantum algorithm is exactly the same but using the quantum oracle of Theorem 56 which then has running time $\sqrt{m} \cdot \text{poly}(n) = 2^{An/4+o(n)}$ and requires a QRAM of size $m \cdot \text{poly}(n) = 2^{An/2+o(n)}$.

**Corollary 60.** For any $n \ge 2$, any integer $m > 0$, any lattice $\mathcal{L} \subset \mathbb{R}^n$ and any $\frac{\sqrt{e \ln 3}}{\sqrt{2n\beta(\mathcal{L})}} \le \alpha \le \frac{1}{2\beta(\mathcal{L})}$, where $b = \log_2 \beta(\mathcal{L})$, there exists a randomized algorithm that creates a classical and a quantum (with QRAM) $(\alpha + o(1))$-BDD oracle in time $2^{(A+1)n/2+o(n)}$ and space $2^{n/2+o(n)}$. Every call to the classical oracle takes time $2^{An/2+o(n)}$ and space poly($n$), excluding the space of the preprocessed data; and every call to the quantum oracle with QRAM takes time $2^{An/4+o(n)}$, classical space poly($n$), poly($n$) qubits and requires a QRAM of size $2^{An/2+o(n)}$ that contains the preprocessed data, where

$$ A = -\frac{1}{2\ln 2}W(-\frac{4\alpha^2\beta(\mathcal{L})^2}{e}) $$

where $W$ is the principal branch of the Lambert W function. Furthermore, the above expression of $A$ is a continuous and increasing function of $\beta(\mathcal{L})$.

*Proof.* By Lemma 59, we can build an oracle for any $\frac{1}{n}\log_2 3 \le A \le 1$ such that the decoding radius is $\alpha = \frac{2^{-A}\sqrt{A\sqrt{2e\ln 2}}}{2\beta(\mathcal{L})} - o(1)$. Hence, we want to find $A$ such that

$$ \frac{2^{-A}\sqrt{A\sqrt{2e\ln 2}}}{2\beta(\mathcal{L})} = \alpha \quad \text{and} \quad \frac{1}{n}\log_2 3 \le A \le 1. $$

Let $f: A \mapsto 2^{-A}\sqrt{A}$ so that the first condition is equivalent to

$$ f(A) = \frac{2\alpha\beta(\mathcal{L})}{\sqrt{2e\ln 2}}. \qquad (17) $$

Now assume that (17) holds and let $y = -2A\ln(2)$, then it is equivalent to

$$ e^y y = -2 \ln(2) \frac{2\alpha^2 \beta(\mathcal{L})^2}{e \ln 2}, $$
that is

$$e^{y}y = -\frac{4\alpha^{2}\beta(\mathcal{L})^{2}}{e} \qquad (18)$$

This equation admits a solution if and only if

$$-\frac{4\alpha^2\beta(\mathcal{L})^2}{e} \geq -\frac{1}{e} \Leftrightarrow \alpha \leq \frac{1}{2\beta(\mathcal{L})} \qquad (19)$$

Assuming this is the case, (18) can admit up to two solutions. However, since the complexity increases with $A$, we want the solution that minimizes $A$, i.e. that maximizes $y$. The largest of the (up to) two solutions of (18) is always given by the principal branch $W$ of the Lambert $W$ function:

$$y = W\left(-\frac{4\alpha^2\beta(\mathcal{L})^2}{e}\right) \quad \text{that is} \quad A = -\frac{1}{2\ln 2}W\left(-\frac{4\alpha^2\beta(\mathcal{L})^2}{e}\right) \qquad (20)$$

and always satisfies $y \geq -1$. In particular, we always have $A \leq \frac{1}{2\ln 2}$. Now check that $f$ is strictly increasing over $[0, \frac{1}{2\ln 2}]$. Hence, the condition $\frac{1}{n}\log_2 3 \leq A$ is equivalent to

$$\begin{align*}
& f\left(\frac{1}{n}\log_2 3\right) \leq f(A) \\
\Leftrightarrow & f\left(\frac{1}{n}\log_2 3\right)^2 \leq \left(\frac{2\alpha\beta(\mathcal{L})}{\sqrt{2e\ln 2}}\right)^2 && \text{by (17)} \\
\Leftrightarrow & 2^{-\frac{2}{n}\log_2 3}\frac{1}{n}\log_2 3 \leq \frac{2\alpha^2\beta(\mathcal{L})^2}{e\ln 2} \\
\Leftrightarrow & \frac{e\ln 3}{2n\beta(\mathcal{L})^2}9^{-\frac{1}{n}} \leq \alpha^2 \\
\Leftrightarrow & \frac{e\ln 3}{2n\beta(\mathcal{L})^2} \leq \alpha^2. \tag{21}
\end{align*}$$

In summary, we can always take $A$ as in (20) assuming (19) and (21) hold.

## 5.4 Putting everything together

We have analyzed the construction of $\alpha$-BDDs in two regimes, based on Lemma 55. It is not a priori clear which construction is better and in fact we will see that it depends in a nontrivial way on the relation between $\alpha$ and $\beta(\mathcal{L})$.

**Theorem 61.** For any sufficiently large $n$, any $m > 0$, any $\frac{\sqrt{e\ln 3}}{\sqrt{2n\beta(\mathcal{L})}} \leq \alpha < \frac{1}{2}\sqrt{\frac{1}{1+b}}$ and any lattice $\mathcal{L} \subset \mathbb{R}^n$, there exists a randomized algorithm that creates a classical and a quantum (with QRAM) $(\alpha + o(1))$-BDD oracle in time $2^{(A+1)n/2+o(n)}$ and space $2^{n/2}$. Every call to the classical oracle takes time $2^{An/2+o(n)}$ and space poly($n$), excluding the space of the preprocessed data; and every call to the quantum oracle with QRAM takes time $2^{An/4+o(n)}$, classical space poly($n$), poly($n$) qubits and requires a QRAM of size $2^{An/2+o(n)}$ that contains the preprocessed data, where

$$A = \begin{cases} -\frac{1}{2\ln 2}W\left(-\frac{4\alpha^2\beta(\mathcal{L})^2}{e}\right) & \text{when } b < \frac{1-4\alpha^2}{2\ln 2} \\ \frac{4\alpha^2}{1-4\alpha^2}b & \text{when } b \geq \frac{1-4\alpha^2}{2\ln 2} \end{cases}$$

where $W$ is the principal branch of the Lambert $W$ function and $b = \log_2 \beta(\mathcal{L})$. Furthermore, the above expression of $A$ is a continuous and increasing function of $b$.

*Proof.* Let $\frac{\sqrt{e\ln 3}}{\sqrt{2n\beta(\mathcal{L})}} \leq \alpha < \frac{1}{2}\sqrt{\frac{1}{1+b}}$ and $b = \log_2 \beta(\mathcal{L})$. By Corollary 58, we can build an $\alpha$-BDD if $\frac{1}{2}\sqrt{1-2b\ln 2} \leq \alpha$, in which case the complexity will depend on $A = A_1(\alpha, b) := \frac{4b\alpha^2}{1-4\alpha^2}$. By Corollary 60, we can build an $\alpha$-BDD if $\alpha < \frac{1}{2}\sqrt{1-2b\ln 2}$, in which case the complexity will depend on $A = A_2(\alpha, b) := -\frac{1}{2\ln 2}W\left(-\frac{4\alpha^2\beta(\mathcal{L})^2}{e}\right)$. In both cases, the BDD oracle can be created in time $2^{(A+1)n/2+o(n)}$, space $2^{0.5n+o(n)}$ and each call takes time $2^{An/2+o(n)}$. Now observe that

$$\alpha < \frac{1}{2}\sqrt{1 - 2b \ln 2} \Leftrightarrow 4\alpha^2 < 1 - 2b \ln 2 \Leftrightarrow b < \frac{1 - 4\alpha^2}{2 \ln 2}.$$

Let $b^* := \frac{1-4\alpha^2}{2\ln 2}$, then there are two cases:
- If $b \ge b^*$ then $\frac{1}{2}\sqrt{1-2b\ln 2} \le \alpha$ so only Corollary 58 applies and we can build a $\alpha$-BDD. In this case the complexity exponent is $A_1(\alpha, b) = \frac{4\alpha^2}{1-4\alpha^2}b$.

- If $b < b^*$ then $\alpha < \frac{1}{2}\sqrt{1-2b\ln 2}$ so Corollary 60 applies but Corollary 58 does not for this particular value of $\alpha$. However, we can apply Corollary 58 to build a $\alpha'$-BDD oracle with $\alpha' \ge \alpha_1^{\min}(b) := \frac{1}{2}\sqrt{1-2b\ln 2} > \alpha$. We will show that the $\alpha$-BDD of Corollary 60 is always more efficient than the $\alpha'$-BDD of Corollary 58 in this case and the complexity exponent will thus be $A_2(\alpha, b) = -\frac{1}{2\ln 2}W(-\frac{4\alpha^2\beta(\mathcal{L})^2}{e})$.

Assume that $b < b^*$, we claim that $A_1(\alpha, b) \ge A_2(\alpha', b)$ for any $\alpha' \ge \alpha_1^{\min}(b)$. Indeed, on the one hand $A_2$ is an increasing function of $b$ so

$$A_2(\alpha, b) < A_2(\alpha, \frac{5}{18 \ln 2}) = -\frac{1}{2 \ln 2} W(-4\alpha^2 e^{-4\alpha^2}) = \frac{4\alpha^2}{2 \ln 2} = \frac{2\alpha^2}{\ln 2} \quad \text{since } W(x e^x) = x.$$

On the other hand, $A_1$ is an increasing function of $\alpha$ so

$$A_1(\alpha, b) \ge A_1(\alpha_1^{\min}(b), b) = \frac{1-2b\ln 2}{2\ln 2}$$

which is a decreasing function of $b$, therefore

$$A_1(\alpha, b) \ge A_1(\alpha_1^{\min}(b^*), b^*) = \frac{1-2b^* \ln 2}{2 \ln 2} = \frac{2\alpha^2}{\ln 2} > A_2(\alpha, b).$$

**Corollary 62.** For any sufficiently large integer $n$, any integer $m > 0$, any lattice $\mathcal{L} \subset \mathbb{R}^n$ there exists a randomized algorithm that creates a classical and a quantum (with QRAM) $1/3$-BDD oracle in time $2^{0.6604n+o(n)}$ and space $2^{0.5n+o(n)}$. Every call to the classical oracle takes time $2^{0.1604n+o(n)}$ and space poly($n$), excluding the space of the preprocessed data. Every call to the quantum oracle with QRAM takes time $2^{0.0802n+o(n)}$, classical space poly($n$), poly($n$) qubits and requires a QRAM of size $2^{0.1604n+o(n)}$ that contains the preprocessed data.

*Proof.* By Theorem 61, the value of $A$ increases with $b = \log_2 \beta(\mathcal{L})$. Since $b \le 0.402$ and $0.402 \ge \frac{5}{18 \ln 2}$, we always have $A \le \frac{4}{5}0.402 + o(1) \le 0.3208 + o(1)$ and we obtain the result.

# 6 Solving SVP by spherical caps on the sphere

We now explain how to reduce the number of queries to the $\alpha$-BDD oracle. Consider a uniformly random target vector $t$ such that $\alpha(1 - \frac{1}{n})\lambda_1(\mathcal{L}) \le \|t\| < \alpha\lambda_1(\mathcal{L})$, it satisfies the condition of Theorem 25, i.e. $\text{dist}(\mathcal{L}, t) \le \alpha\lambda_1(\mathcal{L})$. We enumerate all lattice vectors within distance $2\alpha\lambda_1(\mathcal{L})$ of $t$ and keep only the shortest nonzero one. We show that for any $\alpha \ge \frac{1}{3}$, we will get the shortest nonzero vector of the lattice with probability at least $2^{-cn+o(n)}$ for some $c$ that depends on $\alpha$. By repeating this $2^{cn+o(n)}$ times, the algorithm will succeed with constant probability. The optimal choice of $\alpha$ is not obvious and is deferred to Section 7.

**Theorem 63.** Assume we can create an $\alpha$-BDD oracle, with $\alpha \ge \frac{1}{3}$, in time $T_c$, space $S_c$ such that each call takes time $T_o$. Then there is a randomized algorithm that solves, with constant probability, SVP in space $S_c$ and time

$$T_c + \frac{2^{o(n)} T_o}{\alpha^n}$$

Furthermore, there is a quantum algorithm that solves SVP in classical space $S_c$ using a polynomial number of qubit and time

$$T_c + \frac{2^{o(n)} T_o}{\alpha^{n/2}}.$$

If we can create a quantum $\alpha$-BDD oracle with QRAM in classical time $T_c$ and space $S_c$ such that each call takes quantum time $T_o$, poly($n$) qubits and requires a QRAM of size $M_o$, then there is a quantum algorithm with QRAM that solves SVP in classical space $S_c$ using a polynomial number of qubit, time

$$T_c + \frac{2^{o(n)} T_o}{\alpha^{n/2}}.$$

and requires a QRAM of size $M_o$.
<figure><img src="image_2.png" /><figcaption>Fig. 1. One can cover the sphere of radius $\lambda_1$ by balls of radius $2\alpha\lambda_1$, where $\frac{1}{3} \le \alpha < \frac{1}{2}$, whose centers (here P) are at distance r from the origin O. Each such ball covers a spherical cap of half-angle $\phi$.</figcaption></figure>

*Proof.* On input lattice $\mathcal{L}(\mathbf{B})$, use the LLL algorithm [LLL82] to get a number $d$ (the norm of the first vector of the basis) that satisfies $\lambda_1(\mathcal{L}) \le d \le 2^{n/2}\lambda_1(\mathcal{L})$. For $i = 1, \dots, n^2$, let $d_i = d/(1 + \frac{1}{n})^i$. There exists a $j$ such that $\lambda_1(\mathcal{L}) \le d_j \le (1 + \frac{1}{n})\lambda_1(\mathcal{L})$. We repeat the following procedure for all $i = 1, \dots, n^2$:

Fix $N \in \mathbb{N}$ to be fixed later. For $j = 1$ to $N$, pick a uniformly random vector $v_{ij}$ on the surface of the ball of radius $r(1 - \frac{1}{n})d_i$. By Theorem 25, we can enumerate $2^n$ lattice points using the function $f_{ij}: \mathbb{Z}_2^n \to \mathcal{L}$ defined by

$$f_{ij}(\mathbf{x}) = \mathbf{B}\mathbf{x} - 2 \cdot \mathrm{BDD}_{\alpha}(\mathcal{L}, (\mathbf{B}\mathbf{x} - v_{ij})/2). \quad (22)$$

At each step we only store the shortest nonzero vector. At the end, we output the shortest among them. The running time of the algorithm is straightforward. We make $2^n$ queries to a $\alpha$-BDD oracle that takes time $T_o$, we further repeat this $n^2N$ times. Therefore the algorithm takes time $T_c + 2^n \cdot n^2N \cdot T_o$ and space $S_c$. This entire procedure is summarized in Algorithm 2.

**Require:** basis B of a lattice $\mathcal{L} \subset \mathbb{R}^n$

**Require:** an $\alpha$-BDD oracle (for a well-chosen $\alpha$)

**Ensure:** a shortest non-zero vector of $\mathcal{L}$

1: use LLL to get a number $d$ that satisfies $\lambda_1(\mathcal{L}) \le d \le 2^{n/2}\lambda_1(\mathcal{L})$.

2: $z \leftarrow$ any basis vector

3: **for** $i = 1, \dots, n^2$ **do**

4: $d_i \leftarrow d(1 + \frac{1}{n})^{-i}$

5: $N \leftarrow \frac{A_n(\lambda_1)}{V_{n-1}(2\alpha\lambda_1)}$ (see (24))

6: **for** $j = 1, \dots, N$ **do**

7: $v_{ij} \leftarrow$ random vector of norm $r(1 - \frac{1}{n})d_i$

8: **for** $\mathbf{x} \in \{0, 1\}^n$ **do**

9: $\mathbf{y} \leftarrow f_{ij}(\mathbf{x})$ (see (22))

10: **if** $\|\mathbf{y}\| < \|\mathbf{x}\|$ **then**

11: $z \leftarrow \mathbf{y}$ (shorter vector)

12: **end if**

13: **end for**

14: **end for**

15: **end for**

16: **return** $z$

<caption>**Algorithm 2:** Solving SVP by spherical caps on the sphere</caption>
To prove the correctness of the algorithm, it suffices to show that there exists an $i \in [n^2]$ for which the algorithm finds the shortest vector with high probability. Recall that there exists an $i$ such that $\lambda_1(\mathcal{L}) \le d_i \le (1+\frac{1}{n})\lambda_1(\mathcal{L})$ and let that index be $k$. We will show that for a uniformly random vector $v$ of length $r(1-\frac{1}{n})d_k$, if we enumerate $2^n$ vectors by the function $f: \mathbb{Z}_2^n \to \mathcal{L}$,

$$f(\mathbf{x}) = \mathbf{B}\mathbf{x} - 2 \cdot \text{BDD}_{\alpha}(\mathcal{L}, (\mathbf{B}\mathbf{x} - \mathbf{v})/2), \quad (23)$$

then with probability $\delta$, whose expression is derived in the next paragraph, there exists $\mathbf{x} \in \mathbb{Z}_2^n$ such that $f(\mathbf{x})$ is the shortest nonzero lattice vector; we will then choose $N = 1/\delta$ so that repeating $N$ times this process finds the shortest vector with probability bounded from below by a constant.

To that aim, we show that we can cover the sphere of radius $\lambda_1$ by $N$ balls of radius $2\alpha\lambda_1$ whose centers are at distance $r(1-\frac{1}{n})d_k \le r\lambda_1$ from the origin (see Figure 1 where we took $r = \alpha$). We have two concentric circles of radius $r(1-\frac{1}{n})d_k$ and $\lambda_1$, and let $P$ be a uniformly random point on the surface of the ball of radius $r(1-\frac{1}{n})d_k$. A ball of radius $2\alpha\lambda_1$ at center $P$ will cover the spherical cap with angle $\phi$ of the ball of radius $\lambda_1$. For convenience, write $r = s\lambda_1$ for some $s$. We can calculate the optimal choice of $r$ by noting that if we take the center of the caps to be at distance $r$ then the angle $\phi$ satisfies $\cos\phi = \frac{\lambda_1^2+r^2-4\alpha^2\lambda_1^2}{2r\lambda_1} = f(s)$ by the law of cosines, where $f(x) = \frac{1+x^2-4\alpha^2}{2x}$. We want to maximize the angle $\phi$, since the area we can cover increases with $\phi$. For minimizing $\cos(\phi)$, we minimize $f$. Check that $f(x)$ is decreasing until $\sqrt{1-4\alpha^2}$ and then increasing. We conclude that the optimal radius is when $s = \sqrt{1-4\alpha^2}$ and this gives an optimal angle $\phi$ such that $\cos\phi = \sqrt{1-4\alpha^2}$ and therefore $\sin\phi = 2\alpha$.

Now observe that the surface area of any such cap is lower bounded by the surface area of the base of the cap, which is a $(n-1)$-dimensional sphere of radius $\lambda_1 \sin\phi$. Hence the number of spherical caps required to cover the surface of sphere is in the order of $N := A_n(\lambda_1)/V_{n-1}(\lambda_1 \sin\phi)$ where $A_n$ (resp. $V_n$) is the surface area (resp. volume) of a $n$-dimensional sphere:

$$A_n(\lambda_1) = \frac{2\pi^{n/2}\lambda_1^{n-1}}{\Gamma(n/2)}, \quad V_{n-1}(\lambda_1 \sin \phi) = \frac{\pi^{(n-1)/2}\lambda_1^{n-1} \sin^{n-1} \phi}{\Gamma((n+1)/2)}. \quad (24)$$

Thus we have

$$N = \frac{A_n(\lambda_1)}{V_{n-1}(\lambda_1 \sin \phi)} = \frac{2^{o(n)}}{\sin^{n-1} \phi} = \frac{2^{-n+o(n)}}{\alpha^n}.$$

If we randomly choose the center $v$ of the sphere, the corresponding spherical caps will cover the shortest vector with probability at least $1/N$. By Theorem 25, the list $\{f(\mathbf{x}) \mid \mathbf{x} \in \mathbb{Z}_2^n\}$ will contain all lattice points within radius $2\alpha d_k$ from $v$. Hence, the list will contain a shortest vector with probability $1/N$. By repeating this process $N$ times, we can find the shortest vector with constant probability. Therefore, an upper bound of the total time complexity of our method can be expressed as

$$T_c + 2^n N \cdot T_o = T_c + \frac{2^{o(n)} T_o}{\alpha^n}.$$

In the quantum case, we can apply the quantum minimum finding algorithm in Theorem 31 to speed up search. Let $f$ be the function defined in (23). The algorithm works on three quantum registers and our goal is to build a superposition of states of the form $|s\rangle|f(s)\rangle|x\rangle$ where $x = \|f(s)\|$ most of the time (see the definition of $U$ below). Recall that we assumed that we can create a classical $\alpha$-BDD in time $T_c$ and space $S_c$ such that each call takes time $T_o$. Hence, we can first create the oracle in time $T_c$ and space $T_c$, and then hardcode the preprocessed data that we obtained into the oracle to obtain a new, self-contained, oracle that still runs in time $T_o$ and polynomial space. Let $\varepsilon = o(\frac{n}{\ln T_o})$ and apply Corollary 30 to construct a quantum circuit $O_{BDD}$ of size $T_o^{1+\varepsilon} = 2^{o(n)}T_o$ on poly(n) qubits that satisfies $O_{BDD}|s\rangle|0\rangle = |s\rangle|f(s)\rangle$ for all $s \in \mathbb{Z}_3^n$. We then construct another quantum circuit $U$ satisfying

$$U(|\omega\rangle|0\rangle) = \begin{cases} |\omega\rangle\|\|\omega\|\rangle & \text{if } \omega \neq 0 \\ |\omega\rangle\|\|Be_1\| + 1\rangle & \text{if } \omega = 0, \end{cases}$$
Here $e_1 \in \mathbb{Z}^n$ is a vector whose first coordinate is one and the rest are zero. We then consider the following quantum circuit (we have not drawn ancilla qubits):

<figure><img src="image_3.png" /></figure>

This circuit $\mathcal{O}$ has size $2^{o(n)}T_o^{1+\epsilon}$, satisfies $\mathcal{O}|s\rangle|0\rangle|0\rangle = |s\rangle|f(s)\rangle||f(s)\rangle$ if $f(s) \neq 0$ and $\mathcal{O}|s\rangle|0\rangle|0\rangle = |s\rangle|f(s)\rangle||Be_1\rangle + 1\rangle$ and uses poly(n) qubits. We can now apply the quantum minimum finding algorithm from Theorem 31 on the first and third registers and the index $s'$ of a shortest vector in this list. The output of the algorithm will be $f(s')$.

We can then build a circuit to generate the random vectors $v_{ij}$ above and therefore build a circuit that associates to every $(i, j, s)$ the lattice vector $f_{ij}(s)$. By a similar argument as above, using Corollary 30, we conclude that this quantum circuit has size $2^{o(n)}T_o$ and uses a polynomial number of qubits. Finally, we can apply the quantum minimum finding algorithm on the set of $(i, j, s) \in [n^2] \times [N] \times [2^n]$ and obtain the shortest vector of that list by making $\sqrt{n^2N2^n} = 2^{n/2+o(n)}\sqrt{N}$ queries to the BDD oracle. The total running time (including preprocessing) is therefore

$$T_c + 2^{n/2+o(n)}\sqrt{N} \cdot 2^{o(n)}T_o = T_c + \frac{2^{o(n)}T_o}{\alpha^{n/2}}$$

Lastly, we show that the quantum algorithm will output a shortest non-zero vector with constant probability. Since $||Be_1|| + 1 > \lambda_1(\mathcal{L})$, with at least $1/2$ probability one will find the index $(i, j, s)$ such that $f_{ij}(s)$ is a shortest in the list by using the quantum minimum finding algorithm. Therefore it suffices to show that there is an index $(i, j, s)$ such that $||f_{ij}(s)|| = \lambda_1(\mathcal{L})$. By the analysis above, the list $\{f_{ij}(s) | s \in \mathbb{Z}_3^n\}$ contains the shortest nonzero vector with at least constant probability. Hence, the algorithm will find the shortest vector of the lattice with constant probability.

When using a QRAM, the proof is exactly the same except that we put the samples in a QRAM instead of hardcoding them. This QRAM will have size $M_o$ and everything else is the same.

**Corollary 64.** There is a randomized algorithm that solves SVP in time $2^{1.669n+o(n)}$ and in space $2^{0.5n+o(n)}$ with constant probability. There is a quantum algorithm that solves SVP in time $2^{0.9497n+o(n)}$ and classical-space $2^{0.5n+o(n)}$ with a polynomial number of qubits. There is a quantum algorithm with QRAM that solves the SVP in time $2^{0.8345n+o(n)}$, using a QRAM of size $2^{0.293n+o(n)}$, poly(n) qubits and classical space $2^{0.5n}$.

*Proof.* Apply Theorem 61 with$^{13}\alpha = 0.3853$: since $0 \le b = \log_2 \beta(\mathcal{L}) \le 0.402$, we indeed have that $\alpha < \frac{1}{2}\sqrt{\frac{1}{1+b}}$ so we can create a $(\alpha + o(1))$-BDD oracle in time $T_c = 2^{(A+1)n/2+o(n)}$, space $S_c = 2^{0.5n+o(n)}$ such that each call takes time $T_o = 2^{An/2+o(n)}$ where $A = A(b)$ is given by Theorem 61. The theorem also guarantees that $A(b)$ increases with $b$ so $A \le A(0.402)$. But $0.402 \ge \frac{1-4\alpha^2}{2\ln 2} \approx 0.2929$ so $A(0.402) = \frac{4\alpha^2}{1-4\alpha^2} \cdot 0.402 \approx 0.5862$ by Theorem 61. Apply Theorem 63 to get a randomized algorithm that solves SVP in space $S_c$ and in time

$$T := T_c + \frac{2^{o(n)}T_o}{\alpha^n} = T = 2^{(A+1)n/2+o(n)} + 2^{An/2-n \log_2 \alpha+o(n)} = 2^{1.6690n+o(n)}.$$

For the quantum case, we use $\alpha = 0.3473$ and the same reasoning gives $A \approx 0.3738$ and the total complexity

$$T' := T_c + \frac{2^{o(n)}T_o}{\alpha^n} = T = 2^{(A+1)n/2+o(n)} + 2^{An/2-n/2 \log_2 \alpha+o(n)} = 2^{0.9497n+o(n)}.$$

<footnote n="13">13 The optimal value of $\alpha$ was found numerically, see Section 7.</footnote>
Finally, for the quantum algorithm with a QRAM, the running time of the quantum oracle is $T'_o = \sqrt{T_o}$ and it uses a QRAM of size $T_q = 2^{An/2+o(n)}$. We use $\alpha = 0.3853$ (again) to obtain $A \approx 0.5862$ and a total time complexity of

$$T'' := T_c + \frac{2^{o(n)} T'_o}{\alpha^n} = T = 2^{(A+1)n/2+o(n)} + 2^{An/4-n/2 \log_2 \alpha+o(n)} = 2^{0.8345n+o(n)}$$

with a QRAM of size $T_q = 2^{0.293n+o(n)}$.

# 7 Dependency of the SVP on a quantity related to the kissing number

In the previous sections, we obtained several algorithms for SVP and bounded their complexity using the only known bound on the quantity $\beta(\mathcal{L})$, which is related to the lattice kissing number (see Section 3): $\beta(\mathcal{L}) \le 2^{0.402}$. The complexity of those algorithms is highly affected by this quantity and since $\beta(\mathcal{L})$ can be anywhere between 1 and $2^{0.402}$ (see Section 2), we will study the dependence of the time complexity in $\beta(\mathcal{L})$. Recall that $b = \log_2 \beta(\mathcal{L})$.

In order to avoid doing the analysis three times, we introduce a factor $\nu$ that is 1 for classical algorithms and $\frac{1}{2}$ for quantum algorithms. We also introduce a factor $\xi$ that is 1 for classical and plain quantum algorithms, and $\frac{1}{2}$ for quantum algorithms with QRAMs. We now can reformulate the time complexity in Theorem 63 as

$$T_c + \frac{2^{o(n)} T_o}{\alpha^{\nu n}} \qquad (25)$$

We instantiate the algorithm in Theorem 63 with the $\alpha$-BDD oracle provided by Theorem 61 which satisfies

$$T_c = 2^{(A+1)n/2+o(n)}, \quad T_o = 2^{A\xi n/2+o(n)} \quad \text{and} \quad S_c = 2^{0.5n+o(n)}$$

where

$$A = \begin{cases} -\frac{1}{2 \ln 2} W(-\frac{4\alpha^2 \beta(\mathcal{L})^2}{e}) & \text{when } b < \frac{1-4\alpha^2}{2 \ln 2} \\ \frac{4\alpha^2}{1-4\alpha^2} b & \text{when } b \ge \frac{1-4\alpha^2}{2 \ln 2} \end{cases}.$$

The new expression of the time complexity to

$$2^{(A+1)n/2+o(n)} + 2^{(A\xi/2 - \nu \log_2 \alpha)n+o(n)}. \qquad (26)$$

Note that for the classical and plain quantum algorithms, the preprocessing is always negligible compared to cost of the queries but this is not necessarily the case when using a QRAM. The optimal choice of $\alpha$ is not obvious: by increasing the decoding radius, we reduce the number of queries but increase the cost of each queries. While we could, in principle, obtain closed-form expressions for the optimal value of $\alpha$, those are too complicated to be really helpful. Instead, we express it as an optimization program. Formally, we have $T = 2^{c(b,\nu,\xi)n+o(n)}$ where

$$c(b, \nu, \xi) = \min_{\alpha \in [\frac{1}{3}, \frac{1}{2})} \max \left( \frac{A+1}{2}, \frac{A\xi}{2} - \nu \log_2 \alpha \right)$$

where $A$ and $\cos \phi$ are given by the expressions above that depend on $\alpha$. We numerically computed the graph of this function and plotted the result on Figure 2 for the classical, plain quantum and quantum with QRAM algorithms respectively. As mentioned earlier, it is reasonable to conjecture that $\gamma(\mathcal{L}) = 2^{o(n)}$ for most lattices. We obtain the following result when $\gamma(\mathcal{L}) = \beta(\mathcal{L})^n$ is subexponential in $n$:

**Theorem 65.** There is an algorithm that, given a full rank lattice $\mathcal{L}$ of rank $n$ with $\gamma(\mathcal{L}) = 2^{o(n)}$, finds a shortest vector in $\mathcal{L}$ and runs

- in classical time $2^{1.292n+o(n)}$ and space $2^{0.5n}$,

- in quantum time $2^{0.750n+o(n)}$, classical space $2^{0.5n}$ and poly(n) qubits,

- in quantum time $2^{0.667n+o(n)}$, classical space $2^{0.5n}$, poly(n) qubits and using a QRAM of size $2^{0.167n+o(n)}$.
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** (Exponent $c(b)$ of the) time complexity of the spherical capping algorithm, plotted against $b = \log_2 \beta(\mathcal{L})$. The complexity of the algorithms is $2^{c(b)n+o(n)}$.</figcaption></figure>

# 8 Direct application to the ZLIP problem

The Lattice Isomorphism Problem (LIP) consist of recovering an orthogonal linear transformation sending one lattice to another, assuming its existence. The case of the trivial lattice $\mathbb{Z}^n$ is of particular interest (ZLIP) for cryptographic purposes [DvW22,BGPS23]. In [Duc23], the author proposed a reduction from ZLIP of dimension $n$ to SVP of dimension $n/2 + 1$.

**Theorem 66 ([Duc23]).** ZLIP can be solved by making polynomially many calls to a Shortest Vector Problem (SVP) oracle in dimension at most $n/2 + 1$.

Using Corollary 64, we directly obtain the following theorem.

**Theorem 67.** There exists a provable quantum algorithm that solves ZLIP in time $2^{0.417n+o(n)}$. The algorithm requires a QRAM of size $2^{0.147n+o(n)}$, poly(n) qubits and $2^{0.25n}$ classical space.

# Acknowledgments

We would like to thank Pierre-Alain Fouque, Paul Kirchner, Amaury Pouly and Noah Stephens-Davidowitz for useful comments and suggestions.

# References

ABF$^{+20}$. Martin R Albrecht, Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehlé, and Weiqiang Wen. Faster enumeration-based lattice reduction: root hermite factor time. In *Annual International Cryptology Conference*, pages 186–212. Springer, 2020. 2

ACK$^{+21}$. Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, and Noah Stephens-Davidowitz. Dimension-preserving reductions between SVP and CVP in different $p$-norms. In *SODA*, 2021. 17

ACKS21. Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, and Yixin Shen. Improved (provable) algorithms for the shortest vector problem via bounded distance decoding. In *38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)*. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. 1, 5
ADH<sup>+19</sup>. Martin R Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. In *Annual International Conference on the Theory and Applications of Cryptographic Techniques*, pages 717–746. Springer, 2019. 2

ADRS15. Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2" time using discrete gaussian sampling: Extended abstract. In *Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015*, pages 733–742, 2015. 1, 2, 3, 4, 5, 6, 10, 11, 12, 25, 39

Ajt96. Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In *Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996*, pages 99–108, 1996. 2

AKS01. Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In *Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, STOC '01*, pages 601–610, New York, NY, USA, 2001. ACM. 2, 4

ALNS19. Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, and Noah Stephens-Davidowitz. Slide reduction, revisited - filling the gaps in SVP approximation. CoRR, abs/1908.03724, 2019. 2

ANS18. Yoshinori Aono, Phong Q. Nguyen, and Yixin Shen. Quantum lattice enumeration and tweaking discrete pruning. In Thomas Peyrin and Steven Galbraith, editors, *Advances in Cryptology – ASIACRYPT 2018*, pages 405–434, Cham, 2018. Springer International Publishing. 3

AR05. Dorit Aharonov and Oded Regev. Lattice problems in NP ∩ coNP. J. ACM, 52(5):749–765, 2005. 18

AS18a. Divesh Aggarwal and Noah Stephens-Davidowitz. (gap/s) eth hardness of svp. In *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*, pages 228–238, 2018. 2

AS18b. Divesh Aggarwal and Noah Stephens-Davidowitz. Just take the average! an embarrassingly simple 2^n-time algorithm for SVP (and CVP). In *1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA*, pages 12:1–12:19, 2018. 2

Ban93. Wojciech Banaszczyk. New bounds in some transference theorems in the geometry of numbers. *Mathematical Annalen*, 296(1):625–635, 1993. 10

BBHT98. Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. *Fortschritte der Physik: Progress of Physics*, 46(4-5):493–505, 1998. 13

BDGL16. Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In *Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016*, pages 10–24, 2016. 2

Ben89. Charles H. Bennett. Time/space trade-offs for reversible computation. *SIAM J. Comput.*, 18(4):766–776, 1989. 12

BGPS23. Huck Bennett, Atul Ganju, Pura Peetathawatchai, and Noah Stephens-Davidowitz. Just how hard are rotations of zn? algorithms and cryptography with the simplest lattice. In *Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V*, page 252–281, Berlin, Heidelberg, 2023. Springer-Verlag. 35

BGS24. Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz. Difficulties constructing lattices with exponential kissing number from codes. https://arxiv.org/abs/2410.16660, 2024. 8

BHMT02. Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. *Quantum Computation and Information*, page 53–74, 2002. 6, 19, 20

BLP<sup>+13</sup>. Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. Classical hardness of learning with errors. In *Proceedings of the forty-fifth annual ACM symposium on Theory of computing*, pages 575–584. ACM, 2013. 5

BLS16. Shi Bai, Thijs Laarhoven, and Damien Stehlé. Tuple lattice sieving. *IACR Cryptology ePrint Archive*, 2016:713, 2016. 3, 7

Bri84. Ernest F. Brickell. Breaking iterated knapsacks. In *Advances in Cryptology, Proceedings of CRYPTO '84, Santa Barbara, California, USA, August 19-22, 1984, Proceedings*, pages 342–358, 1984. 2

BV14. Zvika Brakerski and Vinod Vaikuntanathan. Lattice-based FHE as secure as PKE. In *Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014*, pages 1–12, 2014. 2

CCL18. Yanlin Chen, Kai-Min Chung, and Ching-Yi Lai. Space-efficient classical and quantum algorithms for the shortest vector problem. *Quantum Information & Computation*, 18(3&4):285–306, 2018. 1, 3, 4, 5, 6, 12

CDLP13. Kai-Min Chung, Daniel Dadush, Feng-Hao Liu, and Chris Peikert. On the lattice smoothing parameter problem. In *2013 IEEE Conference on Computational Complexity*, pages 230–241, 2013. 39

CGH<sup>+96</sup>. Robert M. Corless, Gaston H. Gonnet, D. E. G. Hare, David J. Jeffrey, and Donald E. Knuth. On the lambertW function. *Adv. Comput. Math.*, 5(1):329–359, 1996. 7
dB89. Rudi de Buda. Some optimal codes have structure. *IEEE Journal on Selected Areas in Communications*, 7(6):893-899, 1989. 2

DH96. Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. CoRR, quant-ph/9607014, 1996. 13

DRS14. Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. On the closest vector problem with a distance guarantee. In *IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014*, pages 98-109, 2014. 3, 5, 6, 10, 11, 18, 19, 26

Duc18. Léo Ducas. Shortest vector from lattice sieving: A few dimensions for free. In Jesper Buus Nielsen and Vincent Rijmen, editors, *Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I*, volume 10820 of *Lecture Notes in Computer Science*, pages 125-145. Springer, 2018. 2

Duc23. Léo Ducas. Provable lattice reduction of zn with blocksize n/2. *Designs, Codes and Cryptography*, November 2023. 1, 35

DvW22. Léo Ducas and Wessel van Woerden. On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography. In *Advances in Cryptology - EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part III*, page 643-673, Berlin, Heidelberg, 2022. Springer-Verlag. 35

FT87. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. *Combinatorica*, 7(1):49-65, 1987. 2

Gen09. Craig Gentry. Fully homomorphic encryption using ideal lattices. In *Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009*, pages 169-178, 2009. 2

GN08. Nicolas Gama and Phong Q. Nguyen. Finding short lattice vectors within mordell's inequality. In *Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008*, pages 207-216, 2008. 2

GNR10. Nicolas Gama, Phong Q. Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Henri Gilbert, editor, *Advances in Cryptology - EUROCRYPT 2010*, pages 257-278, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. 2

GPV08. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In *Proceedings of the fortieth annual ACM symposium on Theory of computing*, pages 197-206. ACM, 2008. 5

Gro96a. Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In *Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing 1996*, pages 212-219. ACM, 1996. 13

Gro96b. Lov K. Grover. A fast quantum mechanical algorithm for database search. In *Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996*, pages 212-219, 1996. 13

Hel85. Bettina Helfrich. Algorithms to construct minkowski reduced and hermite reduced lattice bases. *Theor. Comput. Sci.*, 41(2-3):125-139, December 1985. 2

HK17. Gottfried Herold and Elena Kirshanova. Improved algorithms for the approximate k-list problem in euclidean norm. In Serge Fehr, editor, *Public-Key Cryptography - PKC 2017*, pages 16-40, Berlin, Heidelberg, 2017. Springer Berlin Heidelberg. 3, 7

Hoe63. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. *Journal of the American Statistical Association*, 58(301):13-30, 1963. 13

HPS11. Guillaume Hanrot, Xavier Pujol, and Damien Stehlé. Analyzing blockwise lattice algorithms using dynamical systems. In Phillip Rogaway, editor, *Advances in Cryptology - CRYPTO 2011*, pages 447-464, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. 2

HR07. Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In *Proceedings of the thirty-ninth annual ACM symposium on Theory of computing*, pages 469-477, 2007. 2

HS07. Guillaume Hanrot and Damien Stehlé. Improved analysis of kannan's shortest lattice vector algorithm. In *Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings*, pages 170-186, 2007. 2, 4

ILL89. Russell Impagliazzo, Leonid A Levin, and Michael Luby. Pseudo-random generation from one-way functions. In *Proceedings of the twenty-first annual ACM symposium on Theory of computing*, pages 12-24, 1989. 5, 13

Jr.83. Hendrik W. Lenstra Jr. Integer programming with a fixed number of variables. *Math. Oper. Res.*, 8(4):538-548, 1983. 2
Kan87. Ravi Kannan. Minkowski's convex body theorem and integer programming. *Math. Oper. Res.*, 12(3):415–440, 1987. 2, 4

KF16. Paul Kirchner and Pierre-Alain Fouque. Time-memory trade-off for lattice enumeration in a ball. Cryptology ePrint Archive, Report 2016/222, 2016. https://eprint.iacr.org/2016/222. 3, 7

Kho05. Subhash Khot. Hardness of approximating the shortest vector problem in lattices. *J. ACM*, 52(5):789–808, 2005. 2

KL78. Grigorii Anatol'evich Kabatiansky and Vladimir Iosifovich Levenshtein. On bounds for packings on a sphere and in space. *Problemy Peredachi Informatsii*, 14(1):3–25, 1978. 8

Kle00. Philip Klein. Finding the closest lattice vector when it's unusually close. In *Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms*, SODA '00, page 937–941, USA, 2000. Society for Industrial and Applied Mathematics. 5

KMPM19. Elena Kirshanova, Erik Mårtensson, Eamonn W Postlethwaite, and Subhayan Roy Moulik. Quantum algorithms for the approximate k-list problem and their application to lattice sieving. In *International Conference on the Theory and Application of Cryptology and Information Security*, pages 521–551. Springer, 2019. 3

LLL82. A.K. Lenstra, H.W. Lenstra, and Lászlo Lovász. Factoring polynomials with rational coefficients. *Math. Ann.*, 261:515–534, 1982. 2, 31

LLM06. Yi-Kai Liu, Vadim Lyubashevsky, and Daniele Micciancio. On bounded distance decoding for general lattices. In *Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques*, pages 450–461. Springer, 2006. 18

LMV15. Thijs Laarhoven, Michele Mosca, and Joop Van De Pol. Finding shortest lattice vectors faster using quantum search. *Designs, Codes and Cryptography*, 77, 12 2015. 2, 3, 4

LO85. J. C. Lagarias and Andrew M. Odlyzko. Solving low-density subset sum problems. *J. ACM*, 32(1):229–246, 1985. 2

LS90. Robert Y. Levin and Alan T. Sherman. A note on bennett's time-space tradeoff for reversible computation. *SIAM J. Comput.*, 19(4):673–677, 1990. 12

Mic98. Daniele Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. In *Proceedings of the 39th Annual Symposium on Foundations of Computer Science*, FOCS '98, page 92, USA, 1998. IEEE Computer Society. 2

MP13. Daniele Micciancio and Chris Peikert. Hardness of SIS and LWE with small parameters. In *Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I*, pages 21–39, 2013. 5, 11

MR04. Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. In *45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings*, pages 372–381, 2004. 2

MR08. Daniele Micciancio and Oded Regev. Lattice-based cryptography, 2008. 2

MV10. Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. In *Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010*, pages 1468–1480, 2010. 2, 4, 7

MV13. Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. *SIAM J. Comput.*, 42(3):1364–1391, 2013. 2

MW15. Daniele Micciancio and Michael Walter. Fast lattice point enumeration with minimal overhead. In *Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015*, pages 276–294, 2015. 2

NC16. Michael A. Nielsen and Isaac L. Chuang. *Quantum Computation and Quantum Information (10th Anniversary edition)*. Cambridge University Press, 2016. 12

NV08. Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem are practical. *J. Mathematical Cryptology*, 2(2):181–207, 2008. 2

PS09. Xavier Pujol and Damien Stehlé. Solving the shortest lattice vector problem in time $2^{2.465n}$. IACR Cryptology ePrint Archive, 2009:605, 2009. 2, 4, 7, 8

Reg04. Oded Regev. Lattices in computer science, lecture 8, Fall 2004. 2

Reg06. Oded Regev. Lattice-based cryptography. In *Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings*, pages 131–141, 2006. 2

Reg09. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. *J. ACM*, 56(6):34:1–34:40, September 2009. 2, 10, 40

Sch87. Claus Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. *Theor. Comput. Sci.*, 53:201–224, 1987. 2
SE94. Claus-Peter Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. *Math. Program.*, 66:181–199, 1994. 2

Sha84. Adi Shamir. A polynomial-time algorithm for breaking the basic merkle-hellman cryptosystem. *IEEE Trans. Information Theory*, 30(5):699–704, 1984. 2

SVP. SVP Challenges. https://www.latticechallenge.org/svp-challenge/. 2

vEB81. Peter van Emde-Boas. Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Report. Department of Mathematics. University of Amsterdam. Department of Mathematics, 1981. 2

Vlä19. Serge Vlăduț. Lattices with exponentially large kissing numbers. *Moscow Journal of Combinatorics and Number Theory*, 8(2):163–177, 2019. 8

A Reduction from CVP to DGS

The goal of this section is to improve Theorems 20 and 53 to not require a sampler for the discrete Gaussian distribution *exactly at the smoothing parameter ηε(L)*. Indeed, we usually do not know *ηε(L)* and it is a nontrivial problem to even estimate it [CDLP13]. It was stated in [ADRS15, Theorem 7.3] that the reduction still holds if we only provide a DGS oracle above the smoothing parameter. For completeness, we provide a self-contained proof in the form of Theorem 56. We first prove some technical lemmas on the discrete Gaussian distribution.

**Lemma 68.** For any lattice $\mathcal{L} \subset \mathbb{R}^n$, $s > 0$ and $r \ge s\sqrt{n}/\lambda_1(\mathcal{L})$,

$$ \rho_s(\mathcal{L} \setminus B_n(r\lambda_1(\mathcal{L}))) \le r^n \beta(\mathcal{L})^{n+o(n)} \rho_s(\mathcal{L} \setminus \{0\})^{r^2}. $$

*Proof.* Let $t = 1 + 1/n$, $R = r\lambda_1(\mathcal{L})$, $r_i = Rt^i$ and $T_i = B_n(r_{i+1}) \setminus B_n(r_i)$ for all $i \in \mathbb{N}$. Then by definition of $\beta(\mathcal{L})$,

$$ |\mathcal{L} \cap T_i| \le |\mathcal{L} \cap B_n(r_{i+1})| \le \beta(\mathcal{L})^{n+o(n)} (rt^{i+1})^n $$

It follows that

$$ \rho_s(\mathcal{L} \setminus B_n(R)) = \sum_{i=0}^{\infty} \rho_s(\mathcal{L} \cap T_i) \le \sum_{i=0}^{\infty} |\mathcal{L} \cap T_i| e^{-\pi \frac{r_i^2}{s^2}} \le \beta(\mathcal{L})^{n+o(n)} \sum_{i=0}^{\infty} \underbrace{(rt^{i+1})^n e^{-\pi \frac{R^2}{s^2} t^{2i}}}_{=f(i)} $$

where $f(i) = (rt^{i+1})^n e^{-\pi \frac{R^2}{s^2} t^{2i}}$. But check that for all $i \in \mathbb{N}$,

$$ \frac{f(i+1)}{f(i)} = t^n e^{-\pi \frac{R^2}{s^2} t^{2i} (t^2-1)} \le e^{1-2\pi \frac{R^2}{ns^2}} \le e^{1-3\pi} < 1/2 $$

where we have used that $R \ge s\sqrt{n}$, $t^2 - 1 \le \frac{3}{n}$, $t^n \le e$ and $t^{2i} \ge 1$. It follows that

$$ \rho_s(\mathcal{L} \setminus B_n(R)) \le \beta(\mathcal{L})^{n+o(n)} \cdot 2 \cdot f(0) \le \beta(\mathcal{L})^{n+o(n)} \cdot 2(rt)^n e^{-\pi \frac{R^2}{s^2}} \le r^n \beta(\mathcal{L})^{n+o(n)} \cdot e^{-\pi \frac{r^2 \lambda_1(\mathcal{L})}{s^2}} $$

On the other hand,

$$ \rho_s(\mathcal{L} \setminus \{0\}) \ge e^{-\pi \frac{\lambda_1(\mathcal{L})^2}{s^2}} $$

so the result follows immediately.

**Lemma 69.** For any $c > 1$, for any lattice $\mathcal{L} \subset \mathbb{R}^n$, $\varepsilon \in (0, 1/e)$, we have $t\eta_{\varepsilon}(\mathcal{L}) \le \eta_{\varepsilon t^2 e^{o(1)}}(\mathcal{L})$ where $t = 1 + \frac{1}{nc}$.

*Proof.* Let $s = \eta_{\varepsilon}(\mathcal{L})$, $M = n^c$ and $t = 1 + \frac{1}{M}$ with $c > 1$. Let $r = M$ and check that

$$ \frac{\sqrt{n}}{s\lambda_1(\mathcal{L}^*)} \le \sqrt{\frac{n\pi}{\ln(1/\varepsilon)}} \le r \qquad (27) $$
by Lemma 22, for large enough $n$ since $\varepsilon \le 1/e$. Let $\Gamma = (\mathcal{L}^* \setminus \{0\}) \cap B_n(r\lambda_1(\mathcal{L}^*))$, then

$$|\Gamma| \le \beta(\mathcal{L}^*)^{n+o(n)} r^n.$$

Now observe that

$$
\begin{align*}
\rho_{1/\mathrm{ts}}(\mathcal{L}^* \setminus \{0\}) &= \sum_{x \in \mathcal{L}^* \setminus \{0\}} \rho_{1/\mathrm{ts}}(x) = \sum_{x \in \mathcal{L}^* \setminus \{0\}} \rho_{1/s}(x)^{t^2} \\
&\ge \sum_{x \in \Gamma} \rho_{1/s}(x)^{t^2} \ge |\Gamma| \left( \frac{1}{|\Gamma|} \sum_{x \in \Gamma} \rho_{1/s}(x) \right)^{t^2} && \text{by Jensen's inequality} \\
&= |\Gamma|^{1-t^2} \rho_{1/s}(\Gamma)^{t^2} \\
&= |\Gamma|^{1-t^2} (\rho_{1/s}(\mathcal{L}^* \setminus \{0\}) - \rho_{1/s}(\mathcal{L}^* \setminus B_n(r\lambda_1(\mathcal{L}^*))))^{t^2} \\
&\ge (\beta(\mathcal{L}^*)^{n+o(n)} r^n)^{1-t^2} (\varepsilon - \beta(\mathcal{L}^*)^{n+o(n)} r^n \varepsilon^{r^2})^{t^2}
\end{align*}
$$

by (27), Lemma 68 and since $\rho_{1/s}(\mathcal{L}^* \setminus \{0\}) = \varepsilon$. Now observe that $t^2 - 1 \le 3/M$ and

$$(\beta(\mathcal{L}^*)^{n+o(n)} r^n)^{-3/M} = e^{-3n^{1-c}(\ln \beta(\mathcal{L}^*)+o(1)+c \ln n)} = e^{-3n^{1-c}O(\ln n)} = e^{-o(1)}$$

since $c > 1$. We also have that

$$
\begin{align*}
\beta(\mathcal{L}^*)^{n+o(n)} r^n \varepsilon^{r^2} &= e^{n \ln \beta(\mathcal{L}^*) + nc \ln(n) + o(n) - (r^2-1) \ln \frac{1}{\varepsilon}} \varepsilon \\
&\le e^{O(n \ln n) - n^{2c}} \varepsilon && \text{since } \varepsilon \le 1/e \\
&\le e^{o(1)} \varepsilon
\end{align*}
$$

for large enough $n$. It follows that

$$\rho_{1/\mathrm{ts}}(\mathcal{L}^* \setminus \{0\}) \ge e^{o(1)} (\varepsilon e^{o(1)})^{t^2} \ge \varepsilon^{t^2} e^{o(1)}$$

since $t \le 2$. Therefore we must have $\eta_{\varepsilon t^2} e^{o(1)}(\mathcal{L}) \ge ts$.

We are in a position to prove the theorem, which we restate below.

**Theorem 56.** For any $\alpha > 0$, any $e^{-n^2} \le \varepsilon \le \min(e^{-n^\alpha}, 1/200)$. There exists an algorithm that, on input $\mathcal{L}$ and with constant probability, constructs a classical and a quantum (with QRAM) $\frac{\phi(\mathcal{L})}{\lambda_1(\mathcal{L})}$-BDD oracle for $\mathcal{L}$ by doing poly(n) calls to a 0.5-hDGS$_{\eta_\varepsilon}^m$ sampler on the lattice $\mathcal{L}^*$ and requires storage space $m \cdot \text{poly}(n)$, where $m = O(\frac{n \ln(1/\varepsilon)}{\sqrt{\varepsilon}})$ and $\phi(\mathcal{L}) = \frac{\sqrt{\ln(1/\varepsilon)/\pi - o(1)}}{2\eta_\varepsilon(\mathcal{L}^*)}$. Each call to the classical oracle takes time $m \cdot \text{poly}(n)$ and space $O(\text{poly}(n) + \ln m)$ excluding the storage space of the preprocessing. Every call to the quantum oracle with QRAM takes time $\sqrt{m} \cdot \text{poly}(n)$, classical space $O(\text{poly}(n) + \ln m)$, poly(n) qubits and requires a QRAM of size $m \cdot \text{poly}(n)$ that contains the preprocessed data<fnref n="14" />.

*Proof.* First we note that we can easily identify an interval $I = [a, b]$ such that $\eta_\varepsilon(\mathcal{L}^*) \in [a, b]$ and $\frac{b}{a} \le 2^{n+o(n)}$. Indeed, by e.g. [Reg09, Lemma 2.11 and Claim 2.13] one has

$$\sqrt{\ln(1/\varepsilon)} \pi \le \lambda_1(\mathcal{L}) \eta_\varepsilon(\mathcal{L}^*) \le \sqrt{n}$$

so $\eta_\varepsilon(\mathcal{L}^*) \in \frac{1}{\lambda_1(\mathcal{L})}[c, d]$ where $\frac{d}{c} = \sqrt{\frac{n}{\ln(1/\varepsilon)}} = O(\sqrt{n})$ since $\varepsilon \le 1/200$. Furthermore, by running the LLL algorithm on $\mathcal{L}$ and taking the length of the shortest basis vector, we obtain a length $\ell$ such that $2^{-n\ell} \le \lambda_1(\mathcal{L}) \le \ell$. It follows that $\eta_\varepsilon(\mathcal{L}^*) \in [a, b] := [\frac{c}{\ell}, \frac{2^{n\ell}d}{\ell}]$ and $\frac{b}{a} = 2^{n\ell} \frac{d}{c} = 2^{n+o(n)}$.

<footnote n="14">¹⁴ Here, we are assuming that the Gaussian samples appear in the streaming fashion.</footnote>
Now let $c = 2+\alpha$, $\delta = 1+\frac{1}{nc}$ and $N = \left\lceil \frac{\ln(b/a)}{\ln \delta} \right\rceil$. Check that $N = \text{poly}(n)$ since $\frac{b}{a} = 2^{n+o(n)}$. Furthermore, if we let $s_i = a\delta^i$ for $i = 1, \dots, N$ then there must exists some $i_0$ such that

$$ \frac{1}{\delta} s_{i_0} \le \eta_{\varepsilon}(\mathcal{L}^*) \le s_{i_0}. \qquad (28) $$

The preprocessing stage of the algorithm consists in calling the hDGS$_\sigma^m$ sampler, where $\sigma(\mathcal{L}) = \eta_\varepsilon(\mathcal{L}^*)$, with parameter $s_i$ to obtain a lists $L_i$ of $m$ vectors, for each $i = 1, \dots, N$, and storing all the lists. This requires $N = \text{poly}(n)$ calls and we need to store $m \cdot \text{poly}(n)$ vectors. Note that the hDGS sampler is allowed to return less than $m$ samples if $s_i > \sigma(\mathcal{L})$: in this case, we do not care about the distribution of the vectors anyway so we can add random vectors until we get $m$ samples when that happens.

We now describe the oracle for CVP$^\phi$. On input $t \in \mathbb{R}^n$, for each $i = 1, \dots, N$, the oracle calls the algorithm of Theorem 20 on input $t$ and provides the list $L_i$ to the algorithm in place of the DGS samples. Hence, for each $i$, we either obtain a lattice vector $y_i$ or the algorithm from Theorem 20 fails and we let $y_i = 0$. Finally, the oracle returns the point closest to $t$ in the list $y_1, \dots, y_N$.

As noted in Remark 21, if we assume that all the DGS samples have $\text{poly}(n)$ bit-size then the reduction from Theorem 20 has time complexity $m \cdot \text{poly}(n)$ and space complexity $O(\text{poly}(n) + \ln m)$ excluding the storage space of the $m$ vectors provided by the DGS. Furthermore, when the basis vectors of $\mathcal{L}$ have bit-size poly($n$) (which is the case in this paper by assumption) then we can ensure that all DGS samples have $\text{poly}(n)$ bit-size by first generating more samples (say twice the amount) and throwing away all samples of norm larger than $\exp(\Omega(n^2))$. Since the vectors are sampled from a Gaussian with width at most $\exp(O(n))$ (since the basis vectors have size at most $2^{o(n)}$, the error induced by throwing away the tail of the distribution is smaller than $2^{-\Omega(n^2)}$. In the quantum setting, we use Theorem 54 instead of Theorem 20 which gives exactly the same result except for the exponent in the complexity of the oracle. Therefore running time is clear so it remains to prove that the algorithm actually solves CVP$^\phi$ on $\mathcal{L}$.

We first note that when called on $s_{i_0}$, the hDGS$_\sigma^m$ sampler will return $m$ vectors that are 0.5-close to $m$ samples from $D_{\mathcal{L},s}^m$ since $s_{i_0} \ge \sigma(\mathcal{L}) = \eta_\varepsilon(\mathcal{L}^*)$ by (28). Furthermore, by Lemma 69 we have

$$ t\eta_{\varepsilon}(\mathcal{L}^*) \le \eta_{\varepsilon t^2 e^{o(1)}}(\mathcal{L}^*) $$

where $t = 1 + \frac{1}{nc} = \delta$. It follows by (28) that

$$ \eta_{\varepsilon}(\mathcal{L}) \le s_{i_0} \le \delta\eta_{\varepsilon}(\mathcal{L}^*) \le \eta_{\varepsilon\delta^2 e^{o(1)}}(\mathcal{L}^*) $$

But the map $\varepsilon \mapsto \eta_\varepsilon(\mathcal{L})$ is continuous and decreasing, so it follows that

$$ s_{i_0} = \eta_{\varepsilon'}(\mathcal{L}^*) \quad \text{for some } \varepsilon\delta^2 e^{o(1)} \le \varepsilon' \le \varepsilon. $$

Therefore by Theorem 20 and Remark 21, with constant probability over the choice of $L_{i_0}$, the (deterministic) algorithm of Theorem 20 solves CVP$^\psi$ when given $L_{i_0}$, where

$$ \psi(\mathcal{L}) = \frac{\sqrt{\ln(1/\varepsilon')/\pi - o(1)}}{2\eta_{\varepsilon'}(\mathcal{L}^*)} $$

assuming that $m = |L_{i_0}| \ge m' := O(\frac{n \ln(1/\varepsilon')}{\sqrt{\varepsilon'}})$ which holds because

$$ \frac{n \ln(1/\varepsilon')}{\sqrt{\varepsilon'}} \le \frac{n\delta^2 \ln(1/\varepsilon) + o(n)}{\sqrt{\varepsilon\delta^2 e^{o(1)}}} \le \frac{n \ln(1/\varepsilon) + n^{1-c} \ln(1/\varepsilon) + o(n)}{\sqrt{\varepsilon\varepsilon n^{-c/2} e^{o(1)}}} = O\left(\frac{n \ln(1/\varepsilon)}{\sqrt{\varepsilon}}\right) $$

since $n^{1-c} \ln \varepsilon = n^{1-c+\alpha} = o(1)$ and $\varepsilon^{n^{-c/2}} = e^{n^{\alpha-c/2}} = e^{o(1)}$. It follows that, with constant probability over the preprocessing, our oracle solves CVP$^\psi$. Check that $\varepsilon\delta^2 e^{o(1)} \ge \varepsilon^{\delta^2+o(1)}$ since $\varepsilon < \frac{1}{e}$ and thus by Lemma 16,

$$ \eta_{\varepsilon\delta^2 e^{o(1)}}(\mathcal{L}^*) \le \eta_{\varepsilon\delta^2+o(1)}(\mathcal{L}^*) \le (\delta^2 + o(1))\eta_\varepsilon(\mathcal{L}^*) \le (1+o(1))\eta_\varepsilon(\mathcal{L}^*) $$

since $\delta = 1+o(1)$. Hence we have

$$ \psi(\mathcal{L}) \ge \frac{\sqrt{\ln(1/\varepsilon)/\pi - o(1)}}{2(1+o(1))\eta_{\varepsilon}(\mathcal{L}^*)} \equiv \phi(\mathcal{L}). $$