# 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 $$\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 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 bitstring there are $$\frac{2^{n}}{2}=2^{n-1}$$ that yield the same value of $$f$$ as $$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.