The Aaronson-Ambainis conjecture is a statement of Fourier analysis of functions defined on the Boolean cube, and it has important implications in the comparison of quantum and classical query algorithms. We will start the talk by briefly introducing classical and quantum query algorithms. Then, we will state the AA conjecture and explain why it implies that exponential quantum speedups are limited to very 'structured' computational tasks. To continue, we will state a weaker version of the AA conjecture for some kind of completely bounded polynomials. This new version of AA conjecture may be simpler to prove, and it maintains the implications in quantum computing. Finally, we will prove a particular case of this weaker conjecture.

This talk is based on Influences of Fourier Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms, published in Chicago Journal of Theoretical Computer Science.

Speaker Biography:  Francisco Escudero Gutierrez is an almost-graduated PhD student at QuSoft and CWI (Amsterdam, the Netherlands), advised by Jop Briët. Previously, Francisco completed the double bachelor's degree of math and physics and a master's program in Mathematics at University Complutense (UCM). His research interests mainly concern quantum computing and functional analysis. The concrete topics he has worked on are Grothendieck inequalities, Bohnenblust-Hille inequalities, quantum query complexity, Aaronson-Ambainis conjecture, and computational learning and testing theory.