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:
- Pick $x \in \{0, \ldots, 2^n - 1 \}$ uniformly at random
- Evaluate $f(x)$ and store it
- 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?
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$.