Abstract: We construct a total function which exhibits an exponential quantum parallel query advantage despite having no sequential query advantage. This is interesting for two reasons: (1) For total functions an exponential sequential query advantage is impossible, and was conjectured to not be possible in the parallel setting by Jeffery et al (2017)— our result refutes this conjecture. (2) The exponential speedup emerges entirely from quantum algorithms being able to utilize parallelism more effectively than classical algorithms, making this a genuinely parallel phenomenon.
Pizza and drinks will be served after the seminar in ATL 2117.