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

Question

Question.

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

Equivalently: is there a logspace reduction from iterated matrix products modulo 2, to iterated products of elementary matrices (the invertible matrices which realize row transformations) mod 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^th 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 ℤ/2ℤ, 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 ⊕L) has a section on computational complexity. Towards the beginning of this section, they describe ⊕L as follows:

⊕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 definition that is probably more intuitive to non-computer-scientists. This is that ⊕L is the class of problems that reduce to simulating a polynomial-size CNOT circuit, i.e. a circuit composed entirely of NOT and CNOT gates, acting on the initial state |0...0⟩. (It is easy to show that the two definitions are equivalent, but this would require us first to explain what the usual definition 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 ⊕L as a special case of evaluating coefficients of iterated matrix products (mod 2), which is a complete problem (under logspace reductions) for ⊕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 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 ⊕L-complete problem: so a direct attack by decomposing e.g. invertible matrices as products of elementary matrices seems not to be feasible in logspace unless L = ⊕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. a text for which this is an exercise, if it is simple).

Answer 1

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'=(V',E')$ be the graph such that $V'=V\times\{0,\dots,n\}$ and $E'=\{((u,i),(v,i+1):i<n,(u,v)\in E\}\cup\{(w,w):w\in V'\}$ (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'=(s,0)$ to $t'=(t,n)$ in $G'$.

Moreover, $G'$ is acyclic, and we can explicitly define an enumeration $V'=\{w_k:k\le m\}$ such that all edges in $G'$ apart from the self-loops go from $w_k$ to $w_l$ for some $k<l$. Without loss of generality, $w_0=s'$ and $w_m=t'$. Let $M$ be the adjacency matrix of $G'$ 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'$ to $t'$ 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.