## Analysis on the hypercube with applications to quantum computing

### Edited by org.aimpl.user:haonan.zhang@ist.ac.at

We fix some notation. For all $n\ge 1$, any function $f:\{-1,1\}^n\to \mathbb{R}$ has the unique Fourier expansion
\begin{equation*}
f=\sum_{S\subset [n]}\widehat{f}(S)\chi_S
\end{equation*}
where for each $S\subset [n]:=\{1,\dots, n\}$, $\widehat{f}(S)\in\mathbb{R}$ and $\chi_S(x):=\prod_{j\in S}x_j$. The degree of $f$ is the maximal $|S|$ for which $\widehat{f}(S)\neq 0$. For $d\ge 1$, $f$ is $d$-homogeneous in case it is a linear combination of $\chi_S,|S|=d$. The variance of $f$ is
\begin{equation*}
\text{Var}(f)=\sum_{S\neq \emptyset}\widehat{f}(S)^2.
\end{equation*}
For $1\le j\le n$, the influence of $j$-th variable of $f$ is defines as
\begin{equation*}
\text{Inf}_j(f):=\sum_{j\in S}\widehat{f}(S)^2.
\end{equation*}
We always equip $\{-1,1\}^n$ with the uniform probability measure and denote by $\|\cdot\|_p$ the corresponding $L_p$-norm, $1\le p\le \infty$. For $1\le j\le n$, denote
\begin{equation*}
D_j f(x):=\frac{f(x)-f(x^{\oplus j})}{2},
\end{equation*}
where $f(x^{\oplus j}):=f(x_1,\dots, x_{j-1}, -x_j,x_{j+1},\dots, x_n)$. Note that $D_j^2=D_j$. The heat semigroup on $\{-1,1\}^n$ is $P_t=e^{-t\Delta}$ with $\Delta=\sum_{j=1}^{n}D_j$.
The sensitivity of $f$ at $x\in\{-1,1\}^n$ is defined as
\begin{equation*}
s(f,x):=\sharp {1\le j\le n: f(x)\neq f(x^{\oplus j})},
\end{equation*}
and the sensitivity of $f$ is
\begin{equation*}
s(f):=\max{s(f,x):x\in{-1,1}^n}.
\end{equation*}
Similarly, the block sensitivity $bs(f,x)$ of $f$ at $x$ is the maximum number of disjoint subsets $B_1,\dots, B_k$ of $[n]$ such that $f(x)\neq f(x^{\oplus B_j})$ for all $1\le j \le k$, where $x^{\oplus B}$ denotes the input that flips the values in $B\subset [n]$. The block sensitivity $bs(f)$ of $f$ is then defined as $\max\{bs(f,x):x\in\{-1,1\}^n\}$.

### Sections

Cite this as: *AimPL: Analysis on the hypercube with applications to quantum computing, available at http://aimpl.org/hypercubequantum.
*