14
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ I suppose computing determinants mod $2$ is also ⊕L-complete, hence Gaussian elimination mod $2$ is ⊕L-hard. $\endgroup$ – Emil Jeřábek Feb 7 '12 at 17:11
  • 1
    $\begingroup$ @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. $\endgroup$ – Niel de Beaudrap Feb 7 '12 at 20:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Feb 8 '12 at 11:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Niel de Beaudrap Feb 8 '12 at 11:45
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Feb 8 '12 at 12:35
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I mean, it is $\#L$-complete for elementary matrices with nonnegative integer coefficients. With arbitrary integers, it is DET-complete. $\endgroup$ – Emil Jeřábek Feb 10 '12 at 14:11
  • $\begingroup$ 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! $\endgroup$ – Niel de Beaudrap Feb 11 '12 at 17:16
  • $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Feb 14 '12 at 11:04
  • $\begingroup$ I suppose that from focusing on the ideas in the paper Stucture and importance of Logspace-MOD classes 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. $\endgroup$ – Niel de Beaudrap Feb 14 '12 at 12:45

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.