$\displaystyle\quad+2{\mathbb{E}}_{t}[\left\|\nabla
h_{\xi_{t}}({\mathbf{x}}_{t-1})\right\|^{2}]{\mathbb{E}}_{t}[\left\|\nabla
f_{\theta_{t}}({\mathbf{y}}_{t})-\nabla
f_{\theta_{t}}({\mathbf{y}}_{t-1})\right\|^{2}]$ $\displaystyle\leq
2M_{f}L_{h}{\mathbb{E}}_{t}[\left\|{\mathbf{x}}_{t}-{\mathbf{x}}_{t-1}\right\|^{2}]+2M_{h}L_{f}{\mathbb{E}}_{t}[\left\|{\mathbf{y}}_{t}-{\mathbf{y}}_{t-1}\right\|^{2}]$
$\displaystyle\leq
2M_{f}L_{h}\eta_{t-1}^{2}D^{2}+2M_{h}L_{f}{\mathbb{E}}_{t}[\left\|{\mathbf{y}}_{t}-{\mathbf{y}}_{t-1}\right\|^{2}].$
(89)

We can also bound the second term of (D) using the update equation for
$y_{t+1}$ from Algorithm:

$\displaystyle{\mathbf{y}}_{t}-{\mathbf{y}}_{t-1}$
$\displaystyle=-\delta_{t}{\mathbf{y}}_{t-1}-(1-\delta_{t})h_{\xi_{t}}({\mathbf{x}}_{t-1})+h_{\xi_{t}}({\mathbf{x}}_{t})$
$\displaystyle=\delta_{t}(h({\mathbf{x}}_{t-1})-{\mathbf{y}}_{t-1})+\delta_{t}(h_{\xi_{t}}({\mathbf{x}}_{t-1})-h({\mathbf{x}}_{t-1}))+h_{\xi_{t}}({\mathbf{x}}_{t})-h_{\xi_{t}}({\mathbf{x}}_{t-1}).$
(90)

Taking norm square of (D) we get

$\displaystyle{\mathbb{E}}_{t}[\left\|{\mathbf{y}}_{t}-{\mathbf{y}}_{t-1}\right\|^{2}]$
$\displaystyle\leq
3\delta_{t}^{2}{\mathbb{E}}_{t}\left\|{\mathbf{y}}_{t-1}\\!-\\!h({\mathbf{x}}_{t-1})\right\|^{2}\\!+\\!3\delta_{t}^{2}\sigma^{2}_{h}\\!+\\!3M_{h}{\mathbb{E}}_{t}\left\|{\mathbf{x}}_{t}\\!-\\!{\mathbf{x}}_{t-1}\right\|^{2}$
$\displaystyle\leq
3\delta_{t}^{2}{\mathbb{E}}_{t}\left\|{\mathbf{y}}_{t-1}-h({\mathbf{x}}_{t-1})\right\|^{2}+3\delta_{t}^{2}\sigma^{2}_{h}+3M_{h}\eta_{t-1}^{2}D^{2}.$
(91)

Substituting (D) in (D) we get

$\displaystyle{\mathbb{E}}_{t}\big{[}\|\nabla
C_{\phi_{t}}({\mathbf{x}}_{t},{\mathbf{y}}_{t+1})-\nabla
C_{\phi_{t}}({\mathbf{x}}_{t-1},{\mathbf{y}}_{t})\|^{2}\big{]}$ (92)
$\displaystyle\leq
2M_{f}L_{h}\eta_{t-1}^{2}D^{2}+2M_{h}L_{f}\bigg{(}3\delta_{t}^{2}{\mathbb{E}}_{t}\big{[}\|{\mathbf{y}}_{t-1}-h({\mathbf{x}}_{t-1})\|^{2}\big{]}+3\delta_{t}^{2}\sigma^{2}_{h}+3M_{h}\eta_{t-1}^{2}D^{2}\bigg{)}$
$\displaystyle=2(M_{f}L_{h}+3M_{h}^{2}L_{f})\eta_{t-1}^{2}D^{2}+6M_{h}L_{f}\delta_{t}^{2}{\mathbb{E}}_{t}\big{[}\|{\mathbf{y}}_{t-1}-h({\mathbf{x}}_{t-1})\|^{2}\big{]}+6\delta_{t}^{2}M_{h}L_{f}\sigma^{2}_{h}.$
(93)

Thus using bound from (D) and (92) into (D) and taking full expectation we
obtain

$\displaystyle{\mathbb{E}}\|{{\mathbf{d}}}_{t}\\!-\\!\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})\|^{2}\\!$
$\displaystyle\leq(1\\!-\\!\rho_{t})^{2}{\mathbb{E}}\|{{\mathbf{d}}}_{t-1}\\!-\\!\tilde{\nabla}C({\mathbf{x}}_{t-1},{\mathbf{y}}_{t-1})\|^{2}$
$\displaystyle\quad+4\rho_{t}^{2}M_{f}M_{h}+4(1-\rho_{t})^{2}\big{[}(M_{f}L_{h}+3M_{h}^{2}L_{f})\eta_{t-1}^{2}D^{2}$
$\displaystyle\quad+3M_{h}L_{f}\delta_{t}^{2}{\mathbb{E}}_{t}\|{\mathbf{y}}_{t-1}-h({\mathbf{x}}_{t-1})\|^{2}+3\delta_{t}^{2}M_{h}L_{f}\sigma^{2}_{h}\big{]}.$
(94)

###  D-A Proof of Corollary 2

Starting with Lemma 3 and using the fact that
$(1-\delta_{t})^{2}\leq(1-\delta_{t})\leq 1$ and substituting
$\delta_{t}=\frac{2}{t^{p}}$ and $\eta_{t}\leq\frac{2}{(t+1)^{p}}$, we can
write

$\displaystyle{\mathbb{E}}\left\|{\mathbf{y}}_{t+1}-h({\mathbf{x}}_{t+1})\right\|^{2}\leq\left(1-\tfrac{2}{(t+1)^{p}}\right){\mathbb{E}}\left\|({\mathbf{y}}_{t}-h({\mathbf{x}}_{t}))\right\|^{2}+\tfrac{8\sigma_{h}^{2}}{(t+1)^{2p}}+\tfrac{8M_{h}D^{2}}{(t+1)^{2p}}.$
(95)

Application of Lemma 6 in (95) gives

$\displaystyle{\mathbb{E}}\left\|{\mathbf{y}}_{t}-h({\mathbf{x}}_{t})\right\|^{2}\leq\frac{a_{1}}{(t+1)^{p}},$
(96)

where
$a_{1}=\max\\{2^{p}{\mathbb{E}}\left\|{\mathbf{y}}_{1}-h({\mathbf{x}}_{1})\right\|^{2},8(\sigma_{h}^{2}+M_{h}D^{2})\\}$.
As we have initialized ${\mathbf{y}}_{1}=g_{\xi_{1}}({\mathbf{x}}_{1})$ we can
bound
${\mathbb{E}}\left\|{\mathbf{y}}_{1}-h({\mathbf{x}}_{1})\right\|^{2}={\mathbb{E}}\left\|g_{\xi_{1}}({\mathbf{x}}_{1})-h({\mathbf{x}}_{1})\right\|^{2}\leq\sigma_{h}^{2}$.
Further, using the fact that $0<p\leq 1$, we can simplify $a_{1}$ as
$a_{1}=8(\sigma_{h}^{2}+M_{h}D^{2})$. Similarly, from Lemma 9 using the fact
$(1-\rho_{t})^{2}\leq 1$, we can write

$\displaystyle{\mathbb{E}}\|{{\mathbf{d}}}_{t+1}-\tilde{\nabla}C({\mathbf{x}}_{t+1},{\mathbf{y}}_{t+1})\|^{2}$
(97)
$\displaystyle\leq(1-\rho_{t+1})^{2}{\mathbb{E}}\|{{\mathbf{d}}}_{t}-\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})\|^{2}+4\rho_{t+1}^{2}M_{f}M_{h}$
$\displaystyle\quad+4\big{[}(M_{f}L_{h}+3M_{h}^{2}L_{f})\eta_{t}^{2}D^{2}+3M_{h}L_{f}\delta_{t+1}^{2}{\mathbb{E}}_{t}\big{[}\|{\mathbf{y}}_{t}-h({\mathbf{x}}_{t})\|^{2}\big{]}+3\delta_{t+1}^{2}M_{h}L_{f}\sigma^{2}_{h}\big{]}.$
(98)

Substituting $\delta_{t}=\frac{2}{t^{p}}$, $\rho_{t}=\frac{2}{t^{p}}$ and
$\eta_{t}\leq\frac{2}{(t+1)^{p}}$, and using bound (96) we get

$\displaystyle{\mathbb{E}}\|{{\mathbf{d}}}_{t+1}-\tilde{\nabla}C({\mathbf{x}}_{t+1},{\mathbf{y}}_{t+1})\|^{2}$
(99)
$\displaystyle\leq\left(1-\frac{2}{(t+1)^{p}}\right){\mathbb{E}}\|{{\mathbf{d}}}_{t}-\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})\|^{2}$
$\displaystyle\quad+16\bigg{[}\frac{M_{f}M_{h}}{(t+1)^{2p}}+\frac{(M_{f}L_{h}+3M_{h}^{2}L_{f})D^{2}}{(t+1)^{2p}}+\left(\frac{3M_{h}L_{f}}{(t+1)^{2p}}\right)\left(\frac{a_{1}}{(t+1)^{p}}\right)+\frac{3M_{h}L_{f}\sigma^{2}_{h}}{(t+1)^{2p}}\bigg{]}.$
(100)

Using Lemma 6 and the fact that
$\tfrac{1}{(t+1)^{3p}}\leq\tfrac{1}{(t+1)^{2p}}$ gives

$\displaystyle{\mathbb{E}}\|{{\mathbf{d}}}_{t}-\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})\|^{2}\leq\frac{a_{2}}{(t+1)^{p}},$
(101)

where
$a_{2}:=\max\\{2^{p}{\mathbb{E}}\|{{\mathbf{d}}}_{1}-\tilde{\nabla}C({\mathbf{x}}_{1},{\mathbf{y}}_{1})\|^{2},16(M_{f}M_{h}+(M_{f}L_{h}+3M_{h}^{2}L_{f})D^{2}+3M_{h}L_{f}a_{1}+3M_{h}L_{f}\sigma^{2}_{h})\\}$.
As we have initialized ${{\mathbf{d}}}_{1}=\nabla
C_{\phi_{1}}({\mathbf{x}}_{1},{\mathbf{y}}_{1})$, we can bound
${\mathbb{E}}\|{{\mathbf{d}}}_{1}-\tilde{\nabla}C({\mathbf{x}}_{1},{\mathbf{y}}_{1})\|^{2}={\mathbb{E}}\|\nabla
C_{\phi_{1}}({\mathbf{x}}_{1},{\mathbf{y}}_{1})-\tilde{\nabla}C({\mathbf{x}}_{1},{\mathbf{y}}_{1})\|^{2}\leq
2M_{h}M_{f}$ (see (D)). Also as $0<p\leq 1$, we can further simplify $a_{2}$
to get
$a_{2}=16(M_{f}M_{h}+(M_{f}L_{h}+3M_{h}^{2}L_{f})D^{2}+3M_{h}L_{f}a_{1}+3M_{h}L_{f}\sigma^{2}_{h})$.

