# Deutsch-Jozsa Algorithm for Non-Balanced+Non-Constant Functions?

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?

• This blog post covers something along the lines of what you're asking (black box separations between quantum/classical queries): scottaaronson.com/blog/?p=2325 – Craig Gidney Nov 2 '16 at 16:48
• That will take a couple read-throughs to get what's going on, but it definitely seems interesting! +1 – OperaticDreamland Nov 4 '16 at 1:59

• Yeah, I've come to the same conclusion after putting slightly more thought into it. Originally, I was thinking that if you made a definition like, "A Boolean function is called ** $(k,0)$-balanced** if $(n-k)/2$ elements of the domain output 0, another $(n-k)/2$ output 1, and then the remaining $k$ outputs are 0's" (and, of course, similarly one can have $(0,k)$-balanced functions where the extra $k$ outputs are 1's), then sending them through the above algorithm will give you $\pm 2^{-n+k}$ for the coefficient of $|0\rangle^{\otimes n}$; thus distinguishing it from the $\pm 1$ for... – OperaticDreamland Nov 4 '16 at 1:56
• ... the constant functions and 0 for the balanced ($\equiv \ (0,0)$-balanced) functions... but that's ignoring the last part where you move to the amplitudes. It all falls apart there. Oh well! :) Are there any other known algorithms which do satisfy an "enlarged" promise beyond that for D-J? – OperaticDreamland Nov 4 '16 at 1:58