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.

  • $\begingroup$ 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? $\endgroup$ – 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}$

| cite | improve this answer | |
  • $\begingroup$ Can you explain a bit further. $\endgroup$ – user51905 Dec 6 '12 at 4:12
  • $\begingroup$ Sure, what is unclear? $\endgroup$ – countunique Dec 6 '12 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.