Quantum and Classical Algorithms for Bounded Distance Decoding

2022/02/18 by Richard P. Allen, Allen, Richard, Ratip Emin Berker +5
Computer Science · #Coding theory and cryptography #Computational Complexity (cs.CC) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2203.05019

openalex publication_date 2022/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 λ₁ 2^{-Ω(√(k log q))}-BDD in polynomial time for lattices of periodicity q, finite group rank k, and shortest lattice vector length λ₁. 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.

Related

• An efficient quantum algorithm for lattice problems achieving subexponential approximation factor
• An Efficient Quantum Algorithm for a Variant of the Closest Lattice-Vector Problem
• Improved Classical and Quantum Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
• An Efficient Quantum Decoder for Prime-Power Fields
• The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction