# Probabilistic query complexity lower bound for Bernstein-Vazirani problem

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.)