Manchester Number Theory Seminar - Cedric Pilatte
| Dates: | 11 November 2025 |
|---|
| Times: | 15:00 - 16:00 |
|---|
| What is it: | Seminar |
|---|
| Organiser: | Department of Mathematics |
|---|
| Who is it for: | University staff, External researchers, Current University students |
|---|
|
Speaker: Cedric Pilatte (Oxford)
Title: Fastest quantum algorithms for factoring
Abstract: Quantum computers offer dramatic speedups for certain algorithmic tasks that are particularly relevant to cryptography. Notably, the problem of factoring n-digit integers can be solved using a quantum circuit of size polynomial in n. Until recently, the fastest known method (up to subpolynomial improvements) was Shor’s pioneering 1994 algorithm, which uses O(n^2) gates. In 2023, Regev proposed an even faster quantum algorithm for factoring integers, requiring only O(n^{3/2}) gates. Regev’s algorithm initially came with a major drawback: its correctness could not be proved unconditionally, as it relied on an ad hoc number-theoretic conjecture. We establish a version of this conjecture using tools from analytic number theory, including bounds on Dirichlet character sums and geometry of numbers. By slightly modifying Regev’s original approach, we obtain a quantum factoring algorithm requiring O(n^{3/2}) gates, whose correctness is now established unconditionally.
Room: Frank Adams 2
Travel and Contact Information
Find event
Frank Adams 2
Alan Turing Building
Manchester
