# What are the consequences of $L = \oplus L$?

Shiva Kintali has just announced a (cool!) result that graph isomorphism for bounded treewidth graphs of width $\geq 4$ is $\oplus L$-hard. Informally, my question is, "How hard is that?"

We know that nonuniformly $NL \subseteq \oplus L$, see the answers to this question. We also know that it is unlikely that $\oplus L = P$, see the answers to this question. How surprising would it be if $L=\oplus L$? I have heard many people say that $L=NL$ would not be shocking the way $P=NP$ would.

What are the consequences of $L=\oplus L$?

Definition: $\oplus L$ is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero number of acceptance paths), and which is further restricted to work in logarithmic space.

Wigderson proved that $NL/poly \subseteq \oplus L/poly$. By standard arguments, $L = \oplus L$ would imply $L/poly = NL/poly$. (Take a machine $M$ in $NL/poly$. It has an equivalent machine $M'$ in $\oplus L/poly$. Take the $\oplus L$ language of instance-advice pairs $S = \{(x,a)~|~M'(x,a)~\textrm{accepts}\}$. If this language is in $L$, then by hardcoding the appropriate advice $a$ we get an $L/poly$ machine equivalent to $M$.)
Well if $L=\oplus L$ then simulation of stabilizer circuits is in $L$, since Aaronson and Gottesman (Physical Review A 70, 052328) proved such simulation is complete for $\oplus L$ under log space reductions, or more weakly that simulating CNOT networks is in $L$. Equivalently, if the simulation of such circuits is in $L$ then $L = \oplus L$. Personally, I would find this surprising, but not in the fall off my chair way I would find $P=NP$ surprising.