BEGIN:VCALENDAR
PRODID:-//Columba Systems Ltd//NONSGML CPNG/SpringViewer/ICal Output/3.3-
 M3//EN
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VEVENT
DTSTAMP:20251110T210713Z
DTSTART:20251111T150000Z
DTEND:20251111T160000Z
SUMMARY:Manchester Number Theory Seminar - Cedric Pilatte
UID:{http://www.columbasystems.com/customers/uom/gpp/eventid/}osu-mfzar0i
 q-26sbm4
DESCRIPTION:Speaker: Cedric Pilatte (Oxford)\n\nTitle: Fastest quantum al
 gorithms for factoring\n\nAbstract: Quantum computers offer dramatic spe
 edups for certain algorithmic tasks that are particularly relevant to cr
 yptography. Notably\, the problem of factoring n-digit integers can be s
 olved using a quantum circuit of size polynomial in n. Until recently\, 
 the fastest known method (up to subpolynomial improvements) was Shor’s p
 ioneering 1994 algorithm\, which uses O(n^2) gates. In 2023\, Regev prop
 osed an even faster quantum algorithm for factoring integers\, requiring
  only O(n^{3/2}) gates. Regev’s algorithm initially came with a major dr
 awback: its correctness could not be proved unconditionally\, as it reli
 ed on an ad hoc number-theoretic conjecture. We establish a version of t
 his conjecture using tools from analytic number theory\, including bound
 s on Dirichlet character sums and geometry of numbers. By slightly modif
 ying Regev’s original approach\, we obtain a quantum factoring algorithm
  requiring O(n^{3/2}) gates\, whose correctness is now established uncon
 ditionally.\n\n\nRoom: Frank Adams 2
STATUS:TENTATIVE
TRANSP:TRANSPARENT
CLASS:PUBLIC
LOCATION:Frank Adams 2\, Alan Turing Building\, Manchester
END:VEVENT
END:VCALENDAR