Rings or algebras with many nilpotent elements and efficient computation 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:

*

*There are $n$ nilpotent elements $a_i$ satisfying $a_i^2=0$

*$a_1 a_2 \cdots a_n \ne 0$.

*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.
 A: 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:

*

*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).


*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.
