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?



1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.