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

Question

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.

• D.W.: 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.
• Loic Stoic: @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

Answer 1

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).

See also, e.g., NP-complete promise problems?.