In the Bernstein Vazirani algorithm, the problem is to find $s$ for $f(x) = s \times x $ , $f : \{0,1 \}^n \to \{0 , 1 \} $. The literature says that the classical randomized algorithms also requires $ \Omega ( n)$ queries. I cannot find a proof for this claim. It seems it has something to do with Yao's principle. Can anybody help me to figure out how to prove this?
Thanks.
I would typically write $s\cdot x$ rather than $s\times x$. However, that's a minor thing. The important issue here is that $s\in\{0,1\}^n$. It has $n$ bits. However, each time you perform the classical function evaluation, you only get one bit of information, because $f$ only has one bit of output (Note that even if you phrase it as a reversible computation, although $n+1$ bits may be involved, $n$ of those contain the information about the input, so there's still only 1 new bit of information). If you only get 1 bit per query, and you need to get $n$ bits, it's going to take you at least $n$ queries.
(The obvious strategy to ensure that you only need $n$ queries is to choose the $n$ inputs which each consist of $n-1$ 0s and one 1 (in the $n$ different positions), so that the evaluation of $f$ is a different bit of $s$ each time.)
