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

CC BY-SA 3.0
2011-11-16T16:59:29.517Z
Thank you.  Is there an intuitive explanation for what stabilizer circuits can do? I am not familiar with them.
Aaron Sterling
CC BY-SA 3.0
2011-11-16T17:13:32.990Z
@AaronSterling: Stabilizer circuits are a restricted model of quantum computation; they are generated by CNOT gates (reversibly computing the XOR of two input bits), and two gates which do not have immediate analogues in classical computation. Acting on "classical" inputs (so-called computational basis states), or on inputs which are only mildly more general than "classical" inputs, these may be simulated efficiently in terms of symplectic transformations modulo 2, despite being quantum mechanical in flavour (and only just slightly shy of being capable of universality for quantum computation).
Niel de Beaudrap
CC BY-SA 3.0
2011-11-16T17:16:21.400Z
@AaronSterling: They are a subset of all quantum circuits which include CNOTS (essentially XOR + fanout) as well as a number of quantum gates which can create equal superpositions (e.g. Hadamard gates). If you are familair with quantum computation, then the circuits correspond to those operators which map Pauli operators to other Pauli operators under conjugation, acting upon classical input (or input which can be obtained from classical input via another Clifford group circuit).
Joe Fitzsimons
CC BY-SA 3.0
2011-11-17T16:48:03.850Z
I think we need a "surprise" hierarchy, with 'falling off my chair" at the top :)
Suresh Venkat
CC BY-SA 3.0
2011-11-16T16:27:55.273Z
2011-11-16T16:41:37.100Z
2011-11-16T16:41:37.100Z
Joe Fitzsimons
<p>Wigderson <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W94/proc.pdf">proved</a> 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&#39;$ in $\oplus L/poly$. Take the $\oplus L$ language of instance-advice pairs $S = \{(x,a)~|~M&#39;(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$.) </p>

<p>I think that would be surprising: nondeterministic branching programs would be equivalent to deterministic branching programs (up to polynomial factors).</p>

CC BY-SA 3.0
2011-11-16T19:34:24.297Z
2011-11-16T19:34:24.297Z
Ryan Williams
<p>Shiva Kintali has just announced a (cool!) result that <a href="http://kintali.wordpress.com/2011/11/16/hardness-of-graph-isomorphism-of-bounded-treewidth-graphs/#comments" rel="nofollow noreferrer">graph isomorphism for bounded treewidth graphs of width $\geq 4$ is $\oplus L$-hard</a>.  Informally, my question is, "How hard is that?"</p>

<p>We know that nonuniformly $NL \subseteq \oplus L$, see the answers to <a href="https://cstheory.stackexchange.com/q/7937/30">this question</a>.  We also know that it is unlikely that $\oplus L = P$, see the answers to <a href="https://cstheory.stackexchange.com/q/175/30">this question</a>.  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.</p>

<blockquote>
  <p>What are the consequences of $L=\oplus L$?</p>
</blockquote>

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

<cc.complexity-theory><complexity-classes><logspace>
What are the consequences of $L = \oplus L$?
Aaron Sterling
# What are the consequences of $L = \oplus L$?

(Asked by: username_0 on 2011-11-16)

Shiva Kintali has just announced a (cool!) result that [graph isomorphism for bounded treewidth graphs of width $\geq 4$ is $\oplus L$-hard](http://kintali.wordpress.com/2011/11/16/hardness-of-graph-isomorphism-of-bounded-treewidth-graphs/#comments). Informally, my question is, "How hard is that?"

We know that nonuniformly $NL \subseteq \oplus L$, see the answers to [this question](https://cstheory.stackexchange.com/q/7937/30). We also know that it is unlikely that $\oplus L = P$, see the answers to [this question](https://cstheory.stackexchange.com/q/175/30). 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.

**Tags:** cc.complexity-theory, complexity-classes, logspace

---

## 2 answers

### Answer by username_4 on 2011-11-16. Score: 23 | Accepted answer

Wigderson [proved](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W94/proc.pdf) 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$.)

I think that would be surprising: nondeterministic branching programs would be equivalent to deterministic branching programs (up to polynomial factors).


---

### Answer by username_1 on 2011-11-16. Score: 15

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.

> **Comments:**
> **username_0**: Thank you.  Is there an intuitive explanation for what stabilizer circuits can do? I am not familiar with them.  
> **username_2**: @AaronSterling: Stabilizer circuits are a restricted model of quantum computation; they are generated by CNOT gates (reversibly computing the XOR of two input bits), and two gates which do not have immediate analogues in classical computation. Acting on "classical" inputs (so-called computational basis states), or on inputs which are only mildly more general than "classical" inputs, these may be simulated efficiently in terms of symplectic transformations modulo 2, despite being quantum mechanical in flavour (and only just slightly shy of being capable of universality for quantum computation).  
> **username_1**: @AaronSterling: They are a subset of all quantum circuits which include CNOTS (essentially XOR + fanout) as well as a number of quantum gates which can create equal superpositions (e.g. Hadamard gates). If you are familair with quantum computation, then the circuits correspond to those operators which map Pauli operators to other Pauli operators under conjugation, acting upon classical input (or input which can be obtained from classical input via another Clifford group circuit).  
> **username_3**: I think we need a "surprise" hierarchy, with 'falling off my chair" at the top :)  

---

