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?

  • 1
    $\begingroup$ 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. $\endgroup$ – luftbahnfahrer Aug 16 '18 at 20:55
  • $\begingroup$ @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. $\endgroup$ – acevik Aug 17 '18 at 10:13
  • $\begingroup$ 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. $\endgroup$ – luftbahnfahrer Sep 5 '18 at 19:43
  • $\begingroup$ 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. $\endgroup$ – luftbahnfahrer Sep 5 '18 at 19:48
  • $\begingroup$ 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). $\endgroup$ – 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.$$

  • $\begingroup$ That does not answer his question. $\endgroup$ – Rab Aug 16 '18 at 12:33
  • $\begingroup$ @Rab: the main question of the OP was "How come the inner product is 0?". So, it answers the question. $\endgroup$ – Anthony Bordg Aug 16 '18 at 12:51
  • $\begingroup$ But the inner product of a binary string with itself shouldn’t give 0 unless the string is all 0’s. For this example, 01111 cannot be orthogonal to itself. But the result of the inner product is still 0. Does that mean 01111 is orthogonal to itself? Or is there a special way to treat binary strings as vectors? $\endgroup$ – acevik Aug 16 '18 at 14:21
  • $\begingroup$ @acevik: don't forget that it's the bitwise inner product "modulo 2", as far as I know it's only a convenient notation for some powers of (-1) in some quantum algorithms (hence the mod 2 operation). In particular, it does not behave anymore like an inner product on a vector space, and in this case orthogonality simply does not make sense. $\endgroup$ – Anthony Bordg Aug 16 '18 at 15:18

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.