| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

1. Aaronson-Ambainis Conjecture

Here we collect some problems related to the Aaronson-Ambainis Conjecture.

    1. Aaronson-Ambainis conjecture


      Add remark

      Problem 1.1.

      Show that there exist $C_1,C_2>0$ such that for all $n\ge 1$, for all $f:\{-1,1\}^n\to [-1,1]$, we have \begin{equation} \max_{1\le j\le n}\text{Inf}_j(f)\ge C_1\left(\frac{\text{Var}(f)}{\deg(f)}\right)^{C_2}. \end{equation}
          Some partial cases have been known. For example, it is true when
      1. the function $f$ is symmetric;
      2. the function $f$ is Boolean i.e., it takes values in $\{-1,1\}$;
      3. the constant $\deg(f)$ is replaced by $e^{\deg(f)}$.

        • A stronger form of Aaronson-Ambainis conjecture


          Add remark

          Problem 1.2.

          Show that there exists $C>0$ such that for all $n\ge 1$ and for all $f:\{-1,1\}^n\to \mathbb{R}$ we have \begin{equation} \text{Var}(f)\le \|f\|_\infty\deg(f)^C \max_{1\le j\le n}\|D_j f\|_2. \end{equation}

            • Some special cases


              Add remark

              Problem 1.3.

              Show that the above Aaronson-Ambainis conjecture and its stronger form are valid for
              1. all homogeneous functions on $\{-1,1\}^n$;
              2. all functions $f:\{-1,1\}^n\to \mathbb{R}$ whose Fourier coefficients are of the form \begin{equation*} |\widehat{f}(S)|=p(|S|), \end{equation*} where $p:\mathbb{N}\to \mathbb{R}$ is any function;
              3. all functions $f$ that has the following invariance property \begin{equation} f(x_1,\dots, x_n)=f(x_2,\dots, x_n,x_1); \end{equation}
              4. functions that satisfy some more general invariance properties.

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