# Kaye Exercise 6.4.2 Classical Deutsch-Jozsa algorithm

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.

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"
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$$.