Why doesn't Deutsch-Jozsa Algorithm show that P ≠ BQP? - Quantum Computing Stack Exchange most recent 30 from quantumcomputing.stackexchange.com 2019-11-15T08:25:26Z https://quantumcomputing.stackexchange.com/feeds/question/5215 https://creativecommons.org/licenses/by-sa/4.0/rdf https://quantumcomputing.stackexchange.com/q/5215 6 Why doesn't Deutsch-Jozsa Algorithm show that P ≠ BQP? 3yakuya https://quantumcomputing.stackexchange.com/users/5463 2019-01-17T11:54:03Z 2019-03-04T10:18:06Z <p>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.</p> <p>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 <span class="math-container">\$\mathsf{P}\$</span>), that we <em>can</em> solve in constant time on a quantum machine (so they are in <span class="math-container">\$\mathsf{BQP}\$</span>).</p> <p>This led me to a natural "conclusion" that <span class="math-container">\$\mathsf{P} ≠ \mathsf{BQP}\$</span>. However, I believe this is actually still an open question.</p> <p>Why doesn't Deutsch-Jozsa algorithm prove that <span class="math-container">\$\mathsf{P} \neq \mathsf{BQP}\$</span>?</p> https://quantumcomputing.stackexchange.com/questions/5215/why-doesnt-deutsch-jozsa-algorithm-show-that-p-%e2%89%a0-bqp/5217#5217 6 Answer by DaftWullie for Why doesn't Deutsch-Jozsa Algorithm show that P ≠ BQP? DaftWullie https://quantumcomputing.stackexchange.com/users/1837 2019-01-17T12:45:33Z 2019-03-04T10:18:06Z <p>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: <span class="math-container">\$\mathsf{P}\neq \mathsf{BPP}\$</span>. Why is this? For testing if an <span class="math-container">\$n\$</span> bit function is constant or balanced with certainty (as required by <span class="math-container">\$\mathsf{P}\$</span>), it could be that we have to check <span class="math-container">\$2^{n-1}+1\$</span> 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 <span class="math-container">\$1/2^{99}\$</span>. 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. </p> <p>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 <span class="math-container">\$f(x)\$</span>. 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 <span class="math-container">\$x_1\$</span> be the most significant bit of <span class="math-container">\$x\$</span>, and let <span class="math-container">\$f(x)=x_1\$</span>. If I wrote a program that systematically worked through all values of <span class="math-container">\$x\$</span>, if I was unlucky, I'd try all <span class="math-container">\$2^{n-1}\$</span> options with <span class="math-container">\$x_1=0\$</span> first. But if I saw the function definition, I'd know immediately that it's a balanced function.</p>