Why doesn't Deutsch-Jozsa Algorithm show that P ≠ BQP?

Question

To my understanding, Deutsch-Jozsa algorithm solves a specific problem in constant time, using a fixed circuit depth, compared to a classical deterministic algorithm, which would require time exponential to the number of bits used to store the input.

I thought this proves that there exist certain problems that we cannot solve in polynomial time on a classical machine (so they are not in $\mathsf{P}$), that we can solve in constant time on a quantum machine (so they are in $\mathsf{BQP}$).

This led me to a natural "conclusion" that $\mathsf{P} ≠ \mathsf{BQP}$. However, I believe this is actually still an open question.

Why doesn't Deutsch-Jozsa algorithm prove that $\mathsf{P} \neq \mathsf{BQP}$?

Answer 1

I believe there are two issues here. The first isn't anything wrong with your statement, but rather that you could make a far stronger (non-quantum) statement by the same reasoning: $\mathsf{P}\neq \mathsf{BPP}$. Why is this? For testing if an $n$ bit function is constant or balanced with certainty (as required by $\mathsf{P}$), it could be that we have to check $2^{n-1}+1$ different inputs to see if they're all the same or not. However, imagine we just check 100 different, randomly chosen, input strings and see if they're all the same. The probability of a balanced function giving all the same outputs is approximately $1/2^{99}$. Hence we can determine in constant time on a classical computer whether the function is constant or balanced up to some finite accuracy threshold. It's certainly within BPP.

The question still remains as to where the reasoning falls down. The fallacy is in the construction of the algorithm. It uses an oracle. That oracle computes something using the function in a very specific way. So the statement is really "if we compute using this oracle, then we can prove that separation". It's said to be separation with respect to that oracle. Now you might say "that oracle is just the evaluation of $f(x)$. What else could there be?" but if you actually implement the algorithm, you have to program the function. So you have to know the function (or somebody else provides you with the code) and maybe you could analyse the function specification directly rather than just blindly evaluating it. (There doesn't have to be a proof that you can do better, we just have to allow for the possibility.) As a trivial example, let $x_1$ be the most significant bit of $x$, and let $f(x)=x_1$. If I wrote a program that systematically worked through all values of $x$, if I was unlucky, I'd try all $2^{n-1}$ options with $x_1=0$ first. But if I saw the function definition, I'd know immediately that it's a balanced function.

Answer 2

I will try to give an answer from complexity theory's point of view. This question should be asked in cs.stackexchange by the way. The Deutsch-Jozsa problem has an efficient algorithm on quantum computation and on a classical probabilistic Turing machine, so it is in BQP and BPP. There is no result that says: if you show a problem A in BQP and not in P, then P is different from BQP. Thus, in order to prove P $\ne$ BQP, first consider the probabilistic part of P which is BPP [since complexity theorist believe that P $=$ BPP and it is better to compare a a probabilistic version of P with the quantum world of P, which is BQP] then according to complexity's theorist, they say that you need to prove something very hard like: P $\ne$ PSPACE to work on this BBP$ \ne$ BQP, here is a part of the answer by Greg Kuperberg says:

BQP $\ne$ BPP is another thing that people can't prove, because they are both sandwiched between P and PSPACE and no one can prove that P $ \ne $ PSPACE either. (In fact it's worse than that, there are major results on how not to prove that P $\ne$ PSPACE.)

How is it that Deutsch-Jozsa has a probabilistic polynomial running time? Here for this paper, it states the following in page 2:

the Deutsch-Jozsa problem has an efficient solution on a classical probabilistic Turing machine [8, 9]