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 Answer 1


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

  • $\begingroup$ Could you elaborate in your answer on how you get the bound? Also how does Chernov ineq come into play? $\endgroup$
    – MonteNero
    Aug 15, 2022 at 4:48
  • $\begingroup$ @MonteNero I have edited my answer to explain a bit more how the probability of error was derived. Is it ok now? $\endgroup$ Aug 15, 2022 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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