Motivated by the quantum algorithm in \cite{MN05} for testing commutativity of black-box groups, we study the following problem: Given a black-box finite ring $R=\angle{r_1,\cdots,r_k}$ where $\{r_1,r_2,\cdots,r_k\}$ is an additive generating set for $R$ and a multilinear polynomial $f(x_1,\cdots,x_m)$ over $R$ also accessed as a black-box function $f:R^m\rightarrow R$ (where we ...
more >>>