1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.