¿Cuáles son las consecuencias de ?

Shiva Kintali acaba de anunciar un resultado (¡genial!) De que el isomorfismo gráfico para gráficos de ancho de árbol acotado de ancho es -hard $\geq 4$ $\oplus L$ . Informalmente, mi pregunta es: "¿Qué tan difícil es eso?"

Sabemos que no uniformemente , vea las respuestas a esta pregunta . También sabemos que es poco probable que , vea las respuestas a esta pregunta . ¿Qué tan sorprendente sería si ? He escuchado a muchas personas decir que no sería impactante como lo haría . $NL \subseteq \oplus L$ $\oplus L = P$ $L=\oplus L$ $L=NL$ $P=NP$

¿Cuáles son las consecuencias de ? $L=\oplus L$

Definición: es el conjunto de lenguajes reconocidos por una máquina de Turing no determinista que solo puede distinguir entre un número par o un número impar de rutas de "aceptación" (en lugar de un número cero o no cero de rutas de aceptación), y que se restringe aún más al trabajo en el espacio logarítmico. $\oplus L$

cc.complexity-theory complexity-classes logspace Aaron Sterling
fuente

Respuestas:

Wigderson demostró que . Por argumentos estándar, implicaría . (Tome una máquina en . Tiene una máquina equivalente en . Tome el lenguaje de pares de instancias-consejos . Si este lenguaje está en , codificando los consejos apropiados obtenemos una máquina equivalente a ). $NL/poly \subseteq \oplus L/poly$ $L = \oplus L$ $L/poly = NL/poly$ $M$ $NL/poly$ $M'$ $\oplus L/poly$ $\oplus L$ $S = \{(x,a)~|~M'(x,a)~\textrm{accepts}\}$ $L$ $a$ $L/poly$ $M$

Creo que sería sorprendente: los programas de ramificación no deterministas serían equivalentes a los programas de ramificación deterministas (hasta factores polinómicos).

Ryan Williams
fuente

(El resultado Widgerson fue subsumido por NL / poli = UL / poli .)

Bueno, si entonces la simulación de los circuitos estabilizadores está en , ya que Aaronson y Gottesman (Physical Review A 70, 052328) demostraron que dicha simulación está completa para con reducciones de espacio logarítmico, o más débilmente que simular redes CNOT. en . De manera equivalente, si la simulación de este tipo de circuitos se encuentra en entonces . Personalmente, esto me resultaría sorprendente, pero no en la caída de mi silla me resultaría sorprendente . $L=\oplus L$ $L$ $\oplus L$ $L$ $L$ $L = \oplus L$ $P=NP$

Joe Fitzsimons
fuente

Gracias. ¿Existe una explicación intuitiva de lo que pueden hacer los circuitos estabilizadores? No estoy familiarizado con ellos.

Aaron Sterling

@AaronSterling: los circuitos estabilizadores son un modelo restringido de computación cuántica; son generados por puertas CNOT (calculando reversiblemente el XOR de dos bits de entrada) y dos puertas que no tienen análogos inmediatos en la computación clásica. Actuando sobre entradas "clásicas" (los llamados estados de base computacional), o sobre entradas que son ligeramente más generales que las entradas "clásicas", estas pueden simularse eficientemente en términos de transformaciones simplécticas módulo 2, a pesar de ser de sabor cuántico mecánico ( y solo un poco tímido de ser capaz de universalidad para la computación cuántica).

Niel de Beaudrap

@AaronSterling: son un subconjunto de todos los circuitos cuánticos que incluyen CNOTS (esencialmente XOR + fanout), así como una serie de puertas cuánticas que pueden crear superposiciones iguales (por ejemplo, puertas Hadamard). Si está familiarizado con el cálculo cuántico, entonces los circuitos corresponden a aquellos operadores que asignan operadores Pauli a otros operadores Pauli bajo conjugación, actuando sobre la entrada clásica (o entrada que se puede obtener de la entrada clásica a través de otro circuito de grupo Clifford).

Joe Fitzsimons

Creo que necesitamos una jerarquía de "sorpresa", con 'caerse de mi silla "en la parte superior :)

Suresh Venkat