Bitwise inner product and orthogonality

Question

I am confused about the definition of bitwise inner product used in quantum algorithms. For example, bitwise inner product of 01111 with itself (in mod2) gives us 0. But they are not orthogonal to each other. How come the inner product is 0? Am I missing a point here?

Answer 1

Let $x$ and $y$ be two n-bits integers, the bitwise inner product modulo $2$, denoted $x \cdot y$, of $x$ and $y$ is given by the following sum $$x_1y_1 + \cdots + x_ny_n \;\text{mod}\,2.$$

So, the bitwise inner product of $01111$ with itself is $$0.0 + 1.1 + 1.1 + 1.1 +1.1 = 0 \; \text{mod}\,2.$$

Answer 2

• The bitwise dotproduct $x \cdot y$ tells you how many $1$ bits $x$ has in common with $y$.
• Then, $x \cdot x$ tells you how many $1$ bits $x$ has (since they are all in common).
• The bitwise dotproduct $x \cdot y \mod 2$ tells you whether the number of $1$ bits $x$ has in common with $y$ is odd ($1$) or even ($0$).
• Then, $x \cdot x \mod 2$ tells you whether $x$ has an even (0) or odd (1) number of $1$ bits.

In your example, $01111$ has four $1$ bits, so the number of bits is even and $x \cdot x \mod 2 =0$.

If you change the leading $0$ in your example to a $1$ to get $11111$, there are an odd number (five) $1$s, so you expect $x \cdot x \mod 2 = 1$. This is in fact the case:

$1\cdot1 + 1\cdot1 + 1\cdot1 + 1\cdot1 + 1\cdot1 \mod 2\\ = 5 \mod 2 \\= 1.$