Consider a standard quadratic form:
$$f(x) = x^TAx$$
where $A \in \mathbb{R}^{n\times n}$ and $x \in \{0,1\}^n \subset \mathbb{R}^n$. In this function, all operations are carried out over $\mathbb{R}$. Evaluating this function will require $O(n^2)$ operations.
Now it turns out that the $x$ is generated via a linear operation over $GF(2)$.
$$x = Gx'$$
where $G \in \mathbb{F}_2^{n\times m}$, and $x' \in \mathbb{F}_2^{m}$, and $m \ll n$. We extend $x$ to a vector over the reals by equating the additive and multiplicative identities in the natural way.
If we exploit this in the quadratic form, we have
$$f(x') = (x')^TG^TAGx'$$
Assume $G$ and $A$ are given a-priori and any pre-processing of them is free. Since there are operations over different fields, it's not clear if we can compute $f(x')$ in $O(m^2)$ operations, but I am wondering if it is possible.
Thank you for your suggestions!