Fourier completely bounded polynomial influential-variable conjecture

Let p:{1,1}nRp:\{-1,1\}^n\to\mathbb{R} be a polynomial of degree at most dd. Its Fourier completely bounded dd-norm is denoted by pfcb,d\|p\|_{\operatorname{fcb},d}, and Var[p]\operatorname{Var}[p] denotes its variance. Fourier completely bounded influential-variable conjecture. If pfcb,d1\|p\|_{\operatorname{fcb},d}\leq 1, then pp has a variable with influence at least poly(Var[p],1/d)\operatorname{poly}(\operatorname{Var}[p],1/d). This is proposed as a weaker conjecture than the Aaronson–Ambainis conjecture and would also imply the folklore conjecture concerning classical simulation of quantum query algorithms on most inputs. Its status is not specified in the source.

Sources & referencesView supporting material

Primary source

Francisco Escudero Gutiérrez, “Influences of Fourier Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms”, arXiv:2304.06713 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.