Return to Question

A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$.

The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^n \to R$:

$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x)$

One of $g$ or $h$ is the true Fourier spectra of $f$ and the other one is just a fake Fourier spectra belonging to an unknown Boolean function.

It is not hard to show that a $PH$ machine, cannot even approximate $F(s)$ for any $s$.

What is the query complexity of deciding which one is the true one?

It is interesting to me, since if this problem is not in $PH$, then one can show that there exists an oracle relative to which $BQP$ in not a subset of $PH$.

A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$.

The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^n \to R$:

$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x)$

One of $g$ or $h$ is the true Fourier spectra of $f$ and the other one is just a fake Fourier spectra belonging to an unknown random Boolean function.

It is not hard to show that a $PH$ machine, cannot even approximate $F(s)$ for any $s$.

What is the query complexity of deciding with high success probability which one is the true one  ?

It is interesting to me, since if this problem is not in $PH$, then one can show that there exists an oracle relative to which $BQP$ in not a subset of $PH$.

A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n$ to $\{ -1,1 \}$ , and two Fourier spectra $g$ and $h$.

The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^n$ to $R$:

$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s.x \mod\ 2 \right) f(x)$

One of $g$ or $h$ is the true Fourier spectra of $f$ and the other one is just a fake Fourier spectra belonging to an unknown Boolean function.

It is not hard to show that a $PH$ machine, cannot even approximate $F(s)$ for any $s$.

What is the query complexity of deciding which one is the true one?

It is interesting to me, since if this problem is not in $PH$, then one can show that there exists an oracle relative to which $BQP$ in not a subset of $PH$.

A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$.

The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^n \to R$:

$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x)$

One of $g$ or $h$ is the true Fourier spectra of $f$ and the other one is just a fake Fourier spectra belonging to an unknown Boolean function.

It is not hard to show that a $PH$ machine, cannot even approximate $F(s)$ for any $s$.

What is the query complexity of deciding which one is the true one?

It is interesting to me, since if this problem is not in $PH$, then one can show that there exists an oracle relative to which $BQP$ in not a subset of $PH$.