Is the Deutsch-Jozsa problem in NP?

Question

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.

Answer 1

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