Parity of a boolean function

I was doing a course on Quantum Computing. There was a question in problem set. Which is given below (Question No.5)

Here the parity function is defined as(As per the instructor):
$$y_i = 1-2x_i$$ $$Parity(y) = \prod_{i=0}^{n-1} y_i$$

An example would be lets take a binary string $$x = 1010110110$$ the Parity function would give $$1$$ since even number of ones, otherwise $$-1$$ if odd number of ones.
Also when asking parity of functions its actually asking the parity of the bit string acquired after pluging in the all the input value of the n-bit function. For example lets take the option number 3
$$f:\{0,1^n\} \mapsto \{0,1\}$$ $$A\ constant\ function f({x}) = 1$$ Let take $$n=4$$, For it, all the possible input values $$(x)$$ a function can take are from $$0$$ to $$15$$ and for every value the functional output is $$1$$.
Hence a we need to calculate the parity of $$1111111111111111$$ (16 ones) which is $$1$$
Now my question is ,The option two ($$2$$), is it Correct? does it always give $$1$$ (even) as output ? According to the answers of the quiz, it is showing it is correct, but is it? I've run some test on n=4, n=5, unfortunately both are unsatisfying the answer here.
Thank you.

There are $$2^n$$ possible inputs. When the input bit strings are ordered lexicographically, the least significant bit of each string alternates between even and odd. There are an even number of possible inputs; half of them even and half of them odd.

$$Parity = 1^{2^n/2} * {(-1)}^{2^n/2} = 1$$

So the parity of this function is even. Option 2 is the same as option 1, only for a permutation of the arguments that exchange bit $$j$$ with the least-significant bit.

• Yeah i agree with you, only if j is the LSB of the bit string, but if it is not then? If j is just random than it will not always be 1(even) right? – Saptarshi Sahoo Jan 21 '20 at 16:44

The parity of a Boolean function, $$f$$, is given by

$$Parity(f) = \prod_{\forall x \in \{0,1\}^n} 1 - 2f(x).$$

Notice that the product ranges over all $$x \in \{0,1\}^n$$ and that

$$\{0,1\}^n = \{0,1\}^{n-1} \times \{0,1\}.$$

It is possible to factor out one bit, $$z \in \{0,1\}$$, from the product so that

$$Parity(f) = \prod_{\forall y \in \{0,1\}^{n-1}}\biggr({\prod_{\forall z \in \{0,1\}} 1 - 2f(y,z)}\biggr),$$

and, by expanding the innermost product,

$$Parity(f) = \prod_{\forall y \in \{0,1\}^{n-1}}\bigg(1 - 2f(y, {\bf 0})\bigg)\bigg(1 - 2f(y, {\bf 1})\bigg),$$

in which $$z$$ has been substituted with $${\bf 0}$$ and $${\bf 1}$$.

Now for the special case where $$f$$ is a Boolean function that returns the least significant bit of the argument, we have that, for all $$y \in \{0,1\}^{n-1}$$,

$$f(y,{\bf 0}) = {\bf 0}$$ $$f(y,{\bf 1}) = {\bf 1}.$$

Substituting these into the innermost product we find that

$$\bigg(1 - 2f(y, {\bf 0})\bigg)\bigg(1 - 2f(y, {\bf 1})\bigg) \;\; = \;\; -1$$

so that the parity function becomes

$$Parity(f) = \prod_{\forall y \in \{0,1\}^{n-1}}-1 \;\; = \;\; (-1)^{2^{n-1}}$$

which shows that the function has even parity when $$n>1$$ and odd parity when $$n=1$$.

It does not matter that we chose to factor out the least-significant bit. Choosing a bit from anywhere else, $$j$$, in the input argument would just have given a different order of the products and, since products are commutative, we could rearrange them into exactly the form given above.