Can the Euclidean distance function be computed using only XOR's

Question

The Eulidean distance function $d$ of $x$ and $y$ is given by:

$ d(x,y)=\sqrt{x^2-y^2} $

Let us assume that $x$ and $y$ are fixed-point numbers, or $x,y$ are element of some subfield $f_n$ of $F_p$. We could even assume that $x,y$ have precision $n$ decimal digits. Any facilitating representations of rational or real values $x,y$ that carries "enough" information is good. $x,y$ could also be assumed to be only positive.

Can the Euclidean distance function be computed using only XOR's? If this cannot be achieved, what other boolean functions would be needed?

Answer 1

No. It's not possible. Any function that can be computed using just XOR's is affine over $GF(2)$. However, the Euclidean distance is not affine over $GF(2)$, so there is no hope of representing it with just XOR's.

Recall that $GF(2)$ denotes the finite field with two elements; you might also see it indicated by $\mathbb{F}_2$, and it is the field $(\{0,1\},\oplus,\times)$, where $\oplus$ represents the XOR operation (i.e., addition modulo two) and $\times$ represents the AND operation (i.e., multiplication modulo two).

Recall that a function $f$ is linear if it can be expressed as a linear map, i.e., $f(x+y)=f(x)+f(y)$ holds. More specifically, suppose we have a function $f:GF(2)^n \to GF(2)^m$ that maps from a vector space over $GF(2)$ to a vector space over $GF(2)$. Then $f$ is linear if $f(x \oplus y)=f(x) \oplus f(y)$ for all $x,y$, where $\oplus$ denotes element-wise XOR. Equivalently, $f$ is linear if there is a $m\times n$ matrix $M$ whose elements are in $GF(2)$ (i.e., all of whose elements are 0 or 1), such that $f(x) = Mx$.

A function $g$ is affine if it is of the form $g(x)=f(x)+c$, where $f$ is linear and $c$ is an arbitrary constant. In our case, $g$ is affine if there is a $m\times n$ matrix $M$ whose elements are in $GF(2)$ (i.e., all of whose elements are 0 or 1) and a constant $c \in GF(2)^n$, such that $g(x) = Mx+c$. See, e.g., this Wikipedia article for more.

The XOR operation is linear. Also, because the set of $GF(2)$-affine transformations is closed under composition (this follows because $(\{0,1\},\oplus)$ is a group), it is easy to see that any circuit built solely out of XOR's must be $GF(2)$-affine. (Why affine, rather than linear? Because a circuit can contain constants: it can take an input and XOR it with the constant 1. That makes it affine, rather than linear.)

Now it is easy to verify that the Euclidean distance is not $GF(2)$-affine, just by looking at a few values: e.g., you can look at $d(0,0)$, $d(0,1)$, $d(1,0)$, $d(1,1)$. If $d$ were affine, we would have the relationship

$$d(0,0) \oplus d(0,1) \oplus d(1,0) \oplus d(1,1) = 0.$$

Since this relationship does not in fact hold, $d$ is not $GF(2)$-affine.

And since $d$ is not an affine function of its inputs, this means it cannot be expressed using only XORs.

Certainly NAND gates would be sufficient, as they are universal. It could also be expressed using just XORs and ANDs, as those two are also universal. There are many other options.