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

  • 1
    $\begingroup$ Could you elaborate in your answer on how you get the bound? Also how does Chernov ineq come into play? $\endgroup$
    – MonteNero
    Commented 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$ Commented 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.