Algorithms 10

Abstract: 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: The compressed oracle technique, introduced in the context of quantum cryptanalysis, is the latest method for proving quantum query lower bounds, and has had an impressive number of applications since its introduction, due in part to the ease of importing classical lower bound intuition into the quantum setting via this method. Previously, the main quantum query lower bound methods were the polynomial method, the adversary method, and the multiplicative adversary method, and their relative powers were well understood. In this work, we situate the compressed oracle technique within this established landscape, by showing that it is a special case of the multiplicative adversary method. To accomplish this, we introduce a simplified restriction of the multiplicative adversary method, the MLADV method, that remains powerful enough to capture the polynomial method and exhibit a strong direct product theorem, but is much simpler to reason about. We show that the compressed oracle technique is also captured by the MLADV method. This might make the MLADV method a promising direction in the current quest to extend the compressed oracle technique to non-product distributions.

Abstract: Community detection is a foundational problem in data science concerned with detecting clustering structure in datasets. A natural extension is hypergraph community detection, which aims to capture higher-order correlations beyond pairwise interactions. In this work, we develop a quantum algorithm for hypergraph community detection and show that it achieves a quartic (power-of-four) speedup over the best known classical algorithm, along with superpolynomial savings in space. The speedup is based on a quantized version of the Kikuchi method and arises from the efficient preparation of a guiding state that has enhanced overlap with the solution space. To support our main result, we prove matching low-coordinate degree function lower bounds, a generalization of sum-of-squares and low-degree likelihood ratio lower bounds, which establishes that the classical baseline algorithm over which we achieve a quartic quantum speedup is (nearly) optimal. Our work constitutes a general framework for identifying when our guiding state–based approach, rooted in the Kikuchi hierarchy, can yield super-quadratic quantum speedups. We suggest that a quantity known as marginal order, which captures the presence of a tradeoff between signal-to-noise ratio and computational cost, effectively determines the existence of quantum Kikuchi-guided algorithms.