<p>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.</p>

<p>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;$.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2012-02-10T14:11:43.880Z
I mean, it is $\#L$-complete for elementary matrices with *nonnegative* integer coefficients. With arbitrary integers, it is DET-complete.
Emil Jeřábek
CC BY-SA 3.0
2012-02-11T17:16:29.480Z
The following is probably standard, but I hadn't explicitly seen it before: to show that finding the number of paths of length precisely _n_ in a (possibly cyclic) digraph is **⊕L**-complete, note that this amounts to computing coefficients of some power of an arbitrary matrix over $\mathbb F_2$, which _is_ **⊕L**-complete. This answer is then essentially as a reduction from matrix powering (using a standard construction of M as a block matrix consisting only of copies of the arbitrary adjacency matrix of G in the upper off-diagonal blocks, and 1 on the diagonal) to CNOT circuits. Nice answer!
Niel de Beaudrap
CC BY-SA 3.0
2012-02-14T11:04:15.947Z
You don’t need to go through matrix powering, whose ⊕L-completeness is harder to prove. ⊕L is *defined* by counting mod 2 the accepting paths of a nondeterministic logspace Turing machine (with polynomial time clock, I presume, so that the number is guaranteed to be finite), which is the same as counting paths in the configuration graph of the machine (it is easy to arrange that the paths all end in the same configuration, and that the paths have the same length, by making the machine go into a loop until its clock expires and then enter a fixed accepting state).
Emil Jeřábek
CC BY-SA 3.0
2012-02-14T12:45:59.197Z
I suppose that from focusing on the ideas in the paper [Stucture and importance of Logspace-MOD classes](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.5193) by Buntrock _et al._, I've become much more accustomed to thinking in terms of number of paths of _arbitrary_ length in an _acyclic_ digraph, and the **DET**-like problems such as matrix products and powers which are naturally connected to it.
Niel de Beaudrap
CC BY-SA 3.0
2012-02-10T13:55:03.717Z
2012-02-10T13:55:03.717Z
Emil Jeřábek
<h2>Question.</h2>

<p>In their paper <a href="http://arxiv.org/pdf/quant-ph/0406196" rel="nofollow noreferrer"><em>Improved simulation of stabilizer circuits</em></a>, Aaronson and Gottesman claim that simulating a CNOT circuit is <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:Symbols#parityl" rel="nofollow noreferrer"><strong>&oplus;L</strong></a>-complete (under logspace reductions). It is clear that it is contained in <strong>&oplus;L</strong>; how does the hardness result hold?</p>

<p><em>Equivalently:</em> 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?</p>

<h2>Details</h2>

<p>A <em>controlled-NOT</em> (or <em>CNOT</em>) 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 <em>j</em><sup>&thinsp;th&thinsp;</sup> bit is changed, and that bit is changed by adding $x_h$ modulo 2, for any distinct positions <em>h</em> and <em>j</em>. 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 <em>CNOT circuit</em> is then a matrix product consisting of a product of some elementary matrices of this type.</p>

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

<blockquote>
  <p><strong>&oplus;L</strong> [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 <strong>&oplus;L</strong> is the class of problems that reduce to simulating
  a polynomial-size CNOT circuit, <em>i.e.</em>&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!)</p>
</blockquote>

<p>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. </p>

<p>Clearly, simulating a product of such matrices can be performed in <strong>&oplus;L</strong> as a special case of evaluating coefficients of iterated matrix products (mod&nbsp;2), which is a complete problem (under logspace reductions) for <strong>&oplus;L</strong>.
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 <em>by a logspace reduction</em>. (Indeed, as noted by Emil Jeřábek in the comments, Gaussian elimination suffices to compute determinants mod 2, which is a <strong>&oplus;L</strong>-complete problem: so a direct attack by decomposing <em>e.g.</em>&nbsp;invertible matrices as products of elementary matrices seems not to be feasible in logspace unless <a href="https://cstheory.stackexchange.com/q/8991/248"><strong>L</strong>&nbsp;=&nbsp;<strong>&oplus;L</strong></a>.) To say nothing of matrix products which are not invertible. So some cleverer reduction seems to be required.</p>

