<p>Well, evaluating Clifford group quantum circuits is complete under log space reductions for parity-L (See Aaronson and Gottesman, Physical Review A 70:052328, 2004). Now, let's use some tricks from measurement based quantum computation:</p>

<p>Evaluating clifford group circuits is in QNC^1. This is simply because there is no partial time ordering on measurements, and correction operations are simply calculated by parity of some subset of measurement results.</p>

<p>This would seem to imply that L^{QNC^1} contains P.</p>

CC BY-SA 2.5
2010-08-17T17:53:13.923Z
2010-08-17T17:53:13.923Z
Joe Fitzsimons
<p>parity-$L$ is in <a href="http://en.wikipedia.org/wiki/NC_%28complexity%29">$NC^2$</a> and parity-$L=P$ would mean that $P$ can be simulated in parallel $\log^2$ time or in $\log^2$ space (since $NC^2$ is in $DSPACE(log^2 n)$)</p>

CC BY-SA 3.0
2013-02-12T22:26:44.480Z
@Niel I love that corollary! :)
Tayfun Pay
CC BY-SA 2.5
2010-08-18T10:05:35.283Z
Corollary: if Parity-L=P, then P≠PSPACE.
Niel de Beaudrap
CC BY-SA 3.0
2010-08-17T18:33:04.137Z
2013-02-12T17:51:24.240Z
2013-02-12T17:51:24.240Z
Noam
<p><a href="https://complexityzoo.net/Complexity_Zoo:Symbols#parityl" rel="nofollow noreferrer">Parity-L</a> is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of &quot;acceptance&quot; paths (rather than a zero or non-zero number of acceptance paths), and which is further restricted to work in logarithmic space. Solving a linear system of equations over ℤ<sub>2</sub> is a complete problem for Parity-L, and so Parity-L is contained in P.</p>
<p>What other complexity class relations would be known, if Parity-L and P were equal?</p>

<cc.complexity-theory><complexity-classes><conditional-results>
What are the consequences of Parity-L = P?
Niel de Beaudrap
# What are the consequences of Parity-L = P?

(Asked by: username_0 on 2010-08-17)

[Parity-L](https://complexityzoo.net/Complexity_Zoo:Symbols#parityl) 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. Solving a linear system of equations over ℤ2 is a complete problem for Parity-L, and so Parity-L is contained in P.

What other complexity class relations would be known, if Parity-L and P were equal?

**Tags:** cc.complexity-theory, complexity-classes, conditional-results

---

## 2 answers

### Answer by username_2 on 2010-08-17. Score: 29 | Accepted answer

parity-$L$ is in [$NC^2$](http://en.wikipedia.org/wiki/NC_%28complexity%29) and parity-$L=P$ would mean that $P$ can be simulated in parallel $\log^2$ time or in $\log^2$ space (since $NC^2$ is in $DSPACE(log^2 n)$)

> **Comments:**
> **username_0**: Corollary: if Parity-L=P, then P≠PSPACE.  
> **username_3**: @Niel I love that corollary! :)  

---

### Answer by username_1 on 2010-08-17. Score: 15

Well, evaluating Clifford group quantum circuits is complete under log space reductions for parity-L (See Aaronson and Gottesman, Physical Review A 70:052328, 2004). Now, let's use some tricks from measurement based quantum computation:

Evaluating clifford group circuits is in QNC^1. This is simply because there is no partial time ordering on measurements, and correction operations are simply calculated by parity of some subset of measurement results.

This would seem to imply that L^{QNC^1} contains P.


---

