[Resource Topic] 2022/195: Quantum and Classical Algorithms for Bounded Distance Decoding

Welcome to the resource topic for 2022/195

Quantum and Classical Algorithms for Bounded Distance Decoding

Authors: Richard Allen, Ratip Emin Berker, Sílvia Casacuberta, Michael Gul


In this paper, we provide a comprehensive overview of a recent debate over the quantum versus classical solvability of bounded distance decoding (BDD). Specifically, we review the work of Eldar and Hallgren [EH22], [Hal21] demonstrating a quantum algorithm solving \lambda_1 2^{-\Omega(\sqrt{k \log q})}-BDD in polynomial time for lattices of periodicity q, finite group rank k, and shortest lattice vector length \lambda_1. Subsequently, we prove the results of [DvW21a], [DvW21b] with far greater detail and elaboration than in the original work. Namely, we show that there exists a deterministic, classical algorithm achieving the same result.

ePrint: https://eprint.iacr.org/2022/195

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .