26
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
23
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ (The Widgerson result was subsumed by ​ NL/poly = UL/poly .) ​ ​ ​ ​ $\endgroup$
    – user6973
    Jul 13, 2016 at 19:31
15
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thank you. Is there an intuitive explanation for what stabilizer circuits can do? I am not familiar with them. $\endgroup$
    – Aaron Sterling
    Nov 16, 2011 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$
    – Niel de Beaudrap
    Nov 16, 2011 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$
    – Joe Fitzsimons
    Nov 16, 2011 at 17:16
  • 7
    $\begingroup$ I think we need a "surprise" hierarchy, with 'falling off my chair" at the top :) $\endgroup$
    – Suresh Venkat
    Nov 17, 2011 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.