Amin Shiraz Gilani (University of Maryland) - Exponential quantum advantage in a parallel universe

Title: Exponential quantum advantage in a parallel universe
Abstract:
It is well known that the quantum and randomized sequential query complexities are polynomially related for total functions, and it was conjectured to be the case in the parallel setting as well [Jeffery, Magniez, de Wolf. 2017]. We falsify this conjecture, employing the cheat sheet framework to obtain a function with exponential parallel quantum query advantage over its randomized analogue. We then strengthen this result by constructing a total function which exhibits an exponential quantum parallel query advantage despite having no sequential query advantage. This exponential speedup emerges entirely from quantum algorithms' ability to utilize parallelism more effectively than classical algorithms.
Date of talk: 2024-03-01