The Deutsch-Jozsa problem asks to determine whether a function $f: \{0, \ldots, 2^n - 1 \} \to \{ 0, 1\}$ is constant or balanced (half of the inputs yield 1, the other half yield 0).

Suppose we have the following classical randomized algorithm.

Repeat k times:

  1. Pick $x \in \{0, \ldots, 2^n - 1 \}$ uniformly at random
  2. Evaluate $f(x)$ and store it
  3. If $f(x)$ differs from any previous $f(x)$, then output balanced

Otherwise, output constant

I am trying to determine the probability of error of this algorithm, that is, the probability that the output is constant despite $f$ being balanced. My initial guess is $\frac{1}{2^{k-1}}$, since whatever the first $x$ selected is, if $f$ is balanced, then each subsequent k - 1 queries will have the same $f$ value with probability $\frac{1}{2}$. But for $k = 1$, this error is $1$ so I believe it is incorrect. What is the correct answer and reasoning?

  • $\begingroup$ Can you explain why you think the error being 1 when $k = 1$ is incorrect? Line 3 can only output "balanced" if $k \geq 2$. $\endgroup$ – ljeabmreosn May 26 at 21:06
  • $\begingroup$ @ljeabmreosn I suppose you're right; it is just an error in the algorithm. My thinking is that when $k = 1$, the error probability should be $\frac{1}{2}$ because one query provides no information and is essentially a coin flip. How could the algorithm be edited to accommodate this behavior? $\endgroup$ – Suchetan Dontha May 26 at 21:17
  • $\begingroup$ I think the algorithm is fine as is. The $k=1$ case is one special case. From the question setup, there is no probability distribution associated with $f$. I suppose you could modify the algorithm in the special case that $k=1$, but more than likely, you'll deal with the following setup: Given $f$ and $\varepsilon >0$, find the appropriate $k$ such that the probability of error is less than $\varepsilon$. $\endgroup$ – ljeabmreosn May 26 at 21:38

It seems you may not be clearly distinguishing between the (unconditional) probability of error and the probability of error conditional on $f$ being balanced.

The unconditional probability of error can’t be determined because the problem statement doesn’t tell us the probabilities for $f$ to be constant or balanced.

The probability of error conditional on $f$ being balanced is indeed $2^{-(k-1)}$, and thus $1$ for $k=1$, which is correct since the algorithm will always output “constant” if $k=1$.

| cite | improve this answer | |
  • $\begingroup$ But from this algorithm, the only source of error is when it outputs that $f$ is constant when it is balanced, right? If not, for some context, the question I was answering only asked for the minimum number of queries that had to be made in order for the probability of error to be less than $\frac{1}{2}$. It could be that I'm thinking in the complete wrong direction. $\endgroup$ – Suchetan Dontha May 27 at 0:26
  • $\begingroup$ @SuchetanDontha: I'm not sure what contrast you're indicating by "But". Yes, the only source of error is outputting "constant" when $f$ is balanced; I don't see any contrast between that and what I wrote. In particular, that doesn't mean that the unconditional error probability can be determined. This is the probability of outputting "constant" when $f$ is balanced, times the probability that $f$ is balanced, and we don't know the latter. $\endgroup$ – joriki May 27 at 0:44
  • $\begingroup$ However, if you only want to make sure that the error probability is below some threshold, you can ensure that the conditional error probability is below that threshold, because the unconditional error probability is at most the conditional error probability (with equality obtaining exactly if $f$ is balanced with probability $1$). $\endgroup$ – joriki May 27 at 0:44
  • $\begingroup$ Ok, this makes a lot of sense to me. I said "but" because I thought that the two were the same. If the error probability is $\frac{1}{2^{k-1}} P(f$ $balanced)$, then this is consistent with other references like wikipedia that state this error probability is $\frac{1}{2^{k}}$, where the assumption is that $f$ is balanced half the time. What is the reasoning behind why the unconditional error probability is equal to this product? $\endgroup$ – Suchetan Dontha May 27 at 1:08
  • $\begingroup$ @SuchetanDontha: That's just the law of total probability, taking into account that the other conditional error probability is zero. $\endgroup$ – joriki May 27 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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