Can anyone help with this problem from, An Introduction to Quantum Computing, Phillip Kaye, Raymond Laflamme, Michele Mosca
Exercise 6.4.2: Show that a probabilistic classical algorithm that makes $O(n)$ queries can with probability at least $1 − \frac{1}{2^n}$ correctly determine whether $f$ is constant or balanced.
Hint: Use the Chernoff bound (Appendix A.1).
I am new to Quantum Computing and deutsch jozsa problem, and Hint is not helping.
Consider the following algorithm:
1. Choose $n+1$ bitstrings $\{q_1,\dots,q_{n+1}\}\subseteq \{0,1\}^n$ uniformly at random (allowing repetitions).
2. If $f(q_1)=\dots=f(q_{n+1})$ return "CONSTANT"
3. Else return "BALANCED"
Now let's analyze the above algorithm. If $f$ is constant then the algorithm will always be correct. If on the other side $f$ is balanced then the probability that our algorithm will return CONSTANT is bounded by the probability $$\tag{1}\mathbb{P}\left(f(q_1)=f(q_2), f(q_1)=f(q_3), \dots, f(q_1)=f(q_{n+1})\right).$$ The $n$ events $f(q_1)=f(q_i)$ are independent and have probability of occurring equal to $\frac{2^{n-1}}{2^n}=\frac{1}{2}$ (since out of the $2^n$ possible bitstrings there are $\frac{2^{n}}{2}=2^{n-1}$ that yield the same value of $f$ as $f(q_1)$ and thus the probability of error is at most $\frac{1}{2^n}$, as required. Notice that the Chernoff bound was not used here.
Basically, each of the events in Eq. 1 of this answer will occur with a probability of 1/2, and there are $n$ such events, so the overall probability will be $1/2^n$.
