BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum Fine-Grained Complexity - Subhasree Patro\, Utrecht Univer
 sity and QuSoft\, CWI
DTSTART:20230824T131500Z
DTEND:20230824T143000Z
UID:TALK204331@talks.cam.ac.uk
CONTACT:Subhayan Roy Moulik
DESCRIPTION:One of the major challenges in the field of complexity theory 
 is the inability to prove unconditional time lower bounds\, including for 
 practical problems within the complexity class P. One way around this is t
 he study of fine-grained complexity where we use special reductions to pro
 ve time-lower bounds for many diverse problems in P based on the conjectur
 ed hardness of some key problems. For example\, computing the edit distanc
 e between two strings\, a problem that has a practical interest in the com
 paring of DNA strings\, has an algorithm that takes O(n^2) time. Using a f
 ine-grained reduction it can be shown that faster algorithms for edit dist
 ance also imply a faster algorithm for the Boolean Satisfiability (SAT) pr
 oblem (that is believed to not exist) - strong evidence that it will be ve
 ry hard to solve the edit distance problem faster. Other than SAT\, 3SUM a
 nd APSP are other such key problems that are very suitable to use as a bas
 is for such reductions\, since they are natural to describe and well-studi
 ed. \n  \nThe situation in the quantum regime is no better\; almost all kn
 own lower bounds for quantum algorithms are defined in terms of query comp
 lexity\, which doesn’t help much for problems for which the best-known a
 lgorithms take superlinear time. Therefore\, employing fine-grained reduct
 ions in the quantum setting seems a natural way forward. However\, transla
 ting the classical fine-grained reductions directly into the quantum regim
 e is not always possible for various reasons. In this talk\, I will presen
 t some recent results in which we circumvent these challenges and prove qu
 antum time lower bounds for some problems in BQP conditioned on the conjec
 tured quantum hardness of SAT (and its variants)\, 3SUM and the APSP probl
 em.
LOCATION:MR2
END:VEVENT
END:VCALENDAR