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.

  • $\begingroup$ 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? $\endgroup$ – 3yakuya Jan 17 at 13:16
  • $\begingroup$ One would have to be quite precise when writing down such a claim, but yes, that's roughly the understanding. $\endgroup$ – DaftWullie Jan 17 at 13:54
  • $\begingroup$ 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? $\endgroup$ – glS Jan 18 at 10:04
  • $\begingroup$ @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. $\endgroup$ – DaftWullie Jan 18 at 10:50
  • $\begingroup$ 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? $\endgroup$ – glS Jan 18 at 17:59

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.