Problem $3.$ The Bernstein$-$Vazinani problem.

Suppose $f$:$\{0,1{\}}^n\{0,1\}$ is a function of the form

for some unknown $s_{i}n\{0,1{\}}^n.$ Given a black box for $f,$ how many classical queries are required to

learn $s$ with certainty?

Prove that for any $n-$bit string $u_{i}n\{0,1{\}}^n,$

where $0_{?}$ denotes the $n-$bit string $00$dots$0.$

Let $U_f$ denote a quantum black box for $f,$ acting as $U_f|x_{\text{:}}$ for any

$x_{i}n\{0,1{\}}^n$ and yin$\{0,1\}.$ Show that the output of the following circuit is the state $|s_{\text{:}}.$

What can you conclude about the quantum query complexity $($number of queries to the

oracle$)$ of learning $s?$