Now, introducing $\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})$ can
write

$\displaystyle{\mathbb{E}}\|\nabla
C({\mathbf{x}}_{t})-{{\mathbf{d}}}_{t}\|^{2}$
$\displaystyle={\mathbb{E}}\|\nabla
C({\mathbf{x}}_{t})-{{\mathbf{d}}}_{t}-\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})+\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})\|^{2}$
$\displaystyle\leq
2{\mathbb{E}}\|{{\mathbf{d}}}_{t}-\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})\|^{2}+2{\mathbb{E}}\|\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})-\nabla
C({\mathbf{x}}_{t})\|^{2}$
$\displaystyle=2{\mathbb{E}}\|{{\mathbf{d}}}_{t}-\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})\|^{2}+2{\mathbb{E}}\left\|\nabla
h({\mathbf{x}}_{t})^{\top}\nabla f({\mathbf{y}}_{t})-\nabla
h({\mathbf{x}}_{t})^{\top}\nabla f(h({\mathbf{x}}_{t}))\right\|^{2}$
$\displaystyle\leq
2{\mathbb{E}}\|{{\mathbf{d}}}_{t}-\tilde{\nabla}C({\mathbf{x}}_{t},{\mathbf{y}}_{t})\|^{2}+2M_{h}L_{f}{\mathbb{E}}\|{\mathbf{y}}_{t}-h({\mathbf{x}}_{t})\|^{2}$
$\displaystyle\leq\frac{2a_{2}}{(t+1)^{p}}+\frac{2M_{h}L_{f}a_{1}}{(t+1)^{p}}:=\frac{A_{1}}{(t+1)^{p}},$
(102)

here the first inequality comes from simple norm property while in the next
expression to it we simply substitute the values of gradients. In the second
inequality, we used the Assumption 2 (iii-iv) while the last inequality is
obtained using bounds from 96 and 101 and defined
$A_{1}:=32[M_{h}(M_{f}+28L_{f}\sigma_{h}^{2})+(M_{f}L_{h}+28M_{h}^{2}L_{f})D^{2}]$.

###  D-B Proof of Theorem 2

####  D-B1 Proof of Statement (i) (convex case)

Starting with the smoothness of $C$ with parameter
$L_{F}=M_{h}^{2}L_{f}+M_{f}L_{h}$ and proceeding the same way as (A-1)-(38) we
can write

$\displaystyle{\mathbb{E}}[C({\mathbf{x}}_{t+1})-C({\mathbf{x}}^{\star})]$
$\displaystyle\leq(1-\eta_{t}){\mathbb{E}}[C({\mathbf{x}}_{t})-C({\mathbf{x}}^{\star})]$
$\displaystyle\quad+\eta_{t}D\sqrt{{\mathbb{E}}\left\|\nabla
C({\mathbf{x}}_{t})-{{\mathbf{d}}}_{t}\right\|^{2}}+\frac{L_{F}\eta_{t}^{2}D^{2}}{2}.$
(103)

Setting $\eta_{t}=\frac{2}{t+1}$ and using Corollary 2 with $p=1$, we can
bound the second term of (D-B1) as

$\displaystyle\eta_{t}D\sqrt{{\mathbb{E}}\left\|\nabla
C({\mathbf{x}}_{t})-{{\mathbf{d}}}_{t}\right\|^{2}}\leq\frac{2D\sqrt{A_{1}}}{(t+1)^{3/2}}.$
(104)

Now using bound from (104) in (D-B1) we obtain

$\displaystyle{\mathbb{E}}[C({\mathbf{x}}_{t+1})-C({\mathbf{x}}^{\star})]$
$\displaystyle\leq\left(1-\frac{2}{t+1}\right){\mathbb{E}}[C({\mathbf{x}}_{t})-C({\mathbf{x}}^{\star})]+\frac{2D\sqrt{A_{1}}}{(t+1)^{\frac{3}{2}}}+\frac{2L_{F}D^{2}}{(t+1)^{2}}.$
(105)

Multiplying both side by $t(t+1)$ we can write

$\displaystyle
t(t+1){\mathbb{E}}[C({\mathbf{x}}_{t+1})-C({\mathbf{x}}^{\star})]$ (106)
$\displaystyle\leq
t(t-1){\mathbb{E}}[C({\mathbf{x}}_{t})-C({\mathbf{x}}^{\star})]+\frac{2tD\sqrt{A_{1}}}{(t+1)^{\frac{1}{2}}}+\frac{2tL_{F}D^{2}}{t+1}$
$\displaystyle\leq
t(t-1){\mathbb{E}}[C({\mathbf{x}}_{t})-C({\mathbf{x}}^{\star})]+2D\sqrt{A_{1}}(t+1)^{\frac{1}{2}}+2L_{F}D^{2},$

here in last the inequality we used the fact that $t<t+1$. Summing for
$t=1,2,\cdots,T$ and rearranging we get

$\displaystyle{\mathbb{E}}[C({\mathbf{x}}_{T+1})-C({\mathbf{x}}^{\star})]$
$\displaystyle\leq\frac{1}{T(T+1)}\left(2D\sqrt{A_{1}}\sum_{t=1}^{T}(t+1)^{\frac{1}{2}}+2L_{F}D^{2}T\right)$
$\displaystyle\leq\frac{1}{T(T+1)}\left(\frac{4}{3}D\sqrt{A_{1}}(T+1)^{\frac{3}{2}}+2L_{F}D^{2}T\right)$
$\displaystyle\leq\frac{8D\sqrt{A_{1}}}{3(T+1)^{\frac{1}{2}}}+\frac{2L_{F}D^{2}}{(T+1)},$
(107)

here in the second inequality we use the fact that
$\sum_{t=1}^{T}(t+1)^{1/2}\leq\frac{2}{3}(T+1)^{3/2}$ and the last inequality
is obtained using $(T+1)=T(1+\frac{1}{T})\leq 2T$.

####  D-B2 Proof of Statement (ii) (Non-convex case)

Again starting with the smoothness assumption of $F$ and proceeding the same
way as (A-2)-(44), we can write

$\displaystyle\sum_{t=1}^{T}\eta_{t}{\mathbb{E}}[\mathcal{G}({\mathbf{x}}_{t})]\leq
C({\mathbf{x}}_{1})-C({\mathbf{x}}^{\star})+2D\sum_{t=1}^{T}\eta_{t}{\mathbb{E}}\left\|{{\mathbf{d}}}_{t}-\nabla
C({\mathbf{x}}_{t})\right\|+\frac{L_{F}D^{2}}{2}\sum_{t=1}^{T}\eta_{t}^{2}.$
(108)

Using bound from Corollary 2 for $p=2/3$, and Jensen’s equality we can write

$\displaystyle{\mathbb{E}}\left\|{{\mathbf{d}}}_{t}-\nabla
C({\mathbf{x}}_{t})\right\|\leq\sqrt{{\mathbb{E}}\left\|{{\mathbf{d}}}_{t}-\nabla
C({\mathbf{x}}_{t})\right\|^{2}}\leq\tfrac{\sqrt{A_{1}}}{(t+1)^{\frac{1}{3}}}.$
(109)

Now, using (109), setting $\eta_{t}=\frac{2}{(T+1)^{2/3}}$ in (108) and
rearranging we can write

$\displaystyle{\mathbb{E}}[\mathcal{G}(\hat{{\mathbf{x}}})]\leq\frac{1}{T}\sum_{t=1}^{T}{\mathbb{E}}[\mathcal{G}({\mathbf{x}}_{t})]$
$\displaystyle\leq\frac{C({\mathbf{x}}_{1})-C({\mathbf{x}}^{\star})}{2T(T+1)^{-2/3}}+\sum_{t=1}^{T}\frac{2D\sqrt{A_{1}}}{T(t+1)^{1/3}}+\sum_{t=1}^{T}\frac{L_{F}D^{2}}{T(T+1)^{2/3}}$
$\displaystyle\leq\frac{C({\mathbf{x}}_{1})-C({\mathbf{x}}^{\star})}{2T(T+1)^{-2/3}}+\frac{3D\sqrt{A_{1}}}{T(T+1)^{-2/3}}+\frac{L_{F}D^{2}}{(T+1)^{2/3}}$
$\displaystyle=\frac{(T\\!+\\!1)(C({\mathbf{x}}_{1})\\!-\\!C({\mathbf{x}}^{\star}))}{2T(T+1)^{1/3}}\\!+\\!\frac{3D\sqrt{A_{1}}(T\\!+\\!1)}{T(T+1)^{1/3}}\\!+\\!\frac{L_{F}D^{2}}{(T+1)^{2/3}}$
$\displaystyle\leq\frac{C({\mathbf{x}}_{1})-C({\mathbf{x}}^{\star})}{(T+1)^{1/3}}+\frac{6D\sqrt{A_{1}}}{(T+1)^{1/3}}+\frac{L_{F}D^{2}}{(T+1)^{2/3}}$
$\displaystyle:=\mathcal{O}((T+1)^{-1/3}),$ (110)

here in the second inequality we use the fact that
$\sum_{t=1}^{T}(t+1)^{-1/3}\leq\frac{3}{2}(T+1)^{2/3}$ and the last inequality
is obtained using $(T+1)=T(1+\frac{1}{T})\leq 2T$.


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

Francisco Escudero Gutiérrez  CWI & QuSoft, Science Park 123, 1098 XG
Amsterdam, The Netherlands<EMAIL_ADDRESS>
###### Abstract.

