Uma Girish will present her FPO "Quantum versus Classical Communication and Query Complexity" on Thursday, May 2nd, 2024 at 11am in CS 201.

The members of her committee are as follows:

Examiners: Ran Raz (adviser), Mark Braverman and Gillat Kol 

Readers: Matt Weinberg and Huacheng Yu 

All are welcome to attend.  Please see abstract below.

Understanding the relative power of quantum versus classical computation is a fascinating and important problem in modern science on which there is likely to be much research and progress in the next few decades. While quantum algorithms are widely believed to exponentially outperform classical algorithms, there are very few settings in which this has been unconditionally proved. Communication complexity and query complexity are striking examples of such settings, where we can mathematically prove that quantum algorithms exponentially outperform classical algorithms. In this thesis we study the advantages of quantum over classical in these settings and present new and improved quantum speedups over classical. Among several results, we achieve state-of-the-art quantum speedups in communication complexity, using quantum protocols that are efficiently implementable, and using noisy quantum protocols where all qubits except for one are maximally noisy. We also study the power of entanglement and demonstrate in various ways that a slight increase in the entanglement can provide exponential savings in the communication complexity. We also study the power of adaptive queries in quantum query complexity and show that each successive round of quantum queries can yield super-exponential speedups in the number of quantum queries.