<p>I hope someone can provide a sketch of this reduction, or a reference (<em>e.g.</em>&nbsp;a&nbsp;text for which this is an exercise, if it is simple).</p>

CC BY-SA 3.0
2012-02-07T17:11:05.497Z
I suppose computing determinants mod $2$ is also ⊕L-complete, hence Gaussian elimination mod $2$ is ⊕L-hard.
Emil Jeřábek
CC BY-SA 3.0
2012-02-07T20:22:42.480Z
@EmilJeřábek: I'm thinking about your remark, and I'm trying to see if this immediately implies that simulating CNOT circuits is _not_ complete for **⊕L** unless **L** = **⊕L**. (Consider a product of one matrix, or a product of a single matrix with the identity matrix!) This seems almost too easy; am I missing something? I suppose perhaps it only rules out many-to-one reductions.
Niel de Beaudrap
CC BY-SA 3.0
2012-02-08T11:34:40.597Z
I don’t think it’s that easy. ⊕L is a class of decision problems, whereas matrix multiplication over F_2 is a function problem. The ⊕L version of matrix multiplication is to ask for a particular bit of the result (say, the top left entry of the matrix). Can there be a logspace algorithm that takes a sequence of matrices and produces a sequence of elementary matrices so that the products of both sequences have the same top left element? This is much weaker than true Gaussian elimination. Actually, the Aaronson and Gottesman claim sounds plausible to me, though I’m not sure how to prove it.
Emil Jeřábek
CC BY-SA 3.0
2012-02-08T11:45:18.443Z
@EmilJeřábek: I'm thinking about how most of the **⊕L** decision problems are based off of verifying individual coefficients of problems which are natural for **DET** (it is common to speak of function problems as being **⊕L**-complete, however an abuse of terminology that is); and that my intuition for matrix products is that it is sufficiently complicated that it is difficult to arrange ad-hoc, for any _single_ coefficient, that two matrix products should be equal for that coefficient in such a manner that you can't be fairly certain that all of the other coefficients will agree as well.
Niel de Beaudrap
CC BY-SA 3.0
2012-02-08T12:35:06.490Z
I got it: counting accepting paths of a logspace machine amounts to counting paths in an *acyclic* graph, which can be represented by multiplication of upper triangular matrices with 1 on the diagonal. The latter can be easily expressed as a product of elementary matrices in an explicit way, without Gaussian elimination.
Emil Jeřábek
CC BY-SA 3.0
2012-02-08T17:36:47.297Z
@EmilJeřábek: I think I see how one can get at the number of paths mod 2 using multiple powers of such an adjacency matrix — corresponding to a directed graph with loops, so technically not acyclic, but almost so — and accounting for binomial coefficients (asuming that these or the necessary function depending on them is computable in logspace). If you or someone else were to write an answer in the next few days based on that, I would accept it. Otherwise, I'll write up the sketch myself as a self-answer.
Niel de Beaudrap
CC BY-SA 3.0
2012-02-10T14:02:00.883Z
OK, done. [Ignore this, comments must be at least 15 characters long.]
Emil Jeřábek
<cc.complexity-theory><counting-complexity><linear-algebra><logspace>
Log-space reduction from Parity-L to CNOT circuits?
Niel de Beaudrap
# Log-space reduction from Parity-L to CNOT circuits?

(Asked by: username_0 on 2012-02-07)

## Question.