We give a new presentation of the main result of Arunachalam, Briët 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
$\operatorname{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 research was supported by the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreement no.
945045, and by the NWO Gravitation project NETWORKS under grant no.
024.002.003.

##  1\. Introduction

Understanding the quantum query complexity of Boolean functions
$f:D\to\\{-1,1\\}$, where $D$ is a subset of $\\{-1,1\\}^{n}$, has been a
crucial task of quantum information science [Amb18]. Query complexity is a
model of computing where rigorous upper and lower bounds can be proven, which
allows one to compare the power of quantum computers with classical ones. Many
celebrated quantum algorithms show an advantage in terms of query complexity,
for example in unstructured search [Gro96], period finding [Sho99], Simon’s
problem [Sim97], NAND-tree evaluation [FGG07] and element distinctness
[Amb07]. However, these advantages are limited to be polynomial in the case of
total functions (those with $D=\\{-1,1\\}^{n}$), while they can be exponential
for highly structured problems (informally, this means that $|D|=o(2^{n})$),
such as for Simon’s problem [Sim97], period finding [Sho99] or $k$-fold
forrelation [AA15, Tal20, BS21, SSW21]. It is widely believed that a lot of
structure is necessary for superpolynomial speedups111Recently, Yamakawa and
Zhandry showed that superpolynomial speedups can be attained in unstructured
search problems. However, that does not contradict the believe that structure
is needed to achieve superpolynomial speedups in decision problems, which are
those modeled by Boolean functions [YZ22].. The following folklore conjecture,
which has circulated since the late 90s, but was first formally posed by
Aaronson and Ambainis [AA09], formalizes this idea.

######  Conjecture 1.1 (Folklore).

The output of $d$-query quantum algorithms can be simulated with error at most
$\varepsilon$ on at least a ($1-\delta$)-fraction of the inputs using
poly($d,1/\varepsilon,1/\delta$) classical queries.

In other words, it is believed that quantum query algorithms can be
approximated almost everywhere by classical query algorithms with only a
polynomial overhead.

A route towards proving Conjecture 1.1 was designed by Aaronson and Ambainis
using that the output of quantum query algorithms are polynomials222In this
work we identify the output of quantum query algorithms on an input
$x\in\\{-1,1\\}^{n}$ with the expectation of the quantum query algorithm on
$x$, namely the difference of probability of accepting and the probability of
rejecting.. Indeed, Beals et al. [BBC+01], proved that the output of a
$d$-query quantum algorithm is a bounded polynomial
$p:\\{-1,1\\}^{n}\to\mathbb{R}$ of degree at most $2d$. Here, _bounded_ means
that its supremum norm

(1) $\|p\|_{\infty}=\sup_{x\in\\{-1,1\\}^{n}}|p(x)|$

is at most 1. Based on this observation, Aaronson and Ambainis conjectured in
[AA09] that every bounded polynomial of bounded degree has an influential
variable.

######  Conjecture 1.2 (Aaronson-Ambainis (AA)).

Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$ be a polynomial of degree at most $d$ with
$\|p\|_{\infty}\leq 1$. Then, $p$ has a variable with influence at least
poly($\operatorname{Var}[p],1/d$).

The argument of [AA09, Theorem 7] to show that 1.2 would imply 1.1 works as
follows. Let $p$ the bounded polynomial of degree at most $2d$ that represents
the output of $d$ query quantum algorithm. Say that we want to approximate
$p(y)$ for some $y\in\\{-1,1\\}^{n}$. First, query an influential variable $i$
of $y$. Then, the restricted polynomial $p|_{x(i)=y(i)}$ would also be a
bounded polynomial of degree at most $2d$, so we can query again an
influential variable. Given that the influences of these variables are big,
after a _small_ number of queries the remaining polynomial would have a low
variance, so if we output its expectation it would be close to $p(y)$ with
high probability.

Despite capturing the attention of a wide range of areas, little is known
about Conjecture 1.2. In fact, it was motivated by a similar result from
analysis of Boolean functions, which proves the conjecture with inverse
exponential dependence on the degree [DFKO06]. This result was reproved from a
functional analytic perspective, highlighting its relation with the
Bohnenblust-Hille inequality [DMP19]. A couple reductions to other conjectures
have been made, such as that it is sufficient to prove the conjecture for one-
block decoupled polynomials [OZ15]. Very recently, Lovett and Zhang stated two
conjectures related to fractional certificate complexity that, if true, would
imply the AA conjecture [LZ22]. Also recently, Austrin et al. showed a
connection of the AA conjecture with cryptography: if the AA conjecture is
false, then there is a secure key agreement in the quantum random oracle model
that cannot be broken classically [ACC+22]. However, we only know it to be
true in a few particular cases: Boolean functions
$f:\\{-1,1\\}^{n}\to\\{-1,1\\}$ [Mid05, OSSS05, JZ11], symmetric polynomials
[Iva19], multilinear forms whose Fourier coefficients are all equal in
absolute value [Mon12] and block-multilinear completely bounded polynomials
[BSdW22].

The last result is relevant in this context because Arunachalam, Briët and
Palazuelos showed that quantum query algorithms output polynomials that are
not only bounded, but also completely bounded [ABP19]. This is a more
restricted normalization condition, which can be informally understood as the
polynomial taking bounded values when evaluated not only on bounded scalars,
but also on bounded matrix inputs. This way, one could try to use this extra
condition to prove results about quantum query algorithms. The main motivation
for Conjecture 1.2 was the fact that it was known to hold with exponential
dependence on the degree [DFKO06].

This idea was first put in practice by Bansal, Sinha and de Wolf [BSdW22].
They showed that the AA conjecture holds for completely bounded block-
multilinear forms, which implies an almost everywhere classical simulation
result, similar to 1.1, for the amplitudes of certain quantum query
algorithms. These algorithms query different (non-controlled) bit strings on
every query, while Conjecture 1.1 concerns algorithms that query the same
controlled bit string on every query.

###  1.1. Our results

We follow that line of work and use the characterization of [ABP19] to design
a route towards 1.1. Our first result is a new presentation of that
characterization that is more convenient for our purposes. To do this we
introduce the Fourier completely bounded $d$-norms
($\|\cdot\|_{\operatorname{fcb},d}$), which are relaxations of the supremum
norm. In these norms we not only take the supremum of the values that the
polynomial takes over Boolean strings as in Eq. 1, but also on matrix inputs
that behave like Boolean strings. We will not include formal definitions in
the introduction, but we illustrate the concept of having _Boolean behavior of
degree $d$_ with an example. For $m\in\mathbb{N}$, we denote the $m\times m$
real matrices by $M_{m}$. Say that $d=4$ and $n=6$, then if a pair of vectors
$u,v\in\mathbb{R}^{m}$ and a string of matrices $A\in(M_{m})^{6}$ have Boolean
behaviour of degree $4$, they satisfy, for instance,

$\langle u,A(1)A(1)A(2)A(3)v\rangle=\langle u,A(5)A(2)A(3)A(5)v\rangle,$

because they should simulate the relation $x(1)x(1)x(2)x(3)=x(5)x(2)x(3)x(5)$
satisfied by any Boolean string $\\{-1,1\\}^{6}$. As the reader might guess,
$(u,v,A)$ will have Boolean behavior of degree $d$ if it simulates the
relations of $\mathbb{F}_{2}^{n}$ that involve product of $d$ of the canonical
generators.

Using the Fourier expansion of polynomials defined on the Boolean hypercube we
will introduce a natural way of evaluating polynomial on matrix inputs that
have Boolean behavior, which allows us to introduce the Fourier completely
bounded $d$-norm.

######  Definition 1.3.

(Informal version of Definition 2.2) Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$ be a
polynomial of degree at most $d$. Its _Fourier completely bounded $d$-norm_ is
given by

(2) $\displaystyle\|p\|_{\operatorname{fcb},d}:=\sup|p(u,v,A)|$

where the supremum is taken over all $(u,v,A)$ that have Boolean behavior of
degree $d$.

After a reinterpretation of the semidefinite programs proposed in [GL19] to
characterize quantum query complexity, based on [ABP19], we show that the
Fourier completely bounded $d$-norms are those that characterize quantum query
algorithms.

######  Theorem 1.4.

Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$. Then, $p$ is the output of a $d$-query
quantum algorithm if and only if its degree is at most $2d$ and
$\|p\|_{\operatorname{fcb},2d}\leq 1$.

This new presentation of the main result of [ABP19] is more compact than the
original one. It is presented directly in terms of polynomials of the Boolean
hypercube, does not involve a minimization over possible completely bounded
extensions of $p$, and eludes the use of tensors.

Given that the Fourier completely bounded $d$-norms are at least the supremum
norm333From the results of [BP19] it can be inferred that there is a sequence
of polynomials $p_{n}$ of degree 3 such that
$\|p_{n}\|_{\operatorname{fcb},3}/\|p_{n}\|_{\infty}\to_{n}\infty.$, Theorem
1.4 suggests that Conjecture 1.2 may be more general than necessary. Hence, we
propose the following weaker conjecture, that would also imply Conjecture 1.1.

######  Conjecture 1.5.

Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$ be a polynomial of degree at most $d$ with
$\|p\|_{\operatorname{fcb},d}\leq 1$. Then, $p$ has a variable with influence
at least poly($\operatorname{Var}[p],1/d$).

Using a generalization through _creation_ and _annihilation_ operators of the
construction used by Varopoulos to rule out a von Neumann’s inequality for
degree 3 polynomials [Var74], we can prove a particular case of Conjecture
1.5.

######  Theorem 1.6.

Let $d\in\mathbb{N}$. Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$ be a homogeneous
polynomial of degree $d$ and with $\|p\|_{\operatorname{fcb},d}\leq 1$. Then,
the maximum influence of $p$ is at least $\operatorname{Var}[p]^{2}$.

The proof of the homogeneous case does not straightforwardly generalize (see
Remark 4.3), but it suggests a way to solve the general case (see Remark 4.4).
In particular, we propose Question 4.5 (that reminds of tensor networks and
almost-quantum correlations), which if answered affirmatively would imply 1.5.

Theorem 1.6 is the first result concerning the AA conjecture whose constant
has no dependence on the degree (to prove 1.1 we could afford a polynomial
dependence on the degree). Also, it requires considerably fewer algebraic
constraints than the other particular cases for which we know AA conjecture to
hold. In addition, thanks to Theorem 1.4, it can be interpreted directly in
terms of quantum query algorithms.

######  Corollary 1.7.

Let $d\in\mathbb{N}$. Let $\mathcal{A}$ be a $d$-query quantum algorithm whose
output is a homogeneous polynomial $p:\\{-1,1\\}^{n}\to\mathbb{R}$ of degree
$2d$. Then, the maximum influence of $p$ is at least
$\operatorname{Var}[p]^{2}$.

With a similar construction as the one we used for Theorem 1.6, we can reprove
the results of [BSdW22] regarding the influence of block-multilinear
completely bounded polynomials. These polynomials have a particular algebraic
structure and also a normalization condition when evaluated on matrix inputs
(see Section 4.1 below).

######  Theorem 1.8.

Let $d\in\mathbb{N}$. Let $p:\\{-1,1\\}^{n\times d}\to\mathbb{R}$ be a block-
multilinear degree $d$ polynomial with $\|p\|_{\operatorname{cb}}\leq 1$.
Then, $p$ has a variable of influence at least
$(\operatorname{Var}[p]/d)^{2}$. What is more, if $p$ is homogeneous of degree
$d$, then it has a variable of influence at least $\operatorname{Var}[p]^{2}$.

Theorem 1.8 corresponds to [BSdW22, Theorem 1.4], where Bansal et al. proved
the same result but with influences at least
$\operatorname{Var}[p]^{2}/[e(d+1)^{4}]$ in the general case and with
$\operatorname{Var}[p]^{2}/(d+1)^{2}$ in the homogeneous degree $d$ case.
Their proofs involve evaluating $p$ in _random infinite dimensional matrix
inputs_ , which they can control using ideas of free probability. However, our
proof evaluates $p$ in explicit finite dimensional matrix inputs, is shorter
and obtains better constants. In particular, our constant for the homogeneous
case is optimal.

###  1.2. Some notation

Given $n\in\mathbb{N}$, $[n]$ denotes the set $\\{1,\dots,n\\}$, $[n]_{0}$ the
set $\\{0,1,\dots,n\\}$, $M_{n}$ the space of $n\times n$ real matrices,
$B_{n}\subset M_{n}$ the space of $n\times n$ real matrices with operator norm
(largest singular value) at most $1$, and $S^{n-1}\subset\mathbb{R}^{n}$ the
set of vectors with euclidean norm 1. Given, $d,n\in\mathbb{N}$, we use
$\mathbf{i}$ to denote a multi-index in $[n]^{d}$.

##  2\. The Fourier completely bounded $d$-norms

There is a vast theory concerning the properties of multilinear maps
$T:\mathbb{R}^{n}\times\dots\times\mathbb{R}^{n}\to\mathbb{R}$ that are
completely bounded, i.e., bounded when they are extended to matrix domains
[Pau03]. However, to the best of our knowledge, there is no notion of being
_completely bounded_ for polynomials $p:\\{-1,1\\}^{n}\to\mathbb{R}$ defined
on the Boolean hypercube. Here, we propose a matrix notion of behaving like a
Boolean string. Then, using the Fourier expansion of these polynomials we
define the evaluation of the polynomials on these matrix inputs that behave
like Boolean strings. Finally, we introduce the Fourier completely bounded
$d$-norms and prove a few of their properties.

Every $p:\\{-1,1\\}^{n}\to\mathbb{R}$ can be written as

(3) $p(x)=\sum_{S\subset[n]}\hat{p}(S)\prod_{i\in S}x(i),$

where $\hat{p}(S)$ are the Fourier coefficients of $p$. We say that $p$ has
degree at most $d$ if $\hat{p}(S)=0$ for every $|S|>d$, where $|S|$ denotes
the cardinality of $S$.

We will be interested on simulating the behavior of bit strings
$x\in\\{-1,1\\}^{n}\times\\{1\\}$ with one extra frozen variable444The extra
variable set to $1$ is there because quantum query algorithms query a
controlled bit string, and not a non-controlled version, which would not
require that extra variable.. Given $d\in\mathbb{N}$ and
$\mathbf{i},\mathbf{j}\in[n+1]^{d}$ we say that $\mathbf{i}\sim\mathbf{j}$, if

(4) $x(i_{1})\dots x(i_{d})=x(j_{1})\dots x(j_{d})\ \mathrm{for\ every}\
x\in\\{-1,1\\}^{n}\times\\{1\\}.$

In other words, if we define

$S_{\mathbf{i}}:=\\{k\in[n]:\ k\text{ occurs an odd number of times in
}\mathbf{i}\\},$

then $\mathbf{i}\sim\mathbf{j}$ if and only if
$S_{\mathbf{i}}=S_{\mathbf{j}}$. Note that $n+1$ does not belong to these sets
$S_{\mathbf{i}}$. Given $S\subset[n]$ with $|S|\leq d$, we write
$[\mathbf{i}^{S}]$ to denote the equivalence class of indices $\mathbf{i}$
such that $S_{\mathbf{i}}=S$.

######  Definition 2.1.

Let $n,d,m\in\mathbb{N}$. Let $u,v\in S^{m-1}$ and let $A\in(B_{m})^{n}$. We
say that $(u,v,A)$ has _Boolean behavior of degree d_ if

$\langle u,A(i_{1})\dots A(i_{d})v\rangle=\langle u,A(j_{1})\dots
A(j_{d})v\rangle$

for all $\mathbf{i},\mathbf{j}\in[n+1]^{d}$ such that
$\mathbf{i}\sim\mathbf{j}$. We call $\mathscr{BB}^{d}$ to the set of $(u,v,A)$
with Boolean behavior of degree $d$.

Informally, having Boolean behavior of degree $d$ means that the relations of
Eq. 4 and some normalization conditions are satisfied. In particular, for any
bit string $x\in\\{-1,1\\}^{n}\times\\{1\\}$ and any $d\in\mathbb{N}$, we have
that $(1,1,x)$ has Boolean behavior of degree $d$.

Also note that given $d\in\mathbb{N}$, for every $S\in[n]$ with $|S|\leq d$
there is at least one $\mathbf{i}\in[n+1]^{d}$ such that $S_{\mathbf{i}}=S.$
Thus, given $(u,v,A)$ with Boolean behavior of degree $d$, for every $|S|\leq
d$ the product $\prod_{i\in S}x(i)$ can be simulated (in a unique manner) by
$\langle u,A(i_{1}^{S})\dots A(i_{d}^{S})v\rangle$. In particular, this means
that for a polynomial $p$ of degree at most $d$, we can define through Eq. 3
an evaluation of $p$ on every $(u,v,A)$ that has Boolean behavior of degree
$d$, which leads to the definition Fourier completely bouded $d$-norm.

######  Definition 2.2.

Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$ be a polynomial of degree at most $d$.
Then, its _Fourier completely bounded $d$-norm_ is defined by

$\|p\|_{\operatorname{fcb},d}=\sup_{(u,v,A)\in\mathscr{BB}^{d}}\sum_{S\subset[n],|S|\leq
d}\hat{p}(S)\langle u,A(i_{1}^{S})\dots A(i_{d}^{S})v\rangle.$

The rest of the section is devoted to prove a few results concerning the
Fourier completely bounded $d$-norms. First of all we show that, indeed, they
are norms.

######  Proposition 2.3.

Let $d\in\mathbb{N}$. Then, $\|\cdot\|_{\operatorname{fcb},d}$ is a norm in
the space of polynomials $p:\\{-1,1\\}^{n}\to\mathbb{R}$ of degree at most
$d$.

  * Proof:

It clearly satisfies the triangle inequality and is homogeneous. Also, if
$p=0$ then $\|p\|_{\operatorname{fcb},d}=0$, and vice versa, because
$\|p\|_{\infty}\leq\|p\|_{\operatorname{fcb},d}$. $\Box$

One nice property of these norms is that they can be computed as semidefinite
programs (SDPs), which are optimization problems involving linear positive
semidefinite constraints whose value can be efficiently approximated (see
[LR05] for an introduction to SDPs).

######  Proposition 2.4.

Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$ be a polynomial of degree at most $d$.
Then, its Fourier completely bounded $d$-norm can be written as the following
SDP

(5) $\displaystyle\|p\|_{\operatorname{fcb},d}=$
$\displaystyle\sup\sum_{S\in[n],|S|\leq d}\hat{p}(S)\langle
u,v_{\mathbf{i}^{S}}\rangle,$ $\displaystyle
u,v,v_{\mathbf{i}}\in\mathbb{R}^{m},\ m\in\mathbb{N},\
\mathbf{i}\in[n+1]^{s},\ s\in[d],$ (6) $\displaystyle\langle
u,v_{\mathbf{i}}\rangle=\langle u,v_{\mathbf{j}}\rangle,\ \mathrm{if}\
\mathbf{i}\sim\mathbf{j},\ \mathbf{i},\mathbf{j}\in[n+1]^{d},$ (7)
$\displaystyle\langle u,u\rangle=\langle v,v\rangle=1,$ (8)
$\displaystyle\mathrm{Gram}_{\begin{subarray}{c}\mathbf{j}\in[n+1]^{s},\\\
s\in[d-1]_{0}\end{subarray}}\\{v_{i\mathbf{j}}\\}\preccurlyeq\mathrm{Gram}_{\begin{subarray}{c}\mathbf{j}\in[n+1]^{s},\\\
s\in[d-1]_{0}\end{subarray}}\\{v_{\mathbf{j}}\\},\ \mathrm{for}\ i\in[n+1],$

where we by $v_{\mathbf{j}}$ with $\mathbf{j}\in[n+1]^{0}$ we mean $v$,
$\mathrm{Gram}$ denotes the gram matrix and the symbol ‘$\preccurlyeq$’ the
usual matrix inequality.

  * Proof:

Let
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|p\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
be the expression on the right-hand side of Eq. 5. Note that Eq. 6 represents
the relations of bit strings of Eq. 4, while Eqs. 7 and 8 encode normalization
conditions.

On the one hand, every $(u,v,A)\in\mathscr{BB}^{d}$ defines a feasible
instance for
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|p\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
through

$v_{\mathbf{i}}:=A(i_{1})\dots A(i_{s})v$

for every $\mathbf{i}\in[n+1]^{s}$ and every $s\in[d]$. Given that the value
of this instance is

$\sum_{S\subset[n],|S|\leq d}\hat{p}(S)\langle u,A(i_{1}^{S})\dots
A(i_{d}^{S})v\rangle$

we have that
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|p\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\geq\|p\|_{\operatorname{fcb},d}.$

On the other hand, let $u,v,v_{\mathbf{i}}\in\mathbb{R}^{m}$ be a feasible
instance of
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|p\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$.
For $i\in[n+1]$ define $A(i)\in M_{m}$ as the linear map from $\mathbb{R}^{m}$
to $\mathbb{R}^{m}$ that takes $v_{\mathbf{j}}$ to $v_{i\mathbf{j}}$ for every
$\mathbf{j}\in[n+1]^{s}$ and every $s\in[d-1]_{0}$, and it is extended to $0$
to the rest of $\mathbb{R}^{m}$. First of all, we should check that this is a
correct definition. In other words, we should check that for every
$\lambda\in\mathbb{R}^{M}$, with $M=(n+1)^{d-1}+\dots+(n+1)^{0}$, we have that

$\sum_{\mathbf{j}}\lambda_{\mathbf{j}}v_{\mathbf{j}}=0\ \implies\
\sum_{\mathbf{j}}\lambda_{\mathbf{j}}v_{i\mathbf{j}}=0.$

Indeed, we can prove something stronger:

$\displaystyle(\sum_{\mathbf{j}}\lambda_{\mathbf{j}}v_{i\mathbf{j}})^{T}\sum_{\mathbf{j}^{\prime}}\lambda_{\mathbf{j}^{\prime}}v_{i\mathbf{j}^{\prime}}$
$\displaystyle=\lambda^{T}\mathrm{Gram}_{\begin{subarray}{c}\mathbf{j}\in[n+1]^{s},\\\
s\in[d-1]_{0}\end{subarray}}\\{v_{i\mathbf{j}}\\}\lambda\leq\lambda^{T}\mathrm{Gram}_{\begin{subarray}{c}\mathbf{j}\in[n+1]^{s},\\\
s\in[d-1]_{0}\end{subarray}}\\{v_{\mathbf{j}}\\}\lambda$
$\displaystyle=(\sum_{\mathbf{j}}\lambda_{\mathbf{j}}v_{\mathbf{j}})^{T}\sum_{\mathbf{j}^{\prime}}\lambda_{\mathbf{j}^{\prime}}v_{\mathbf{j}^{\prime}}.$

The above calculation also proves that the $A(i)$’s are contractions, and
thanks to Eq. 6 it follows that $(u,v,A)$ has Boolean behavior of degree $d$.
Finally, note that the value of this $(u,v,A)$ for
$\|p\|_{\operatorname{fcb},d}$ is the same as the value of
$(u,v,v_{\mathbf{j}})$ for
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|p\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$,
so
$\|p\|_{\operatorname{fcb},d}\geq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|p\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}.$
$\Box$

