How Much Can Quantum Queries Help Us Learn?

Title: How Much Can Quantum Queries Help Us Learn?
Host Faculty: Subrahmanyam Kalyanasundaram
Speaker: Nikhil Mande
Date: October 30th
Time: 11:30 noon

Abstract

In exact learning with membership queries, a learner is given a known family of Boolean functions and must identify an unknown member by querying its values on inputs of its choice. For a family of functions on a domain of size N, let D, R, and Q denote its deterministic, randomized, and quantum query complexities, respectively.

Atıcı and Servedio [Quantum Information Processing’05] conjectured that R = O(Q^2 + Q log N) for every such family. The best known general upper bounds are D = O(Q^3 log N), due to Servedio and Gortler [SICOMP’04], and R = O(Q^3 log N / log Q), due to Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf [Quantum’21]. We show that both upper bounds are tight by exhibiting families of functions attaining matching separations, thereby refuting the Atıcı-Servedio conjecture. The talk will explain these constructions, their quantum learning algorithms, and the ideas behind the classical lower bounds. No background in quantum computing will be assumed; basic familiarity with linear algebra and probability will suffice.

Based on joint work with Srinivasan Arunachalam and Amin Shiraz Gilani, arXiv link:https://arxiv.org/abs/2609.38073

Bio

Nikhil Mande is a lecturer (assistant professor) in the School of Computer Science and Informatics at the University of Liverpool since January 2023. Before that he was a postdoctoral researcher in the Algorithms and Complexity Group at CWI and Department of Computer Science at Georgetown University. His research interests are quantum computing and computational complexity theory. His webpage is here.