# Why doesn't the Deutsch Jozsa algorithm on a classical computer show P != BPP?

I recently saw this answer on a question in the Quantum Computing SE. The answer demonstrated how we can probabilistically find the answer to the Deutsch Jozsa problem on a PTM in $$O(1)$$ time, with an error of $$\frac{1}{2^k}$$, where k is the number of entries we check.

I will provide an algorithm and proof of why (to my understanding it shows this).

Assume that on a deterministic turing machine the runtime is $$O(2^N)$$.

on a PTM, in order for a problem to be in BPP, you must have an error $$\epsilon < \frac{1}{3}$$ for a run of any size.

Deutsch Jozsa problem gives us a function, $$f$$, which maps inputs of size $$N$$ to a boolean output $$0$$ or $$1$$.

Algorithm:

1. Pick a random sample of $$K$$ input values, each of length $$N$$.
2. Run $$f$$ with inputs from $$K$$
3. Label outputs $$o_1$$, $$o_2$$, ..., $$o_3$$
4. If there is at least one $$o$$ that is not equal to the rest, you have a balanced function.
5. Otherwise, you have a constant function

The time complexity of this depends only on the size of the constant $$K$$ which is contant, so our time complexity is $$O(K) \rightarrow O(1)$$.

The error in the above function is $$\epsilon = 0$$ if the output is balanced, and $$\epsilon = \frac{1}{2^k}$$, where $$k$$ is the length of $$K$$, for a constant function.

The error above can be seem by the below proof:

Label the first output as $$o_1$$.

If we are given a constant function, we will always output the correct answer. This is because we will never observe an $$o$$ that does not equal the rest in a constant function.

If we were given a balanced function, the probability of sampling an input that maps to an output equal to $$o_1$$ is $$\frac{1}{2}$$.

Because each call is independent, if we were given a balanced function, the probabilities multiply, and we get $$\frac{1}{2^k}$$, where $$k$$ is the number of calls.

If we output constant when given a balanced function, this is because we have not observed any differing value, which has a probability of $$\frac{1}{2^k}$$.

If $$k > 2$$, the error is a maximum of $$\frac{1}{4}$$. So this should meet the requirements of BPP.

This also does not rely on an oracle, like in the quantum case, but a function. So the original argument of having to create the actual oracle does not work here, I think.

• In English, normally a question should end with a question mark ("?"). I encourage you to edit your question to explain why you think this should show that P != BPP. Try to write out a proof that P != BPP in detail.
– D.W.
Commented Sep 5, 2022 at 22:04
• @D.W. Yeah I wrote this pretty poorly originally, sorry. I wrote out an algorithm on how to solve the Deutsch Jozsa problem on a PTM in a constant number of calls. Thanks for pointing it out. I'm sure that I'm missing something, but I can't see where Commented Sep 6, 2022 at 1:28

One problem is already explained in the answer you link to, in the part starting with "The fallacy is ... It uses an oracle.". In the Deutsch Jozsa problem, $$f$$ is provided as an oracle, so you have not proved anything about $$P$$ vs $$BPP$$, as the latter does not involve any oracles.
A second (but closely related) problem: you have not provided any justification for why a PTM for the Deutsch Jozsa problem implies $$P \ne BPP$$. That step is omitted in your proof, and in fact, it doesn't follow. Indeed, if you refer to the formal definition of $$BPP$$, you will discover that the Deutsch Jozsa problem is not in $$BPP$$. $$BPP$$ is defined in terms of formal languages, but there is no formal language corresponding to the Deutsch Jozsa problem. In short-hand, theoretical computer scientists say that the Deutsch Jozsa problem is a promise problem, and promise problems are outside the scope of complexity classes like $$P$$ or $$BPP$$ (which are concerned with decision problems).