Note: I'd imagine this will be a simple yes/no question for people better versed in this topic than myself, but nevertheless I'll provide a bit of background first for the edification of anyone who might come across this later. As such, one may wish to skip to the bottom for the actual question.
Essentially any introductory text on quantum computing (e.g. Nielsen and Chuang's classic book, $\S$1.4.4) will include some discussion on the Deutsch-Jozsa algorithm, the idea of which is fairly straight-forward. It is (roughly following Nielsen and Chuang for convenience) a solution to the Deutsch Problem:
Deutsch Problem: Bob has an oracle circuit (implementing a unitary transformation) $U_f$ that, given some $(n+1)$-bit input $|x\rangle|y\rangle$, gives $|x\rangle|y\oplus f(x)\rangle$, with $|x\rangle\equiv|x_1\rangle\cdots|x_n\rangle$, as an output for some unknown function $ \ f:\{0,1\}^n\longrightarrow \{0,1\}$. Schematically, we have:
Now, suppose that $f$ is either constant or balanced (i.e. the output is 0 half the time, 1 for the other half). Then one can ask: if Alice lives far, far away from Bob and she wants to sent Bob $n+1$ bits, who will then stuff them in his nifty oracle and send the resulting bits back to her, then how many such queries does Alice have to make to identify $f$ as constant or balanced?
In the classical bit case, the answer is straightforward: Alice can only send one value for $x$ at a time, and so she needs at least $2^{n-1}-1$ queries to figure out which kind of $f$ they're dealing with.
In the quantum case we can utilize interference and this question can be answered using the Deutsch-Jozsa algorithm, as mentioned above. Explicitly:
Deutsch-Jozsa Algorithm: Alice takes$|0\rangle^{\otimes n}|1\rangle$, shoves them into the Hadamard transform $H^{\otimes(n+1)}$ (i.e. applies a Hadamard gate to each of the qubits being tensored), sends that to Bob, and then applies $H^{\otimes n}\otimes \text{Id}$ to what Bob sends back. Schematically, one has:
Then she is left with (after a short-ish computation, see N&C's book for details):
$$ |\psi\rangle=\sum_{x,z\in\{0,1\}^n}\frac{(-1)^{x\odot z+f(x)}}{2^n}|z\rangle\left(\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right). $$
Finally, one observes that the coefficient of $|0\rangle^{\otimes n}$ state in the above sum is
$$ \sum_{x\in\{0,1\}^n}\frac{(-1)^{f(x)}}{2^n}=\left\{ \begin{array}{cr}
\pm 1, & f \text{ is constant} \\
0, & f \text{ is balanced}
\end{array} \right., $$which means that a measurement all other coefficients are 0 if $f$ is constant, and at least one of the other coefficients is nonzero if $f$ is balanced; thus a measurement resulting in all $0$'s means tells Alice that $f$ is constant, and any other result means that $f$ is balanced. Therefore, Alice needs only a single query to identify which type of function is hiding in Bob's oracle — a significant improvement on the classical case indeed!
With all of that out of the way, we can finally get to the question:
Question: It seems to me that most Boolean functions like $f$ above are not constant nor balanced. The mathematician in me then cannot help but wonder: can this algorithm actually allow you to distinguish between other Boolean functions as well? Is this even an interesting question to ask?
Best Answer
No, the Deutsch-Jozsa algorithm only allows you to deterministically distinguish between constant and balanced functions. One would of course expect that to some extent other functions can still be distinguished probabilistically.
The Deutsch-Jozsa algorithm is thus an example of a "promise problem", which only works on inputs which satisfy a certain promise (here, being constant or balanced).