BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260430T031328Z
UID:Seminar-ACS-1493@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Karteek Sreenivasaiah:MAILTO:Karteek.Sreenivasaiah@liverpool.ac.uk
DTSTART:20260513T130000
DTEND:20260513T140000
SUMMARY:Algorithms and Computing Systems Series
DESCRIPTION:Nikhil Mande: Quantum Search With Generalized Wildcards\n\nIn the "search with wildcards'' problem [Ambainis, Montanaro, Quantum Inf. Comput.'14], one's goal is to learn an unknown bit-string x in {-1,1}^n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice (call this a "guess"). Ambainis and Montanaro showed a quantum algorithm of cost O(sqrt{n} log n) and a near-matching lower bound of Omega(sqrt{n}). Belovs [Comput. Comp.'15] subsequently showed a tight O(sqrt{n}) upper bound.\n\n\n\nWe consider a natural generalization of this problem, where an algorithm is restricted in the subsets it may make guesses on. We show tight bounds for various choices of subset collections, such as sets of bounded size, contiguous blocks, prefixes, and only the full set. In particular, our results recover the above-mentioned bounds.\n\n\n\nAll of these results are derived using a framework that we develop. We show, using the primal adversary bound, that the quantum query complexity of learning x is characterized, up to a constant factor, by a particular abstract analytic optimization program.\n\n\n\nI will assume no prior knowledge about quantum computing, and will spend a few minutes towards the end of the talk discussing generative AI's contribution in developing key conceptual ideas in this work.\n\n\n\nBased on joint work with Arjan Cornelissen, Subhasree Patro, Nithish Raja, and Swagato Sanyal.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1493
LOCATION:GH223
END:VEVENT
END:VCALENDAR