I have already posed the question on Math SE but I hope that people from QC community can help. I am starting studying QC, but first, I want to understand the classical view of algorithms. So in the following my question:

Here is the description of Deutsch-Jozsa problem: Let $f:\{0,1\}^n↦\{0,1\}$ be a function promised to be either constant or balanced ('balanced' means that f outputs as many $0$'s as $1$'s). Imagine that you try $k$ inputs (out of the $2^n$ available) and consistently find the same output. What is the probability that the function is actually constant? This link gives an answer as $1-1/2^{k-1}$. I am not able to reproduce this result and I have a prior question: how can the result not depend on $n$? Obtaining 5 equal results has a very different meaning if $n=10$ or $n=100$ isn't it?


Yes, it will depend on $n$ because sampling with replacement is assumed in the proof, which doesn't make sense if $n$ is finite. Intuitively, if a function $f$ really is balanced, and first output corresponding to certain random input is $0$ or $1$, then the probability that the second output corresponding to some other random input will be the same is less than $\frac{1}{2}$ (if $n < \infty$). The formula you state only gives a lower bound which is approached as $n\to\infty$. In general, $k=2^{n-1}+1$ inputs is sufficient to prove whether $f$ is constant or balanced, assuming it's guaranteed to be one of the two. As explained in the linked answer, without assuming replaceability, a tighter lower bound would have been $$\frac{2\binom{2^{n-1}}{k}}{\binom{2^{n}}{k}} = 1-\prod_{i=1}^{k-1} \left(\frac{2^{n-1}-i}{2^n-i}\right).$$ Notice that this becomes equivalent to your formula for $n\to\infty$ i.e., $$\lim_{n\to\infty} 1-\prod_{i=1}^{k-1} \left(\frac{2^{n-1}-i}{2^n-i}\right) = 1 - \frac{1}{2^{k-1}}.$$

Perhaps even better bounds can be found depending on the specific nature of $f$; I'll think about it.


Indeed, the formula assumes that $n=\infty$, and is approximately correct if $2^n \gg k$

  • $\begingroup$ The dependence is introduced by balanced condition; in fact the problem is not mathematically well posed, but without assuming that the function is balanced the probability does not make sense at all; maybe the problem should be mathematically stated using hypothesis testing framework, with "function balanced" being a null-hypothesis. $\endgroup$ – kludg Nov 24 '19 at 12:05

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.