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

arXiv2304.06713MaRDI QIDQ6433013FDOQ6433013

Authors: Francisco Gutierrez 

Publication date: 13 April 2023

Abstract: We give a new presentation of the main result of Arunachalam, Bri"et and Palazuelos (SICOMP'19) and show that quantum query algorithms are characterized by a new class of polynomials which we call Fourier completely bounded polynomials. We conjecture that all such polynomials have an influential variable. This conjecture is weaker than the famous Aaronson-Ambainis (AA) conjecture (Theory of Computing'14), but has the same implications for classical simulation of quantum query algorithms. We prove a new case of the AA conjecture by showing that it holds for homogeneous Fourier completely bounded polynomials. This implies that if the output of $d$-query quantum algorithm is a homogeneous polynomial $p$ of degree $2d$, then it has a variable with influence at least $Var[p{]}^2$. In addition, we give an alternative proof of the results of Bansal, Sinha and de Wolf (CCC'22 and QIP'23) showing that block-multilinear completely bounded polynomials have influential variables. Our proof is simpler, obtains better constants and does not use randomness.

This page was built for publication: Influences of Fourier Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433013)