[GS_C_QI] Challenges in implementing quantum algorithms for breaking cryptography
ABSTRACT
The process of translating a semiformally specified quantum algorithm in a research paper into a working implementation in a programming language is often overlooked in quantum computing. Unfortunately, this process cannot be mechanical because of the mismatch between the semiformal domain and the formal target, so that the specification underdetermines the implementation in a way critical to correctness and complexity. In this talk, I will report on the challenges that I faced when implementing quantum algorithms for breaking cryptography (Shor, Beauregard, Ekera-Hastad and Gidney-Ekera). Dissolving these challenges will probably need the same rigour as compiler verification and not more fuzz testing.
