In the 10th Anniversary Edition of Nielsen and Chuang Quantum Computation and Quantum Information textbook, Chapter 6.7 talks about Black Box algorithm limits.

It is given:

$f:\{0,1\}^n \rightarrow \{0,1\}$

$F:\{X_0,X_1,X_2,....,X_{N-1} \}\rightarrow \{0,1\}$ $\text{such that} \space F \space \text{is a boolean function,} \space X_k=f(k) \space and \space N=2^n-1$

It is then mentioned that:

We say that a polynomial $p: R^N\rightarrow R$ represents $F$ if $p(X)=F(X)$ for all $X \in \{0,1\}^N$ (where $R$ denotes the real numbers). Such a polynomial $p$ always exists, since we can explicitly construct a suitable candidate:
$$p(X)=\sum_{Y\in \{0,1\}^N} F(Y)\prod_{k=0}^{N-1}[1-(Y_k-X_k)^2]$$

Can someone explain this formula to me and whether the construction is a result of rigorous steps or by intuition? Will also be good if there are useful materials related to this for me to read.


Plug in an arbitrary $X$ into the formula.

Look at each summand for each particular $Y \in \{0,1\}^N$

If $Y \neq X$, then there must be at least one index $i$ such that $X_k \neq Y_k$. But both $Y_k$ and $X_k$ are only either $0$ or $1$. So if they are not equal, then the difference must be either $+1$ or $-1$. Square that and you get $1$ if they are different. Then one of the terms in the product will be $1-1=0$.

So if $Y \neq X$, that particular summand is $0$.

The only summand that remains is when $Y=X$. In that case each of the $1-(Y_k-X_k)^2$ are equal to $1$. So the product of all of those still gives $1$ and the result for that summand is $F(Y)=F(X)$.

Add together the summands for all the $Y$, and you get the only nonzero term, $F(X)$. So $p(X)=F(X)$ for all $X \in \{0,1\}^N$.

As desired, $p$ represents $F$. However, there may be simpler $p$ that still do the same. This is just one of them. The one of smallest degree gives the notion of degree of a boolean function which is related to sensitivity and block sensitivity.

| improve this answer | |
  • $\begingroup$ Thanks AHusain. I'll have to progress further to understand your last paragraph. $\endgroup$ – C.C. Jul 14 '19 at 4:59

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.