Given $d,d^{\prime}\in\mathbb{N}$ with $d^{\prime}>d$ and a polynomial
$p:\\{-1,1\\}^{n}\to\mathbb{R}$ of degree at most $d$,
$\|p\|_{\operatorname{fcb},d}$ and $\|p\|_{\operatorname{fcb},d^{\prime}}$
have different definitions, but they are comparable. In particular, we prove
that the Fourier completely bounded $d$-norms are not increasing.

######  Proposition 2.5.

Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$ be a polynomial of degree at most $d$.
Then,

$\|p\|_{\operatorname{fcb},d+1}\leq\|p\|_{\operatorname{fcb},d}.$

######  Remark 2.6.

Proposition 2.5 is coherent with Theorem 1.4 (proved below), because allowing
more queries to quantum algorithms only increases their power. Theorem 1.4
also suggests that $\|p\|_{\operatorname{fcb},n}=\|p\|_{\infty}$ should hold,
because $n$ quantum queries should be enough to output any bounded polynomial.
If true, alongside Propositions 2.4 and 2.5, it would mean that
$(\|p\|_{\operatorname{fcb},d})_{d\in[n]}$ is a decreasing hierarchy of SDPs
that tend to $\|p\|_{\infty}$.

  * Proof of Proposition 2.5:

