Influences of Fourier Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms

Watch a conference talk from TQC 2023 (Theory of Quantum Computation, Communication and Cryptography Conference) exploring the characterization of quantum query algorithms through Fourier completely bounded polynomials. Learn about a new presentation of Arunachalam, Briët and Palazuelos' main findings, introducing a novel polynomial class and its relationship to quantum algorithms. Discover a significant conjecture about influential variables in these polynomials that, while weaker than the Aaronson-Ambainis conjecture, carries similar implications for classical simulation of quantum query algorithms. Examine proof of the AA conjecture for homogeneous Fourier completely bounded polynomials, demonstrating that d-query quantum algorithms with homogeneous polynomial outputs of degree 2d contain variables with specific influence thresholds. Explore a simplified alternative proof of Bansal, Sinha and de Wolf's findings on influential variables in block-multilinear completely bounded polynomials, featuring improved constants without relying on randomness.