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

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

  • $\begingroup$ (The Widgerson result was subsumed by ​ NL/poly = UL/poly .) ​ ​ ​ ​ $\endgroup$
    – user6973
    Jul 13 '16 at 19:31

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.

  • 1
    $\begingroup$ Thank you. Is there an intuitive explanation for what stabilizer circuits can do? I am not familiar with them. $\endgroup$ Nov 16 '11 at 16:59
  • 7
    $\begingroup$ @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). $\endgroup$ Nov 16 '11 at 17:13
  • 6
    $\begingroup$ @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). $\endgroup$ Nov 16 '11 at 17:16
  • 7
    $\begingroup$ I think we need a "surprise" hierarchy, with 'falling off my chair" at the top :) $\endgroup$ Nov 17 '11 at 16:48

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.