2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 5, 2022 at 22:04
  • $\begingroup$ @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 $\endgroup$
    – Loic Stoic
    Sep 6, 2022 at 1:28

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.