The Extended Euclidean Algorithm (EEA) is a fundamental building block in number theory and computer algebra. It is the standard method for computing modular inverses and the Bézout coefficients for a pair of inputs (f,g) such that f⋅u+g⋅v=gcd(f,g). The EEA is a key subroutine for many quantum algorithms, most notably to calculate modular inverses in Shor’s algorithm for discrete log and factoring and for decoding Reed Solomon codes in Decoded Quantum Interferometry (DQI). In this talk, we will talk about how to compile efficient quantum circuits for EEA in two different regimes—one where Implicit access to Bézout coefficients is sufficient and second when explicit access to Bézout coefficients is needed. I will try to structure the talk such that very little background in Quantum Computing is expected; and would encourage all students who enjoy computer science and competitive programming to attend the seminar.
