Ronald de Wolf

The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension $d$, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. $k$-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of $k$ of the input vectors. Iterating these ``sieving steps'' sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for $k=2$, but taking larger $k$ reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from $2^{0.3098 d}$ to $2^{0.2846 d}$, using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby ``center points'' to focus the search on the neighborhoods of these center points. Our algorithm uses $2^{0.1887d}$ classical bits and QCRAM bits, and $2^{o(d)}$ qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to $2^{0.1887d}$.

Abstract Graph sparsification underlies a large number of algorithms for graph cut problems and solving Laplacian systems. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. We give a quantum algorithm that outputs a classical description of an $\varepsilon$-spectral sparsifier of a weighted graph with $n$ vertices and $m$ edges. It has time complexity $\widetilde O(\sqrt{mn}/\varepsilon)$ in the adjacency array model and $\widetilde O(n^{3/2}/\varepsilon)$ in the adjacency matrix model. These bounds are tight up to polylogarithmic factors, and improve on the optimal classical complexities $\Omega(m)$ and $\Omega(n^2)$, respectively. Using classical algorithms on the obtained sparsifier yields immediate quantum speedups for approximately solving Laplacian systems and for approximating a range of graph cut problems in essentially the same complexity. As a significantly more involved application we show how to speed up the quantum query complexity for computing exactly the edge connectivity of simple graphs. We show upper bounds on the query complexity of $\widetilde O(\sqrt{mn})$ and $\widetilde O(n^{3/2})$ in the adjacency matrix and adjacency array models, respectively. The upper bound for the adjacency matrix model is tight up to logarithmic factors, while for the adjacency array model the best quantum query lower bound we know is $\Omega(n)$.