Let $(u,v,A)$ have Boolean behavior of degree $d+1$. Then,

$(\tilde{u},\tilde{v},\tilde{A})=(u,\frac{A(n+1)v}{\|A(n+1)v\|},A)$

has Boolean behavior of degree $d$. Also, given that $d+1>d$, we have that for
every $S\subset[n]$ with $|S|\leq d$, there exists $\mathbf{i}\in[n+1]^{d+1}$
such that $S_{\mathbf{i}}=S$ and $i_{d+1}=n+1$ and

(9) $\langle u,A(i_{1})\dots
A(i_{d+1})v\rangle=\|A(n+1)v\|\langle\tilde{u},\tilde{A}(i_{1})\dots\tilde{A}(i_{d})\tilde{v}\rangle$

This way,

$\displaystyle\|p\|_{\operatorname{fcb},d+1}$
$\displaystyle=\sup_{(u,v,A)\in\mathscr{BB}^{d+1}}\sum_{S\subset[n],|S|\leq
d}\hat{p}(S)\langle u,A(i^{S}_{1})\dots A(i^{S}_{d+1})v\rangle$
$\displaystyle=\|A(n+1)v\|\sup_{(u,v,A)\in\mathscr{BB}^{d+1}\
}\sum_{S\subset[n],|S|\leq
d}\hat{p}(S)\langle\tilde{u},\tilde{A}(i^{S}_{1})\dots\tilde{A}(i^{S}_{d})\tilde{v}\rangle$
$\displaystyle\leq\sup_{(\tilde{u},\tilde{v},\tilde{A}(i))\in\mathscr{BB}^{d}\
}\sum_{S\subset[n],|S|\leq
d}\hat{p}(S)\langle\tilde{u},\tilde{A}(i^{S}_{1})\dots\tilde{A}(i^{S}_{d})\tilde{v}\rangle$
$\displaystyle=\|p\|_{\operatorname{fcb},d},$

where in the equality we have used Eq. 9, and in the inequality that
$(\tilde{u},\tilde{v},\tilde{A})$ has Boolean behavior of degree $d$ and
$\|A(n+1)v\|\leq 1$. $\Box$

The next proposition states that $\|\cdot\|_{\operatorname{fcb},d}$ does not
increase after restrictions, which is a relevant feature to ensure that
Conjecture 1.5 implies Conjecture 1.1. Given a polynomial
$p:\\{-1,1\\}^{n}\to\mathbb{R}$ and $i\in[n]$, the _restriction of $p$ to the
$i$-th variable being set to $y\in\\{-1,1\\}$_ is the polynomial
$q:\\{-1,1\\}^{n-1}\to\mathbb{R}$ (whose variables we index with
$x(1),\dots,x(i-1),x(i+1),\dots,x(n)$ for convenience) defined by
$q(x):=p(x(1),\dots,x(i-1),y,x(i+1),\dots,x(n))$.

######  Proposition 2.7.

Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$ be a polynomial of degree at most $d$ and
let $i\in[n]$. Let $q:\\{-1,1\\}^{n-1}\to\mathbb{R}$ be the restriction of $p$
to the $i$-th variable being set to $y\in\\{-1,1\\}$. Then,

$\|q\|_{\operatorname{fcb},d}\leq\|p\|_{\operatorname{fcb},d}.$

  * Proof:

Let $(u,v,A(1),\dots,A(i-1),A(i+1),\dots A(n+1))$ with Boolean behavior of
degree $d$. Define $\tilde{u}:=u$, $\tilde{v}:=v$ and $\tilde{A}(j)$ for
$j\in[n+1]$ as