In their paper [*Improved simulation of stabilizer circuits*](http://arxiv.org/pdf/quant-ph/0406196), Aaronson and Gottesman claim that simulating a CNOT circuit is [**⊕L**](http://qwiki.stanford.edu/index.php/Complexity_Zoo:Symbols#parityl)-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 deﬁnition 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 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 **⊕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**](https://cstheory.stackexchange.com/q/8991/248).) 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).

**Tags:** cc.complexity-theory, counting-complexity, linear-algebra, logspace
> **Comments:**
> **username_1**: I suppose computing determinants mod $2$ is also ⊕L-complete, hence Gaussian elimination mod $2$ is ⊕L-hard.  
> **username_0**: @EmilJeřábek: I'm thinking about your remark, and I'm trying to see if this immediately implies that simulating CNOT circuits is _not_ complete for **⊕L** unless **L** = **⊕L**. (Consider a product of one matrix, or a product of a single matrix with the identity matrix!) This seems almost too easy; am I missing something? I suppose perhaps it only rules out many-to-one reductions.  
> **username_1**: I don’t think it’s that easy. ⊕L is a class of decision problems, whereas matrix multiplication over F_2 is a function problem. The ⊕L version of matrix multiplication is to ask for a particular bit of the result (say, the top left entry of the matrix). Can there be a logspace algorithm that takes a sequence of matrices and produces a sequence of elementary matrices so that the products of both sequences have the same top left element? This is much weaker than true Gaussian elimination. Actually, the Aaronson and Gottesman claim sounds plausible to me, though I’m not sure how to prove it.  
> **username_0**: @EmilJeřábek: I'm thinking about how most of the **⊕L** decision problems are based off of verifying individual coefficients of problems which are natural for **DET** (it is common to speak of function problems as being **⊕L**-complete, however an abuse of terminology that is); and that my intuition for matrix products is that it is sufficiently complicated that it is difficult to arrange ad-hoc, for any _single_ coefficient, that two matrix products should be equal for that coefficient in such a manner that you can't be fairly certain that all of the other coefficients will agree as well.  
> **username_1**: I got it: counting accepting paths of a logspace machine amounts to counting paths in an *acyclic* graph, which can be represented by multiplication of upper triangular matrices with 1 on the diagonal. The latter can be easily expressed as a product of elementary matrices in an explicit way, without Gaussian elimination.  
> **username_0**: @EmilJeřábek: I think I see how one can get at the number of paths mod 2 using multiple powers of such an adjacency matrix — corresponding to a directed graph with loops, so technically not acyclic, but almost so — and accounting for binomial coefficients (asuming that these or the necessary function depending on them is computable in logspace). If you or someone else were to write an answer in the next few days based on that, I would accept it. Otherwise, I'll write up the sketch myself as a self-answer.  
> **username_1**: OK, done. [Ignore this, comments must be at least 15 characters long.]  

---

## 1 answers

### Answer by username_1 on 2012-02-10. Score: 10 | Accepted answer

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

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

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.

> **Comments:**
> **username_1**: I mean, it is $\#L$-complete for elementary matrices with *nonnegative* integer coefficients. With arbitrary integers, it is DET-complete.  
> **username_0**: The following is probably standard, but I hadn't explicitly seen it before: to show that finding the number of paths of length precisely _n_ in a (possibly cyclic) digraph is **⊕L**-complete, note that this amounts to computing coefficients of some power of an arbitrary matrix over $\mathbb F_2$, which _is_ **⊕L**-complete. This answer is then essentially as a reduction from matrix powering (using a standard construction of M as a block matrix consisting only of copies of the arbitrary adjacency matrix of G in the upper off-diagonal blocks, and 1 on the diagonal) to CNOT circuits. Nice answer!  
> **username_1**: You don’t need to go through matrix powering, whose ⊕L-completeness is harder to prove. ⊕L is *defined* by counting mod 2 the accepting paths of a nondeterministic logspace Turing machine (with polynomial time clock, I presume, so that the number is guaranteed to be finite), which is the same as counting paths in the configuration graph of the machine (it is easy to arrange that the paths all end in the same configuration, and that the paths have the same length, by making the machine go into a loop until its clock expires and then enter a fixed accepting state).  
> **username_0**: I suppose that from focusing on the ideas in the paper [Stucture and importance of Logspace-MOD classes](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.5193) by Buntrock _et al._, I've become much more accustomed to thinking in terms of number of paths of _arbitrary_ length in an _acyclic_ digraph, and the **DET**-like problems such as matrix products and powers which are naturally connected to it.  

---

