# Generalization of the Deutsch problem

This problem concerns a straightforward generalization of the Deutsch problem discussed for functions with more than one bit as input. This time, we have a Boolean function f that takes a $4$-bit number as input and outputs $0$ or $1$, i.e., $f:\{0,1\}^4 \to \{0,1\}$. Thus, an input to $f$ is one of 16 possible 4 bit binary numbers:

$0000$, $0001$, $0010$, $0011$, $0100$, $0101$, $0110$, $0111$, $1000$, $1001$, $1010$, $1011$, $1100$, $1101$, $1110$, $1111$.

We are also told that $f$ is one of the following two types:

• either $f$ is a constant function, i.e., $f(x)$ is the same for all $16$ possible values of the input $x$, or
• $f$ is a balanced function, i.e., $f(x)$ is $0$ for exactly $8$ of the possible $16$ inputs and $f(x)$ is $1$ for the remaining $8$ of the possible $16$ inputs.

we are allowed to do is to use the circuit for $f$ as a "black box" by giving an input x to the circuit for $f$ and observing the output $f(x)$. This is called a "query" operation.

Show that a classical probabilistic algorithm can determine if $f$ is balanced or constant with probability at least $2/3$ by using $2$ queries.

Hint: (Obviously, we cannot do this using a deterministic algorithm. Unless the deterministic algorithm sees the output for at least $9$ input values, there is no way for it to find out if the function is balanced or constant).

Think about picking the two inputs uniformly and randomly from the set of 16 possible inputs. Your final result could depend probabilistically on the result of these two queries.

-
It would be good if you showed an attempt. Assuming f is balanced, what is the probability that a random pair evaluates to the same values? –  Karolis Juodelė Dec 5 '12 at 19:26

Let your algorithm be that you guess constant for outputs $00$ and $11$, and guess balanced otherwise.
Pr(wrong guess) = Pr(output $00$, $11$ | $f$ is balanced) $\cdot$ Pr($f$ is balanced) + Pr(output $01$, $10$ | $f$ is constant) $\cdot$ Pr($f$ is constant) $= (.5)(.5) + (0)(.5) = \frac{1}{4}$