Total functions exhibit exponential quantum advantage — albeit in a parallel universe

Friday Quantum Seminar

Mahathi Vempati (QuICS)
Friday, February 23, 2024 - 12:00pm
ATL 2324

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.