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

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.

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.