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

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}$$?

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.

• Thank you for your explanation! To clarify: if we had an algorithm that worked like Deutsch-Jozsa (i.e. constant time solution for a problem that takes exponential time on a classical machine), but did not use an oracle of any kind (i.e. all functions used for gate definitions are known) that would prove that $BQP ≠ P$? Ex. if it was proven that order-finding is not in P, and having Shor's algorithm? – 3yakuya Jan 17 '19 at 13:16
• One would have to be quite precise when writing down such a claim, but yes, that's roughly the understanding. – DaftWullie Jan 17 '19 at 13:54
• I don't understand why the first reasoning should lead to the conclusion $P\neq BPP$, even just with respect to the oracle. You give a specific deterministic inefficient algorithm, and show that there is an efficient probabilistic algorithm for the same task. This doesn't however rule out the existence of an equally efficient deterministic algorithm, does it? For example, it could be that deterministically checking the function over a specific, deterministically generated subset of inputs gives you the same performance as the probabilistic algorithm. Or am I missing the point here? – glS Jan 18 '19 at 10:04
• @glS However you deterministically generate inputs (for the case of P), there will always be a balanced f which only shows up on the $2^{n-1}+1$th step. – DaftWullie Jan 18 '19 at 10:50
• ah, fair enough. So is it correct to say that your example shows that $P\neq BPP$ with respect to an oracle, even though not unconditionally? – glS Jan 18 '19 at 17:59

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]

• "The Deutsch-Jozsa problem has an efficient algorithm on (...) a classical probabilistic Turing machine" what algorithm are you referring to here? – glS Nov 22 '19 at 0:05
• @glS Well, I remember read it somewhere, I put a link for the paper where it says so. However, I don't know exactly how it can be done, so I should read again references of that paper. But anyway, even if it is proved hard in classical and efficient in quantum, then it doesn't mean we can say BQP$\ne$BPP – YOUSEFY Nov 22 '19 at 3:07