# Bitwise inner product and orthogonality

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?

• The problem is that the space of bit strings is vector space over a finite field. (In particular, it is a field of characteristic 2.) In such vector fields, there are many "intuitions" from vector fields over $\mathbb{R}$ or $\mathbb{C}$ that no longer apply. You've identified one of them. – luftbahnfahrer Aug 16 '18 at 20:55
• @luftbahnfahrer So the interpretation of the notion of orthogonality of a vector space over strings of finite length is different than that of real vector spaces? Even the notion of vector changes then. That means if x and y are two binary strings, their bitwise inner product being 0 doesn’t intuitively refer to orthogonality in the real vector space sense. – acevik Aug 17 '18 at 10:13
• Sorry for the (very) late reply... This does not change the notion of vectors in a vector space. There is just no notion of "orthogonality" in this space since there is no inner product. In order for a vector space over a field F to have an inner product, the field F needs to be ordered. – luftbahnfahrer Sep 5 '18 at 19:43
• The definition of a vector space does not mention anything about inner products (see, e.g. mathworld.wolfram.com/VectorSpace.html). Your space of bitstrings is the vector space over the field of two elements {0,1}. In order to a vector space over a field $F$ to have an inner product, the field $F$ must be ordered. Finite fields cannot be ordered. – luftbahnfahrer Sep 5 '18 at 19:48
• I apologise as well for my late reply. The situation got more complicated now. Why is it that finite fields cannot be ordered? Every set can be well-ordered by the Well-Ordering Theorem (i.e. equivalent form of the Axiom of Choice). – acevik Oct 4 '18 at 8:59

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