1
$\begingroup$

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ – Saptarshi Sahoo Jan 21 '20 at 16:44
1
$\begingroup$

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.

$\endgroup$

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.