Log-space reduction from Parity-L to CNOT circuits? Question.

In their paper Improved simulation of stabilizer circuits, Aaronson and Gottesman claim that simulating a CNOT circuit is &oplus;L-complete (under logspace reductions). It is clear that it is contained in &oplus;L; how does the hardness result hold?

Equivalently: is there a logspace reduction from iterated matrix products modulo&nbsp;2, to iterated products of elementary matrices (the invertible matrices which realize row transformations) mod&nbsp;2?

Details

A controlled-NOT (or CNOT) operation is a reversible boolean operation, of the form
$$
\mathsf{CNOT}_{\!h,j} (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j\,, \;\ldots\;, x_n)
\;\;=\;\;
(x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j \oplus x_h\,, \;\ldots\;, x_n)
$$
where only the j&thinsp;th&thinsp; bit is changed, and that bit is changed by adding $x_h$ modulo 2, for any distinct positions h and j. It is not hard to see, if we interpret $\mathbf x = (x_1\,, \;\ldots\;, x_n)$ as a vector over &#8484;/2&#8484;, that this corresponds to an elementary row transformation modulo 2, which we may represent by a matrix with 1s on the diagonal and a single off-diagonal position. A CNOT circuit is then a matrix product consisting of a product of some elementary matrices of this type.

The paper by Aaronson and Gottesman mentioned above (which, very incidentally to this question, is about a class of quantum circuits which can be simulated in  &oplus;L) has a section on computational complexity. Towards the beginning of this section, they describe &oplus;L as follows:


  &oplus;L [is] the class of all problems that are solvable by a
  nondeterministic logarithmic-space Turing machine, that
  accepts if and only if the total number of accepting paths
  is odd. But there is an alternate deﬁnition that is probably more intuitive to non-computer-scientists. This is
  that &oplus;L is the class of problems that reduce to simulating
  a polynomial-size CNOT circuit, i.e.&nbsp;a&nbsp;circuit composed
  entirely of NOT and CNOT gates, acting on the initial
  state |0...0&rang;. (It is easy to show that the two deﬁnitions
  are equivalent, but this would require us ﬁrst to explain
  what the usual deﬁnition means!)


The target audience of the article included a substantial number of non-computer-scientists, so the wish to elide is not unreasonable; I'm hoping someone can clarify how this equivalence holds. 

Clearly, simulating a product of such matrices can be performed in &oplus;L as a special case of evaluating coefficients of iterated matrix products (mod&nbsp;2), which is a complete problem (under logspace reductions) for &oplus;L.
Furthermore, as the CNOT matrices just perform elementary row operations, any invertible matrix can be decomposed as a product of CNOT matrices. However: it is not clear how to me how to decompose even an invertible matrix mod&nbsp;2 into a product of CNOT matrices by a logspace reduction. (Indeed, as noted by Emil Jeřábek in the comments, Gaussian elimination suffices to compute determinants mod 2, which is a &oplus;L-complete problem: so a direct attack by decomposing e.g.&nbsp;invertible matrices as products of elementary matrices seems not to be feasible in logspace unless L&nbsp;=&nbsp;&oplus;L.) To say nothing of matrix products which are not invertible. So some cleverer reduction seems to be required.

I hope someone can provide a sketch of this reduction, or a reference (e.g.&nbsp;a&nbsp;text for which this is an exercise, if it is simple).
Let us start with the $\oplus L$-complete problem of counting mod $2$ the number of paths of length $n$ from vertex $s$ to vertex $t$ in a directed graph $G=(V,E)$. We apply a couple of logspace reductions as follows.

Let $G&#39;=(V&#39;,E&#39;)$ be the graph such that $V&#39;=V\times\{0,\dots,n\}$ and $E&#39;=\{((u,i),(v,i+1):i&lt;n,(u,v)\in E\}\cup\{(w,w):w\in V&#39;\}$ (i.e., we take $n+1$ copies of $G$’s vertices, make edges go from the $i$th copy to the $(i+1)$th copy according to $G$’s edges, and add all self-loops). Then the original problem is equivalent to counting paths of length $n$ from $s&#39;=(s,0)$ to $t&#39;=(t,n)$ in $G&#39;$.

Moreover, $G&#39;$ is acyclic, and we can explicitly define an enumeration $V&#39;=\{w_k:k\le m\}$ such that all edges in $G&#39;$ apart from the self-loops go from $w_k$ to $w_l$ for some $k&lt;l$. Without loss of generality, $w_0=s&#39;$ and $w_m=t&#39;$. Let $M$ be the adjacency matrix of $G&#39;$ wrt the given enumeration. Then $M$ is an upper triangular integer matrix with $1$ on the diagonal, and the number of paths of length $n$ from $s&#39;$ to $t&#39;$ equals the top right element of $M^n$.

It is easy to see that
$$M=\prod_{j=m}^1\prod_{i=0}^{j-1}E_{i,j}(M_{i,j}),$$
where $E_{i,j}(a)$ is the elementary matrix whose only nondiagonal entry is $a$ in row $i$ and column $j$. In this way, we reduced the original problem to computing the top right element of a product of elementary matrices. In the $\oplus L$ case, the computation is modulo $2$, i.e., we consider the matrices over $\mathbb F_2$. (In this case, the elementary matrices can be only $E_{i,j}(0)=I$, which we can ignore, and $E_{i,j}(1)$, which can be simulated by a single CNOT gate, as mentioned in the question.) If we consider them as integer matrices, we get a $\#L$-complete problem, and if we consider them modulo $k$, we get a $\mathrm{Mod}_kL$-complete problem.