Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer
Can you explain a bit further. –  user51905 Dec 6 '12 at 4:12
Sure, what is unclear? –  StuartHa Dec 6 '12 at 8:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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