Understanding the power and limitations of randomness and quantumness

21^st April 2023, 13:00 Ashton Lecture Theatre
Nikhil Mande

Abstract

In this talk we will try to understand whether access to randomness and quantumness gives an advantage to algorithms, in the settings of query complexity and communication complexity. The talk will consist of two parts:

In the first part of the talk, we consider query-to-communication simulation and show a surprising weakness of the quantum model as compared to the classical deterministic and randomized models.
In the second part of the talk, we consider the query complexity of algorithms, with oracle access to AND's and OR's of arbitrary subsets of the inputs, computing Boolean functions. We show that randomized algorithms give at most a polynomial advantage over their deterministic counterparts.