Classical Bernstein–Vazirani needs n queries for bounded error

Fix a random tape. The algorithm is a deterministic adaptive binary decision tree of depth at most $q$, since each query reply is one bit by [F2]. A binary tree of depth at most $q$ has at most $2^q$ leaves: this holds at depth zero, and at each added level every prior leaf creates at most two children. Each leaf outputs one candidate secret, so at most one of the $2^n$ secrets reaching that leaf can be correctly recovered. Hence success averaged uniformly over secrets is at most $2^q\mathrm{/}{2}^n=2^{q-n}$.

For fixed $n$ and $q$, there are finitely many deterministic depth-at-most-$q$ decision trees on the finite address set, with output labels in $\{0,1{\}}^n$. The random-tape algorithm induces weights on this finite strategy set by grouping tapes according to their tree. Averaging step 1.1 over this finite distribution leaves average success at most $2^{q-n}$. If worst-case success is at least $2\mathrm{/}3$ on every secret, its average under the uniform secret law is at least $2\mathrm{/}3$. For $q\le n-1$, the upper bound is at most $1\mathrm{/}2<2\mathrm{/}3$, a contradiction; therefore $q\ge n$.

For each coordinate $i<n$, query $e_i$, the string with one at $i$ and zeros elsewhere. By [F2], the reply is $f_a(e_i)=a_i$. These $n$ replies give the entire secret, so $n$ queries suffice exactly.