The Quantum Decoding Problem - From Classical to Quantum Superposition

Learn about groundbreaking research in quantum cryptography through this conference talk presented at the 19th Theory of Quantum Computation, Communication and Cryptography Conference (TQC 2024). Explore the introduction and foundational analysis of the Quantum Decoding Problem (QDP), which builds upon Regev's quantum reduction from Short Integer Solution to Learning with Errors, and the recent DRT reduction in code-based cryptography. Discover how QDP, featuring errors in quantum superposition, can be solved in quantum polynomial time under certain noise conditions, surpassing the classical Shannon limit for decoding. Examine detailed mathematical proofs involving quantum measurements, q-ary unambiguous state discrimination, and pretty good measurements, while understanding the implications for finding minimal weight codewords in random codes. Delve into the limitations of the DRT reduction and its relationship with QDP through comprehensive analysis of quantum algorithms and weight distribution of random shifted dual codes using quantum Fourier analysis.