Rings or algebras with many nilpotent elements and efficient computation

Question

Crossposted from quantum.SE where comment appears to suggest that solving modulo 2 might be possible.

Searching the web for '"quantum computer" nilpotent' returns many results, so maybe the question is ontopic for this site.

Can a quantum computer solve the following mathematical problem:

This is related to an open problem, so likely the answer is negative.

The problem is Cycle Enumeration using Nilpotent Adjacency Matrices with Algorithm Runtime Comparisons pp 2-3

Is there commutative ring or commutative algebra $R$ with the following properties:

1. There are $n$ nilpotent elements $a_i$ satisfying $a_i^2=0$
2. $a_1 a_2 \cdots a_n \ne 0$.
3. Computation in $R$ is efficient: for an $n$ by $n$ matrix $M$ with entries zero and $a_i$, for natural $m$ we can compute $M^m$ in time polynomial in $nm$.

If we omit the efficiency constraint, the answer is easy:

Take $R=K[a_1,a_2,...a_n]/(a_1^2,a_2^2,...a_n^2)$ for any ring $K$.

If we omit commutativity, there are solutions with matrices.

Answer 1

Let's consider a commutative $R$-algebra satisfying assumptions 1 and 2 in the question, where $R$ is a commutative ring. Let's start with a few observations:

1. For every $U \subseteq \{1,...,n\}$, we have $a_U := \prod_{u \in U}a_u \neq 0$. Otherwise, $\prod_{u=1}^n a_u = 0$, which contradicts assumption 2 in the question. (We set $a_\emptyset = 1$ by convention).

2. For every $U, V \subseteq \{1,...,n\}$, if $a_U = a_V$ then necessarily $U = V$. To see this, assume that $a_U = a_V$ and that $U \neq V$. Without loss of generality assume $U \not\subseteq V$ and let $x \in U \backslash V$. Then $0 = a_x^2a_{U \backslash\{x\}}= a_{V \sqcup \{x\}}\neq 0$. Conclude by contradiction with point 1 above.

For each $U \subseteq V$ write $q_U^V$ for the quotient map of $R$-modules $q_U^V: R a_U \rightarrow R a_V$ defined by $x \mapsto x a_{V \backslash U}$. Write $K := R a_{\{1,...,n\}})$ and $q_U := q_U^{\{1,...,n\}}: R a_U \rightarrow K$. We can now prove an interesting fact about $R$-linear combinations of the $a_U$ elements, namely that if for some coefficients $x_U \in R$ we have $\sum_{U \subseteq \{1,...,n\}} x_U a_U = 0$ then for every $V \subseteq \{1,...,n\}$ we also have: $$ \sum_{U \subseteq V} q_U^{U\sqcup \overline{V}}\!\!\left(x_U\right) a_{U \sqcup \overline{V}} = \left(\sum_{U \subseteq \{1,...,n\}} x_U a_U\right)a_{\overline{V}} = 0 $$ where we have written $\overline{V} := \{1,...,n\} \backslash V$. In particular, if $\mathcal{U}\subset \mathcal{P}$ is an antichain (i.e. if for all $U, V \in \mathcal{U}$ we have that $U \subseteq V$ implies $U=V$), then the elements $(a_U)_{U \in \mathcal{U}}$ are linearly independent over some suitable (non-trivial) quotient of $R$. Because there are antichains $\mathcal{U}$ with size exponential in $n$, e.g. those formed by subsets $U$ with size $\frac{n}{2}$ for even $n$, this is an indication that computation in the $R$-algebra is not going to be efficient over some suitable (non-trivial) quotient of $R$.

PS: I think this last argument can be made formal by defining a surjective ring homomorphism $f: S \rightarrow Q$ from the sub-ring $S$ spanned by $R$-linear combinations of the elements $a_U$ for all $U \subseteq \{1,...,n\}$ to a suitable quotient ring $Q$ of $K[a_1,...,a_n]/(a_1^2,...,a_n^2)$ as follows: $$ f\left(\sum_{U \subseteq \{1,...,n\}} x_U a_U\right) := \sum_{U \subseteq \{1,...,n\}} q_U(x_U) a_U $$ I have not worked out the details yet, I might do so in the future if of interest.