$\tilde{A}(j)=\left\\{\begin{array}[]{ll}A(j)&\mathrm{if\ }j\neq i,\\\
yA(n+1)&\mathrm{if\ }j=i.\end{array}\right.$

Then, $(\tilde{u},\tilde{v},\tilde{A}(1),\dots,\tilde{A}(n+1))$ has Boolean
behavior of degree $d$. Now note that for every $S\subset[n+1]-\\{i\\}$, we
have that

(10) $\hat{q}(S)=\hat{p}(S)+y\hat{p}(S\cup\\{i\\}).$

Also, for every $S\subset[n+1]-\\{i\\}$ with $|S|\leq d-1$, it is satisfied
that

(11)
$\langle\tilde{u},\tilde{A}(j^{S}_{1})\dots\tilde{A}(j^{S}_{d})\tilde{v}\rangle=y\langle\tilde{u},\tilde{A}(j^{S\cup\\{i\\}}_{1})\dots\tilde{A}(j^{S\cup\\{i\\}}_{d})\tilde{v}\rangle.$

Thus,

$\displaystyle\|q\|_{\operatorname{fcb},d}$
$\displaystyle=\sup_{\begin{subarray}{c}(u,v,A(j))\in\mathscr{BB}^{d}\\\
j\in[n+1]-\\{i\\}\end{subarray}}$
$\displaystyle\sum_{S\subset[n+1]-\\{i\\},|S|\leq d}\hat{q}(S)\langle
u,A(j^{S}_{1})\dots A(j^{S}_{d})v\rangle$
$\displaystyle=\sup_{\begin{subarray}{c}(u,v,A(j))\in\mathscr{BB}^{d}\\\
j\in[n+1]-\\{i\\}\end{subarray}}$
$\displaystyle\sum_{S\subset[n+1]-\\{i\\},|S|\leq d}\hat{p}(S)\langle
u,A(j^{S}_{1})\dots A(j^{S}_{d})v\rangle$ $\displaystyle+$
$\displaystyle\sum_{S\subset[n+1]-\\{i\\},|S|\leq
d-1}y\hat{p}(S\cup\\{i\\})\langle u,A(j^{S}_{1})\dots A(j^{S}_{d})v\rangle$
$\displaystyle\leq\sup_{\begin{subarray}{c}(\tilde{u},\tilde{v},\tilde{A}(j))\in\mathscr{BB}^{d}\\\
j\in[n+1]\end{subarray}}$ $\displaystyle\sum_{S\subset[n+1]-\\{i\\},|S|\leq
d}\hat{p}(S)\langle\tilde{u},\tilde{A}(j^{S}_{1})\dots\tilde{A}(j^{S}_{d})\tilde{v}\rangle$
$\displaystyle+$ $\displaystyle\sum_{S\subset[n+1]-\\{i\\},|S|\leq
d-1}\hat{p}(S\cup\\{i\\})\langle\tilde{u},\tilde{A}(j^{S\cup\\{i\\}}_{1})\dots\tilde{A}(j^{S\cup\\{i\\}}_{d})\tilde{v}\rangle$
$\displaystyle=\sup_{\begin{subarray}{c}(\tilde{u},\tilde{v},\tilde{A}(j))\in\mathscr{BB}^{d}\\\
j\in[n+1]\end{subarray}}$ $\displaystyle\sum_{S\subset[n],|S|\leq
d}\hat{p}(S)\langle\tilde{u},\tilde{A}(j^{S}_{1})\dots\tilde{A}(j^{S}_{d})\tilde{v}\rangle$
$\displaystyle=\|p\|_{\operatorname{fcb},d},$

where in the second equality we have used Eq. 10 and in the first inequality
Eq. 11. $\Box$

##  3\. Quantum query algorithms are Fourier completely bounded polynomials

Now we are ready to prove Theorem 1.4, that fully characterizes quantum query
algorithms in terms of the Fourier completely bounded $d$-norms.

See 1.4

To prove Theorem 1.4 we just have to reinterpret the semidefinite programs of
[GL19], based on [ABP19].

######  Theorem 3.1 (Gribling-Laurent).

Let $p:\\{-1,1\\}^{n}\to\mathbb{R}$. Then, $p$ is the output of $d$-query
quantum algorithm if and only if its degree is at most $2d$ and the value of
the following semidefinite program is at most 0,

(12) $\displaystyle\max$ $\displaystyle\
-w+\sum_{x\in\\{-1,1\\}^{n}}\frac{p(x)\phi(x)}{2^{n}}$
$\displaystyle\mathrm{s.t.}$ $\displaystyle\ w\geq 0,\ m\in\mathbb{N},\
A_{s}\in(B_{m})^{n+1},\ u,v\in\mathbb{R}^{m},\ s\in[2d],$ $\displaystyle\
\|\phi\|_{1}=1,\ \|u\|^{2}=\|v\|^{2}=w,$ $\displaystyle\
\hat{\phi}(S_{\mathbf{i}})=\langle u,A_{1}(i_{1})\dots
A_{2d}(i_{2d})v\rangle,\ \mathbf{i}\in[n+1]^{2d},$

where $\|\phi\|_{1}=\sum_{x\in\\{-1,1\\}^{n}}\frac{|\phi(x)|}{2^{n}}$.

######  Remark 3.2.

Theorem 3.1 corresponds to [GL19, Equation (24)]. There, the authors not only
ask for the $A_{s}(i)$ to be contractions, but also unitaries. However, that
extra restriction does not change the value of the semidefinite program
because we can always block-encode a contraction in the top left corner of an
unitary (see for instance [AAI+16, Lemma 7]). We also want to remark that
$A_{s}(i)$ can be taken to be equal to $A_{s^{\prime}}(i)$ for every
$s,s^{\prime}\in[2d]$ and every $i\in[n+1]$, as this extra restriction does
not change value of the semidefinite program. Indeed, let $(u,v,A_{s},w,\phi)$
be part of feasible instance of Eq. 12. Define now

$\displaystyle\tilde{u}$ $\displaystyle:=u\otimes e_{1},$
$\displaystyle\tilde{v}$ $\displaystyle:=v\otimes e_{2d+1},$ $\displaystyle
A(i)$ $\displaystyle:=\sum_{s\in[2d]}A_{s}(i)\otimes e_{s}e_{s}^{T},$

where $\\{e_{s}\\}_{s\in[2d+1]}$ is an orthonormal basis of
$\mathbb{R}^{2d+1}$. Then,

$\langle u,A_{1}(i_{1})\dots
A_{d}(i_{2d})v\rangle=\langle\tilde{u},\tilde{A}(i_{1})\dots\tilde{A}(i_{2d})\tilde{v}\rangle,$

for every $\mathbf{i}\in[n+1]^{2d}$. Hence,
$(\tilde{u},\tilde{v},\tilde{A},w,\phi)$ is a feasible instance for Eq. 12
that attains the same value as $(u,v,A_{s},w,\phi)$.

  * Proof of 1.4:

Thanks to Theorem 3.1 and Remark 3.2, we know that $p$ is the output of
$d$-query quantum algorithm if and only if its degree is at most $2d$ and the
following constraint is satisfied

(13) $\displaystyle\ \sum_{x\in\\{-1,1\\}^{n}}\frac{p(x)\phi(x)}{2^{n}}\leq w$
$\displaystyle\mathrm{s.t.}$ $\displaystyle\ w\geq 0,\ m\in\mathbb{N},\
A\in(B_{m})^{n+1},\ u,v\in\mathbb{R}^{m},$ (14) $\displaystyle\
\|\phi\|_{1}=1,$ $\displaystyle\ \|u\|^{2}=\|v\|^{2}=w,$ $\displaystyle\
\hat{\phi}(S_{\mathbf{i}})=\langle u,A(i_{1})\dots A(i_{2d})v\rangle,\
\mathbf{i}\in[n+1]^{2d}.$

Now, note that if $(u,v,A,\phi,w)$ satisfies all conditions of Eq. 13 except
for Eq. 14, then $(u/\sqrt{\|\phi\|_{1}},$
$v/\sqrt{\|\phi\|_{1}},A,\phi/\|\phi\|_{1},w/\|\phi\|_{1})$ would be a
feasible instance. Furthermore, given that

$\sum_{x\in\\{-1,1\\}^{n}}\frac{p(x)\phi(x)}{2^{n}}\leq
w\iff\frac{1}{\|\phi\|_{1}}\sum_{x\in\\{-1,1\\}^{n}}\frac{p(x)\phi(x)}{2^{n}}\leq\frac{w}{\|\phi\|_{1}},$

we can write Eq. 13 forgetting about the normalization condition of Eq. 14. In
other words, Eq. 13 is equivalent to

(15) $\displaystyle\ \sum_{x\in\\{-1,1\\}^{n}}\frac{p(x)\phi(x)}{2^{n}}\leq w$
$\displaystyle\mathrm{s.t.}$ $\displaystyle\ w\geq 0,\ m\in\mathbb{N},\
A\in(B_{m})^{n+1},\ u,v\in\mathbb{R}^{m},$ (16) $\displaystyle\
\|u\|^{2}=\|v\|^{2}=w,$ $\displaystyle\ \hat{\phi}(S_{\mathbf{i}})=\langle
u,A(i_{1})\dots A(i_{2d})v\rangle,\ \mathbf{i}\in[n+1]^{2d}.$

In addition, by homogeneity we can assume $w=1$. Also note, that if $(u,v,A)$
are part of a feasible instance of Eq. 15, then it automatically has Boolean
behaviour of degree $2d$, and any $(u,v,A)$ defines a feasible instance for
Eq. 15. Finally, by Parseval’s identity we can rewrite
$\sum_{x\in\\{-1,1\\}^{n}}\frac{p(x)\phi(x)}{2^{n}}$ as
$\sum_{S\subset[n]}\hat{p}(S)\hat{\phi}(S)$. Putting altogether we get that
$p$ is the output of $d$-query quantum algorithm if and only if its degree is
at most $2d$ and

$\displaystyle\ \sum_{S\subset[n],|S|\leq 2d}\hat{p}(S)\langle
u,A(i^{S}_{1})\dots A(i^{S}_{2d})v\rangle\leq 1$ $\displaystyle\mathrm{s.t.}\
$ $\displaystyle(u,v,A)\ \mathrm{has\ Boolean\ behavior\ of\ degree\ }2d,$

which is the same as saying that $\|p\|_{\operatorname{fcb},2d}\leq 1$. $\Box$

##  4\. Aaronson and Ambainis conjecture for (Fourier) completely bounded
polynomials

In this section we prove Theorem 1.6 and Theorem 1.8. Both are based on the
construction used by Varopoulos to disprove a degree 3 von Neumann’s
inequality [Var74]. First of all, we recall the expressions of variance and
influences of a polynomial $p:\\{-1,1\\}^{n}\to\mathbb{R}$. The variance is
given by

$\operatorname{Var}[p]=\sum_{|S|\geq 1}\hat{p}^{2}(S),$

and the influence of the $i$-th variable by

$\mathrm{Inf}_{i}[p]=\sum_{S\ni i}\hat{p}^{2}(S).$

The maximum influence of $p$ is
$\text{MaxInf}[p]:=\max_{i\in[n]}\mathrm{Inf}_{i}[p].$ One may interpret
$\operatorname{Var}[p]$ as the total change of $p$ and $\mathrm{Inf}_{i}[p]$
as the change of $p$ that is due to varying the $i$-th variable.

###  4.1. AA conjecture for block-multilinear completely bounded polynomials

Before proving Theorem 1.8, we shall specify what is a block-multilinear
completely bounded polynomial. A _block-multilinear polynomial_ of degree $d$
is a polynomial $p:\\{-1,1\\}^{n\times d}\to\mathbb{R}$ such that if we divide
the variables $x\in\\{-1,1\\}^{n\times d}$ in $d$ blocks of $n$ coordinates
each, then the every of the monomials of $p$ has at most one coordinate of
each of the blocks. In other words, the block-multilinear polynomials of
degree $d$ are those that can be written as

(17)
$p(x_{1},\dots,x_{d})=\hat{p}(\emptyset)+\sum_{s\in[d]}\sum_{\begin{subarray}{c}\mathbf{b}\in[d]^{s}\\\
b_{1}<\dots<b_{s}\end{subarray}}\sum_{\mathbf{i}\in[n]^{s}}\hat{p}(\\{(b_{1},i_{1}),\dots,(b_{s},i_{s})\\})x_{b_{1}}(i_{1})\dots
x_{b_{s}}(i_{s}),$

for every $(x_{1},\dots,x_{d})\in(\\{-1,1\\}^{n})^{d}.$ For this kind of
polynomials, there is a very natural way of evaluating them in matrix inputs,

(18) $p(A_{1},\dots,A_{d})=\hat{p}(\emptyset)\mathop{\rm
Id}\nolimits_{m}+\sum_{s\in[d]}\sum_{\begin{subarray}{c}\mathbf{b}\in[d]^{s}\\\
b_{1}<\dots<b_{s}\end{subarray}}\sum_{\mathbf{i}\in[n]^{s}}\hat{p}(\\{(b_{1},i_{1}),\dots,(b_{s},i_{s})\\})A_{b_{1}}(i_{1})\dots
A_{b_{s}}(i_{s}),$

for every $A_{s}\in(M_{m})^{n}$, $s\in[d]$ and $m\in\mathbb{N}$. The
_completely bounded norm_ of a block-multilinear polynomial is defined as

(19) $\|p\|_{\operatorname{cb}}:=\sup\\{\|p(A_{1},\dots,A_{d})\|:\
m\in\mathbb{N},\ A_{s}\in(B_{m})^{n},\ s\in[d]\\}.$

Concerning these polynomials, we can show the following.

See 1.8

######  Remark 4.1.

With our proof of the homogeneous case of Theorem 1.8 we can show that for the
case of $p:\\{-1,1\\}^{n\times d}\to\mathbb{R}$ being a homogeneous degree $d$
block-multinear polynomial we have the following non-commutative root
influence inequality

(20)
$\|p\|_{\operatorname{cb}}\geq\sum_{i\in[n]}\sqrt{\mathrm{Inf}_{s,i}[p]},$

for any $s\in[d]$. This improves [BSdW22, Theorem 1.4] in two ways. First, we
can allow $s$ to be any number in $[d]$, while they only prove the result of
$s\in\\{1,d\\}$. Second, they prove a weaker statement that depends on $d$,
namely,

$\|p\|_{\operatorname{cb}}\geq\sum_{i\in[n]}\frac{\sqrt{\mathrm{Inf}_{s,i}[p]}}{\sqrt{e(d+1)}},$

for $s\in\\{1,d\\}$.

######  Remark 4.2.

Given that $p(x_{1},\dots,x_{d})=x_{1}(1)\dots x_{d}(1)$ is a homogeneous
degree $d$ block-multilinear completely bounded polynomial with
$\operatorname{Var}[p]^{2}=\mathrm{MaxInf}[p]=1$, we have that the homogeneous
case of Theorem 1.8 is optimal.

  * Proof of the homogeneous degree $d$ case of Theorem 1.8:

Let $p$ be a homogeneous degree $d$ block-multilinear polynomial. Let
$s\in[d]$. We label the coordinates by $(r,i)$, where $r\in[d]$ indicates the
block, and $i\in[n]$. Our goal is defining $A\in(B_{m})^{n}$ and
$f_{\emptyset},e_{\emptyset}\in S^{m-1}$ such that

(21) $\langle f_{\emptyset},A(i_{1})\dots
A(i_{d})e_{\emptyset}\rangle=\frac{\hat{p}(\\{(1,i_{1}),\dots,(d,i_{d})\\})}{\sqrt{\mathrm{Inf}_{s,i_{s}}[p]}}.$

Once we are there, we can prove the announced root-influence inequality Eq.
20. Indeed,

$\displaystyle\|p\|_{\operatorname{cb}}$
$\displaystyle\geq\sum_{i_{1},\dots,i_{d}\in[n]}\hat{p}(\\{(1,i_{1}),\dots,(d,i_{d})\\})\langle
f_{\emptyset},A(i_{1})\dots A(i_{d})e_{\emptyset}\rangle$
$\displaystyle=\sum_{i_{1},\dots,i_{d}\in[n]}\hat{p}(\\{(1,i_{1}),\dots,(d,i_{d})\\})\frac{\hat{p}((1,i_{1}),\dots,(d,i_{d}))}{\sqrt{\mathrm{Inf}_{s,i_{s}}[p]}}$
$\displaystyle=\sum_{i\in[n]}\sqrt{\mathrm{Inf}_{s,i}[p]}.$

Finally, the statement about the maximal influence quickly follows from the
root-influence inequality

$\displaystyle\|p\|_{\operatorname{cb}}\geq\sum_{i\in[n]}\sqrt{\mathrm{Inf}_{s,i}[p]}\geq\sum_{i\in[n]}\frac{\mathrm{Inf}_{s,i}[p]}{\sqrt{\mathrm{MaxInf}[p]}}=\frac{\operatorname{Var}[p]}{\sqrt{\mathrm{MaxInf}[p]}},$

which after rearranging yields

$\mathrm{MaxInf}[p]\geq\left(\frac{\operatorname{Var}[p]}{\|p\|_{\operatorname{cb}}}\right)^{2}.$

Hence, it suffices to design $(f_{\emptyset},e_{\emptyset},A)\in S^{m-1}\times
S^{m-1}\times(B_{m})^{n}$ satisfying Eq. 21. Let
$\mathcal{S}:=\\{\\{(r,i_{r}),\dots,(d,i_{d})\\}:i_{r},\dots,i_{d}\in[n],\
s+1\leq r\leq d\\}$ and
$\mathcal{S}^{\prime}:=\\{\\{(1,i_{1}),\dots,(r,i_{r})\\}:i_{1},\dots,i_{r}\in[n],\
r\leq s-1\\}$. Let $m:=2+|\mathcal{S}|+|\mathcal{S}^{\prime}|$. Let
$\\{e_{\emptyset},e_{S},f_{\emptyset},f_{S^{\prime}}:\ S\in\mathcal{S},\
S^{\prime}\in\mathcal{S}^{\prime}\\}$ be an orthonormal basis of
$\mathbb{R}^{m}$, and define $A(i)\in M_{m}$ by

$\displaystyle A(i)e_{S}$ $\displaystyle:=e_{S\cup\\{(d-|S|,i)\\}},\
\mathrm{for}\ 0\leq|S|\leq d-s-1,\ S\in\mathcal{S},$ $\displaystyle A(i)e_{S}$
$\displaystyle:=\sum_{\begin{subarray}{c}S^{\prime}\in\mathcal{S^{\prime}}\\\
|S^{\prime}|=s-1\end{subarray}}\frac{\hat{p}(S^{\prime}\cup
S\cup\\{(s,i)\\})}{\sqrt{\mathrm{Inf}_{s,i}(p)}}f_{S^{\prime}},\ \mathrm{for}\
|S|=d-s,\ S\in\mathcal{S},$ $\displaystyle A(i)f_{S^{\prime}}$
$\displaystyle:=\delta_{(|S^{\prime}|,i)\in\mathcal{S}^{\prime}}f_{S^{\prime}-\\{(|S^{\prime}|,i)\\}},\
S^{\prime}\in\mathcal{S}^{\prime}.$

One can check that $(f_{\emptyset},e_{\emptyset},A(i))$ satisfies Eq. 21. This
is because the first applications of the $A(i)$’s act like a _creation_
operator and the last as _annihilation_ operators. The first $d-s$
applications of the $A(i)$’s create a _superposition_ over some vectors with
the coefficients that we are interested in (those Fourier coefficients that
involve the $d-s+1$ first applications of $A(i)$). The last $s-1$ applications
of $A(i)$ act like annihilation operators that lead us to the desired
coefficient.

Finally, we claim that $A(i)$ are contractions. Given that $\\{e_{S}:\
0\leq|S|\leq d-s-1,\ S\in\mathcal{S}\\}$, $\\{e_{S}:\ |S|=d-s,\
S\in\mathcal{S}\\}$ and $\\{f_{S^{\prime}}:\
S^{\prime}\in\mathcal{S}^{\prime}\\}$ are mapped to orthogonal spaces, we just
have to check than when $A(i)$ is a contraction when is restricted to the span
of each of these 3 sets. For the first and third sets of vectors that is
clear. For the second is true because for any $\lambda\in[n]^{d-s}$

$\displaystyle\|A(i)\sum_{\begin{subarray}{c}S\in\mathcal{S}\\\
|S|=d-s\end{subarray}}\lambda_{S}e_{S}\|$
$\displaystyle=\|\sum_{\begin{subarray}{c}S\in\mathcal{S}\\\
|S|=d-s\end{subarray}}\sum_{\begin{subarray}{c}S^{\prime}\in\mathcal{S}^{\prime}\\\
|S^{\prime}|=s-1\end{subarray}}\frac{\hat{p}(S^{\prime}\cup
S\cup\\{(s,i)\\})}{\sqrt{\mathrm{Inf}_{s,i}[p]}}\lambda_{S}f_{S^{\prime}}\|$
$\displaystyle=\sqrt{\frac{\sum_{\begin{subarray}{c}S^{\prime}\in\mathcal{S}^{\prime}\\\
|S^{\prime}|=s-1\end{subarray}}\left(\sum_{\begin{subarray}{c}S\in\mathcal{S}\\\
|S|=d-s\end{subarray}}\hat{p}(S^{\prime}\cup
S\cup\\{(s,i)\\})\lambda_{S}\right)^{2}}{\mathrm{Inf}_{s,i}[p]}}$
$\displaystyle\leq\sqrt{\frac{\sum_{\begin{subarray}{c}S^{\prime}\in\mathcal{S}^{\prime}\\\
|S^{\prime}|=s-1\end{subarray}}\left(\sum_{\begin{subarray}{c}S\in\mathcal{S}\\\
|S|=d-s\end{subarray}}\hat{p}(S^{\prime}\cup
S\cup\\{(s,i)\\})^{2}\right)\left(\sum_{\begin{subarray}{c}S\in\mathcal{S}\\\
|S|=d-s\end{subarray}}\lambda_{S}^{2}\right)}{\mathrm{Inf}_{s,i}[p]}}$
$\displaystyle=\sqrt{\frac{\mathrm{Inf}_{s,i}[p]}{\mathrm{Inf}_{s,i}[p]}}\sqrt{\sum_{\begin{subarray}{c}S\in\mathcal{S}\\\
|S|=d-s\end{subarray}}\lambda_{S}^{2}}$
$\displaystyle=\|\sum_{\begin{subarray}{c}S\in\mathcal{S}\\\
|S|=d-s\end{subarray}}\lambda_{S}e_{S}\|,$

where in the inequality we have used Cauchy-Schwarz. $\Box$

  * Proof of the general case of Theorem 1.8:

Let $p:\\{-1,1\\}^{n\times d}\to\mathbb{R}$ be a block-multilinear degree $d$
polynomial. For every $s\in[d]$, let $p_{=s}$ be its degree $s$ part. Let
$D\in[d]$ be such that
$\operatorname{Var}[p_{=D}]\geq\operatorname{Var}[p]/d,$ which exists because
$\operatorname{Var}[p]=\sum_{s\in[d]}\operatorname{Var}[p_{=s}]$. We will now
divide the proof in two parts. One is showing that

(22) $\|p_{=D}\|_{\operatorname{cb}}\leq\|p\|_{\operatorname{cb}},$

and the other is proving that

(23)
$\mathrm{MaxInf}(p_{=D})\geq\left(\frac{\operatorname{Var}[p_{=D}]}{\|p_{=D}\|_{\operatorname{cb}}}\right)^{2}.$

Once we had done that, the result will easily follow:

$\displaystyle\mathrm{MaxInf}(p)$
$\displaystyle\geq\mathrm{MaxInf}(p_{=D})\geq\left(\frac{\operatorname{Var}[p_{=D}]}{\|p_{=D}\|_{\operatorname{cb}}}\right)^{2}\geq\left(\frac{\operatorname{Var}[p]}{d\|p\|_{\operatorname{cb}}}\right)^{2},$

where in the second inequality we have used Eq. 23, and in the third we have
used Eq. 22 and that $\operatorname{Var}[p_{=D}]\geq\operatorname{Var}[p]/d$.

First, we prove Eq. 22. Let $B\in B_{d+1}$ be defined by
$B:=\sum_{s\in[D]}e_{s}e_{s+1}^{T},$ where $\\{e_{s}\\}_{s\in[D+1]}$ is an
orthonormal basis of $\mathbb{R}^{D+1}$. Note that $\langle
e_{1},B^{s}e_{D+1}\rangle=\delta_{s,D}$ for all $s\in[d]_{0}$. Hence,

$\displaystyle\|p_{=D}\|_{\operatorname{cb}}$
$\displaystyle=\sup_{\begin{subarray}{c}u,v\in S^{m-1},\ A\in(B_{m})^{n}\\\
m\in\mathbb{N}\end{subarray}}\sum_{\begin{subarray}{c}\mathbf{b}\in[d]^{D}\\\
b_{1}<\dots<b_{D}\end{subarray}}\sum_{\mathbf{i}\in[n]^{D}}$
$\displaystyle\hat{p}_{=D}(\\{(b_{1},i_{1}),\dots,(b_{D},i_{D})\\})\langle
u,A_{b_{1}}(i_{1})\dots A_{b_{D}}(i_{D})v\rangle$
$\displaystyle=\sup_{\begin{subarray}{c}u,v\in S^{m-1},\ A\in(B_{m})^{n}\\\
m\in\mathbb{N}\end{subarray}}\sum_{s\in[d]}\sum_{\begin{subarray}{c}\mathbf{b}\in[d]^{s}\\\
b_{1}<\dots<b_{s}\end{subarray}}\sum_{\mathbf{i}\in[n]^{s}}$
$\displaystyle\hat{p}(\\{(b_{1},i_{1}),\dots,(b_{s},i_{s})\\})$
$\displaystyle\cdot\langle u\otimes e_{1},[A_{b_{1}}(i_{1})\otimes
B]\dots[A_{b_{s}}(i_{s})\otimes B]v\otimes e_{D+1}\rangle$
$\displaystyle\leq\|p\|_{\operatorname{cb}}.$

Second, we prove Eq. 23. Let
$\mathcal{S}:=\\{\\{(b_{1},i_{1}),\dots,(b_{D-1},i_{D-1})\\}:\ b_{s}\in[d],\
b_{1}<\dots<b_{D-1},\ i_{s}\in[n],\ s\in[D-1]\\}.$ Let $m:=2+|S|$. Let
$\\{v,f_{\emptyset},f_{S}:S\in\mathcal{S}\\}$ be an orthonormal basis of
$\mathbb{R}^{m}$. For $b\in[d],\ i\in[n]$, define $A_{b}(i)\in M_{m}$ by

$\displaystyle A_{b}(i)v$
$\displaystyle:=\sum_{\begin{subarray}{c}S\in\mathcal{S}\\\
|S|=D-1\end{subarray}}\frac{\hat{p}_{=D}(S\cup\\{(b,i)\\})}{\sqrt{\mathrm{MaxInf}[p_{=D}]}}f_{S},$
$\displaystyle A_{b}(i)f_{S}$ $\displaystyle:=\delta_{(b,i)\in
S}f_{S-\\{(b,i)\\}},\ \mathrm{for}\ S\in\mathcal{S}\cup\emptyset.$

$A_{b}(i)$ are contractions because they map the vectors of an orthonormal
basis to orthogonal vectors without increasing their norms. Note that for
$b_{1}<\dots<b_{D}$ and $\mathbf{i}\in[n]^{D}$ we have that

$\langle f_{\emptyset},A_{b_{1}}(i_{1})\dots
A_{b_{D}}(i_{D})v\rangle=\frac{\hat{p}_{=D}(\\{(b_{1},i_{1}),\dots,(b_{D},i_{D})\\})}{\sqrt{\mathrm{MaxInf}[p_{=D}]}}.$

Thus,

$\displaystyle\|p_{=D}\|_{\operatorname{cb}}\geq\sum_{\begin{subarray}{c}\mathbf{b}\in[d]^{D}\\\
b_{1}<\dots<b_{D}\end{subarray}}\sum_{\mathbf{i}\in[n]^{D}}\hat{p}_{=D}(\\{(b_{1},i_{1}),\dots,(b_{D},i_{D})\\})\langle
f_{\emptyset},p(A_{1},\dots,A_{d})v\rangle=\frac{\operatorname{Var}[p_{=D}]}{\sqrt{\mathrm{MaxInf}[p_{=D}]}},$

which after rearranging yields Eq. 23. $\Box$

###  4.2. AA conjecture for homogeneous Fourier completely bounded polynomials

Finally, we prove a new case of the AA conjecture.

See 1.6

  * Proof:

Let $m:=1+{n\choose 0}+\dots+{n\choose d-1}$. Let
$\\{v,f_{\emptyset},f_{S}:S\subset[n],\ 1\leq|S|\leq d-1\\}$ be an orthonormal
basis of $\mathbb{R}^{m}$. Define the matrices $A(i)\in M_{m}$ as

$\displaystyle A(i)v$ $\displaystyle:=\sum_{\begin{subarray}{c}S\ni i\\\
|S|=d\end{subarray}}\frac{\hat{p}(S)}{\sqrt{\mathrm{MaxInf}[p]}}f_{S-\\{i\\}},$
$\displaystyle A(i)f_{S}$ $\displaystyle:=\delta_{S\ni i}f_{S-\\{i\\}},\
\mathrm{for}\ S\subset[n],\ 0\leq|S|\leq d-1,$

for $i\in[n]$ and $A(n+1):=0$. We claim that $(f_{\emptyset},v,A(i))$ has
Boolean behavior of degree $d$. $A(n+1)$ is clearly a contraction. For
$i\in[n]$, $A(i)$ is a contraction, as it maps vectors of the orthonormal
basis to orthogonal vectors without increasing the norm, because

$\|A(i)v\|^{2}=\sum_{S\ni
i}\frac{\hat{p}(S)^{2}}{\mathrm{MaxInf}[p]}=\frac{\mathrm{Inf}_{i}[p]}{\mathrm{MaxInf}[p]}\leq
1.$

On the other hand, if $S\subset[n]$ satisfies $|S|\leq d-1$, then any
$\mathbf{i}\in[n+1]^{d}$ with $S_{\mathbf{i}}=S$ either has a repeated element
of $[n]$ or has an appearance of the index $n+1$, which implies that $\langle
f_{\emptyset},A(i_{1})\dots A(i_{d})\rangle=0=\hat{p}(S)$. If $|S|=d$, then
any $\mathbf{i}\in[n+1]^{d}$ with $S_{\mathbf{i}}=S$ has $d$ different indices
in $[n]$ (corresponding to the elements of $S$), so in that case

(24) $\langle f_{\emptyset},A(i_{1})\dots
A(i_{d})v\rangle=\frac{\hat{p}(S)}{\sqrt{\mathrm{MaxInf}[p]}}.$

Putting everything together we conclude that $(f_{\emptyset},v,A(i))$ has
Boolean behavior of degree $d$, so

$\displaystyle\|p\|_{\operatorname{fcb},d}$
$\displaystyle\geq\sum_{S\subset[n]}\hat{p}(S)\langle
f_{\emptyset},A(i_{1})\dots
A(i_{d})v\rangle=\sum_{S\subset[n]}\frac{\hat{p}(S)^{2}}{\sqrt{\mathrm{MaxInf}[p]}}$
$\displaystyle=\frac{\operatorname{Var}[p]}{\sqrt{\mathrm{MaxInf}[p]}},$

where in the first equality we have used Eq. 24. After rearranging, the above
expression yields

$\mathrm{MaxInf}[p]\geq\left(\frac{\operatorname{Var}[p]}{\|p\|_{\operatorname{fcb},d}}\right)^{2}.$

$\Box$

######  Remark 4.3.

Sadly, we could not extend the proof of Theorem 1.6 to the general case. Now,
we aim to illustrate what would go wrong with our technique.

For example, consider a polynomial $p:\\{-1,1\\}^{4}\to\mathbb{R}$ with
$\deg(p)=2$ and $\|p\|_{\operatorname{fcb},4}\leq 1$. Ideally, we would want
to define unit vectors $u$ and $v$ and contractions $A(i)$ such that for every
$S\subset[4]$ and every $\mathbf{i}\in[\mathbf{i}^{S}]$ they satisfied

(25) $\langle u,A(i_{1})\dots
A(i_{4})v\rangle=\frac{\hat{p}(S)}{\sqrt{\mathrm{MaxInf}[p]}}.$

If we emulated the strategy of the proof of Theorem 1.6, then $A(1)v$ should
be a _normalized_ superposition of orthogonal vectors whose amplitudes are all
possible $\hat{p}(S_{\mathbf{i}})$ that have $i_{4}=1$. It can be seen that
all $\hat{p}(S)$ with $|S|\leq 2$ must be included among these amplitudes.
Hence, the _normalizing_ factor of $A(1)v$ should be
$\sqrt{\operatorname{Var}p}$, instead of $\sqrt{\mathrm{MaxInf}(p)}$. Thus, we
would reach

$\langle u,A(i_{1})\dots
A(i_{4})v\rangle=\frac{\hat{p}(S)}{\sqrt{\mathrm{Var}[p]}}$

instead of Eq. 25, which would lead to
$\|p\|_{\operatorname{fcb},4}\geq\sqrt{\operatorname{Var}p},$ that does not
say much about the influences.

######  Remark 4.4.

However, there might be a different way of, given a polynomial $p$ of degree
at most $d$, choosing $(u,v,A)$ with Boolean behavior of degree $d$ such that

$\langle u,A(i_{1})\dots
A(i_{d})v\rangle=\frac{\hat{p}(S_{\mathbf{i}})}{\mbox{\rm
poly}(d,\mathrm{MaxInf}[p])},$

for any $\mathbf{i}\in[n+1]^{d}$. If that was true, one could copy and paste
the proof of Theorem 1.6 and conclude 1.5. This reduces 1.5 to a question with
flavor of tensor networks (at the end of the day we are seeking for an MPS,
but caring about the norm of the matrices instead of the dimension) [CPGSV21]
and almost-quantum correlations (we could also say that we look for $(u,v,A)$
that define a correlation with some symmetry defined by the Boolean behavior,
without imposing the symmetries on the $A$) [NGHA15].

######  Question 4.5.

Given a polynomial $p$ of degree at most $d$, is there
$(u,v,A)\in\mathscr{BB}^{d}$ such that

$\langle u,A(i_{1})\dots
A(i_{d})v\rangle=\frac{\hat{p}(S_{\mathbf{i}})}{\mbox{\rm
poly}(d,\mathrm{MaxInf}[p])},$

for any $\mathbf{i}\in[n+1]^{d}$?

Acknowledgements. We want to thank Jop Briët, Sander Gribling and Carlos
Palazuelos for useful comments, conversations and encouragement. We also want
to thank the reviewers for helpful comments.

## References

  * [AA09] S. Aaronson and A. Ambainis.  The need for structure in quantum speedups.  _arXiv preprint arXiv:0911.0996_ , 2009.
  * [AA15] S. Aaronson and A. Ambainis.  Forrelation: A problem that optimally separates quantum from classical computing.  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , pages 307–316. 2015.
  * [AAI+16] S. Aaronson, A. Ambainis, J. Iraids, M. Kokainis, and J. Smotrovs.  Polynomials, quantum query complexity, and Grothendieck’s inequality.  In _31st Conference on Computational Complexity, CCC 2016_ , pages 25:1–25:19. 2016.  ArXiv:1511.08682.
  * [ABP19] S. Arunachalam, J. Briët, and C. Palazuelos.  Quantum query algorithms are completely bounded forms.  _SIAM J. Comput_ , 48(3):903–925, 2019.  Preliminary version in ITCS’18.
  * [ACC+22] P. Austrin, H. Chung, K.-M. Chung, S. Fu, Y.-T. Lin, and M. Mahmoody.  On the impossibility of key agreements from quantum random oracles.  In _Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part II_ , pages 165–194. Springer, 2022.
  * [Amb07] A. Ambainis.  Quantum walk algorithm for element distinctness.  _SIAM Journal on Computing_ , 37(1):210–239, 2007.
  * [Amb18] A. Ambainis.  Understanding quantum algorithms via query complexity.  In _Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018_ , pages 3265–3285. World Scientific, 2018.
  * [BBC+01] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf.  Quantum lower bounds by polynomials.  _J. ACM_ , 48(4):778–797, 2001.  ISSN 0004-5411.  doi:10.1145/502090.502097.
  * [BP19] J. Briët and C. Palazuelos.  Failure of the trilinear operator space Grothendieck inequality.  _Discrete Analysis_ , 2019.  Paper No. 8.
  * [BS21] N. Bansal and M. Sinha.  K-forrelation optimally separates quantum and classical query complexity.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1303–1316. 2021.
  * [BSdW22] N. Bansal, M. Sinha, and R. de Wolf.  Influence in completely bounded block-multilinear forms and classical simulation of quantum algorithms.  _arXiv preprint arXiv:2203.00212_ , 2022.
  * [CPGSV21] J. I. Cirac, D. Pérez-García, N. Schuch, and F. Verstraete.  Matrix product states and projected entangled pair states: Concepts, symmetries, theorems.  _Rev. Mod. Phys._ , 93:045003, Dec 2021.  doi:10.1103/RevModPhys.93.045003.
  * [DFKO06] I. Dinur, E. Friedgut, G. Kindler, and R. O’Donnell.  On the fourier tails of bounded functions over the discrete cube.  In _Proceedings of the thirty-eighth annual ACM symposium on Theory of computing_ , pages 437–446. 2006.
  * [DMP19] A. Defant, M. Mastyło, and A. Pérez.  On the fourier spectrum of functions on boolean cubes.  _Mathematische Annalen_ , 374(1):653–680, 2019.
  * [FGG07] E. Farhi, J. Goldstone, and S. Gutmann.  A quantum algorithm for the hamiltonian nand tree.  _arXiv preprint quant-ph/0702144_ , 2007.
  * [GL19] S. Gribling and M. Laurent.  Semidefinite programming formulations for the completely bounded norm of a tensor.  _arXiv preprint arXiv:1901.04921_ , 2019.
  * [Gro96] L. K. Grover.  A fast quantum mechanical algorithm for database search.  In _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_ , pages 212–219. 1996.
  * [Iva19] P. Ivanishvili.  Aaronson-ambainis conjecture.  https://extremal010101.wordpress.com/2019/10/29/aaronson-ambainis-conjecture/, 2019\.
  * [JZ11] R. Jain and S. Zhang.  The influence lower bound via query elimination.  _Electronic Colloquium on Computational Complexity - ECCC_ , 7, 02 2011.  doi:10.4086/toc.2011.v007a010.
  * [LR05] M. Laurent and F. Rendl.  Semidefinite programming and integer programming.  _Handbooks in Operations Research and Management Science_ , 12:393–514, 2005.
  * [LZ22] S. Lovett and J. Zhang.  Fractional certificates for bounded functions.  _Electronic Colloquium on Computational Complexity - ECCC_ , 107, 2022\.
  * [Mid05] G. Midrijanis.  On randomized and quantum query complexities.  _arXiv preprint quant-ph/0501142_ , 2005.
  * [Mon12] A. Montanaro.  Some applications of hypercontractive inequalities in quantum information theory.  _Journal of Mathematical Physics_ , 53(12):122206, 2012.
  * [NGHA15] M. Navascués, Y. Guryanova, M. J. Hoban, and A. Acín.  Almost quantum correlations.  _Nature communications_ , 6(1):6288, 2015.
  * [OSSS05] R. O’Donnell, M. Saks, O. Schramm, and R. A. Servedio.  Every decision tree has an influential variable.  In _46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05)_ , pages 31–39. IEEE, 2005.
  * [OZ15] R. O’Donnell and Y. Zhao.  Polynomial bounds for decoupling, with applications.  _arXiv preprint arXiv:1512.01603_ , 2015.
  * [Pau03] V. Paulsen.  _Completely Bounded Maps and Operator Algebras_.  02 2003.  ISBN 9780521816694.  doi:10.1017/CBO9780511546631.
  * [Sho99] P. W. Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  _SIAM review_ , 41(2):303–332, 1999.
  * [Sim97] D. R. Simon.  On the power of quantum computation.  _SIAM Journal on Computing_ , 26(5):1474–1483, 1997.  doi:10.1137/S0097539796298637.
  * [SSW21] A. A. Sherstov, A. A. Storozhenko, and P. Wu.  An optimal separation of randomized and quantum query complexity.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1289–1302. 2021.
  * [Tal20] A. Tal.  Towards optimal separations between quantum and randomized query complexities.  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 228–239. IEEE, 2020.
  * [Var74] N. T. Varopoulos.  On an inequality of von Neumann and an application of the metric theory of tensor products to operators theory.  _J. Functional Analysis_ , 16:83–100, 1974.  doi:10.1016/0022-1236(74)90071-8.
  * [YZ22] T. Yamakawa and M. Zhandry.  Verifiable quantum advantage without structure.  In _2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 69–74. IEEE, 2022.