6
$\begingroup$

The Deutsch-Jozsa problem is a problem that quantum computers can solve deterministically, while classical computers cannot. However, there are classical algorithms that can solve it probabilistically. A simple example of such an algorithm is:

Check 500 inputs at random. If all of these inputs are equal, output "constant." Else, output "balanced."

This works because the probability of measuring all 0's or all 1's in a balanced function is $\frac{1}{2^{500}}$, meaning that the error is less than $\frac{1}{3}$. With the existence of this algorithm, Deutsch-Jozsa is in BPP.

And I would think that this also implies that the problem is in NP. But I can't find a (deterministic polynomial time) algorithm to verify if a solution is correct given some oracle and an output.

$\endgroup$
1
  • 2
    $\begingroup$ The relationship between BPP and NP is not known. $\endgroup$ Mar 16, 2023 at 5:58

1 Answer 1

9
$\begingroup$

NP is a class of decision problems, so before considering the membership of the problem in NP, we first need to formulate a decision variant of it. This entails, among other things$^1$, the choice of YES and NO instances. The problem belongs to NP if there is a certificate for YES instances that can be checked in polynomial time. Similarly, it belongs to co-NP if there is a certificate for NO instances that can be checked in polynomial time.

If we formulate the decision problem so that balanced functions represent the YES instances and constant functions represent the NO instances, then the problem is in NP. If we do it the other way, then it is in co-NP. In each case the certificate is just a pair of inputs $(x,y)$ such that $f(x)\ne f(y)$.


$^1$ In formulating the decision problem precisely, we will encounter other caveats. In particular, we need to constrain admissible inputs to the union of YES and NO instances due to the fact that the original problem is a promise problem. Other changes concern the way the computer accesses the function $f$. Specifically, we need to switch from using an oracle for $f$ to some encoding of $f$ on the tape of the Turing machine.

$\endgroup$
1
  • $\begingroup$ Is there a polynomial time algorithm to convert between "Turing machine encoding of $f$" and "oracle of $f$", as you said in your footnote? $\endgroup$ Mar 17, 2023 at 0:19

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.