¿Reducción del espacio logarítmico de los circuitos Parity-L a CNOT?

Pregunta.

En su artículo, Simulación mejorada de circuitos estabilizadores , Aaronson y Gottesman afirman que simular un circuito CNOT es ⊕L -completo (bajo reducciones de espacio de registro). Está claro que está contenido en ⊕L ; ¿Cómo se mantiene el resultado de la dureza?

Equivalente: ¿hay una reducción de espacio de registro de productos de matriz iterada módulo 2, a productos iterados de matrices elementales (las matrices invertibles que realizan transformaciones de fila) mod 2?

Detalles

Una operación NOT-controlada (o CNOT ) es una operación booleana reversible, de la forma donde sólo el j ^ésimo se cambia poco, y que el bit se cambia agregando módulo 2, para cualquier posición distinta h y j . No es difícil de ver, si interpretamos

{C N O T}_{h, j} (x_{1}, \dots, x_{h}, \dots, x_{j}, \dots, x_{n}) = (x_{1}, \dots, x_{h}, \dots, x_{j} \oplus x_{h}, \dots, x_{n})

$\mathsf{CNOT}_{\!h,j} (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j\,, \;\ldots\;, x_n) \;\;=\;\; (x_1\,, \;\ldots\;, x_h\,,\; \ldots\;, x_j \oplus x_h\,, \;\ldots\;, x_n)$

x_{h}

$x_h$

x = (x_{1}, \dots, x_{n})

$\mathbf x = (x_1\,, \;\ldots\;, x_n)$ como un vector sobre ℤ / 2ℤ, que corresponde a un módulo de transformación de fila elemental 2, que podemos representar por una matriz con 1s en la diagonal y una única posición fuera de la diagonal. Un circuito CNOT es entonces un producto matricial que consiste en un producto de algunas matrices elementales de este tipo.

El artículo de Aaronson y Gottesman mencionado anteriormente (que, incidentalmente a esta pregunta, trata sobre una clase de circuitos cuánticos que pueden simularse en ⊕L ) tiene una sección sobre complejidad computacional. Hacia el comienzo de esta sección, describen ⊕L de la siguiente manera:

⊕L [es] la clase de todos los problemas que puede resolver una máquina Turing de espacio logarítmico no determinista, que acepta si y solo si el número total de caminos de aceptación es impar. Pero hay una definición alternativa que probablemente sea más intuitiva para los no científicos en computación. Este es que ⊕L es la clase de problemas que reducen a la simulación de un circuito de tamaño polinomio CNOT, es decir, un circuito compuesto enteramente de NOT y puertas CNOT, que actúa sobre el estado inicial | 0 ... 0⟩. (Es fácil demostrar que las dos definiciones son equivalentes, ¡pero esto requeriría primero explicar lo que significa la definición habitual!)

El público objetivo del artículo incluía un número considerable de no informáticos, por lo que el deseo de eludir no es irrazonable; Espero que alguien pueda aclarar cómo se mantiene esta equivalencia.

Claramente, la simulación de un producto de tales matrices se puede realizar en ⊕L como un caso especial de evaluación de coeficientes de productos de matriz iterada (mod 2), que es un problema completo (bajo reducciones de espacio de registro ) para ⊕L . Además, como las matrices CNOT solo realizan operaciones elementales de fila, cualquier matriz invertible puede descomponerse como producto de matrices CNOT. Sin embargo: no está claro cómo para mí descomponer incluso una matriz invertible mod 2 en un producto de matrices CNOT mediante una reducción de espacio de registro . (De hecho, como señaló Emil Jeřábek en los comentarios, la eliminación gaussiana es suficiente para calcular los determinantes mod 2, que es un problema ⊕L- completo: por lo tanto, un ataque directo por descomposición, por ejemplo Las matrices invertibles como productos de matrices elementales no parecen ser factibles en el espacio logs a menos que L = ⊕L .) Sin mencionar los productos matriciales que no son invertibles. Por lo tanto, parece ser necesaria una reducción más inteligente.

Espero que alguien pueda proporcionar un boceto de esta reducción, o una referencia ( por ejemplo, un texto para el cual es un ejercicio, si es simple).

cc.complexity-theory counting-complexity linear-algebra logspace Niel de Beaudrap
fuente

Supongo que los determinantes computacionales mod también son ⊕L-completos, por lo tanto, la eliminación gaussiana mod es ⊕L-difícil.

2

$2$

2

$2$

Emil Jeřábek apoya a Monica

@ EmilJeřábek: Estoy pensando en tu comentario, y estoy tratando de ver si esto implica inmediatamente que la simulación de circuitos CNOT no está completa para ⊕L a menos que L = ⊕L . (¡Considere un producto de una matriz, o un producto de una matriz única con la matriz de identidad!) Esto parece casi demasiado fácil; ¿Me estoy perdiendo de algo? Supongo que tal vez solo descarte reducciones de muchos a uno.

Niel de Beaudrap

No creo que sea tan fácil. ⊕L es una clase de problemas de decisión, mientras que la multiplicación de matrices sobre F_2 es un problema de función. La versión ⊕L de la multiplicación de matrices es pedir un bit particular del resultado (digamos, la entrada superior izquierda de la matriz). ¿Puede haber un algoritmo de espacio de registro que tome una secuencia de matrices y produzca una secuencia de matrices elementales para que los productos de ambas secuencias tengan el mismo elemento superior izquierdo? Esto es mucho más débil que la verdadera eliminación gaussiana. En realidad, la afirmación de Aaronson y Gottesman me parece plausible, aunque no estoy seguro de cómo demostrarlo.

Emil Jeřábek apoya a Monica

@ EmilJeřábek: Estoy pensando en cómo la mayoría de los ⊕L problemas de decisión se basan fuera de verificar coeficientes individuales de los problemas que son naturales para el DET (que es común hablar de problemas de la función como ⊕L -Complete, sin embargo, un abuso de terminología que es); y que mi intuición para los productos matriciales es que es lo suficientemente complicado como para que sea difícil organizar ad-hoc, para cualquier coeficiente individual , que dos productos matriciales deberían ser iguales para ese coeficiente de tal manera que no se pueda estar bastante seguro que todos los demás coeficientes estarán de acuerdo también.

Niel de Beaudrap

Lo tengo: contar las rutas de aceptación de una máquina de espacio de registro equivale a contar las rutas en un gráfico acíclico , que se puede representar mediante la multiplicación de matrices triangulares superiores con 1 en la diagonal. Este último puede expresarse fácilmente como un producto de matrices elementales de manera explícita, sin eliminación gaussiana.

Emil Jeřábek apoya a Monica

Comencemos con el problema -completo de contar mod el número de caminos de longitud desde el vértice hasta el vértice en un gráfico dirigido . Aplicamos un par de reducciones de espacio de registro de la siguiente manera. $\oplus L$ $2$ $n$ $s$ $t$ $G=(V,E)$

Sea la gráfica tal que y $G'=(V',E')$ $V'=V\times\{0,\dots,n\}$ (es decir, tomamos copias delos vérticesde , hacemos que los bordes pasen de la ésima copia a la ésima copia de acuerdo conlos bordes de , y agregue todos los bucles automáticos). Entonces el problema original es equivalente a contar caminos de longitud desde hasta $E'=\{((u,i),(v,i+1):i<n,(u,v)\in E\}\cup\{(w,w):w\in V'\}$ $n+1$ $G$ $i$ $(i+1)$ $G$ $n$ $s'=(s,0)$ $t'=(t,n)$ en . $G'$

Por otra parte, es acíclico, y podemos definir explícitamente una enumeración de tal manera que todos los bordes en aparte de los auto-bucles van de a para algunos . Sin pérdida de generalidad, y . Sea la matriz de adyacencia de $G'$ $V'=\{w_k:k\le m\}$ $G'$ $w_k$ $w_l$ $k<l$ $w_0=s'$ $w_m=t'$ $M$ $G'$ wrt la enumeración dada. Entonces es una matriz entera triangular superior con en la diagonal, y el número de caminos de longitud desde hasta es igual al elemento superior derecho de . $M$ $1$ $n$ $s'$ $t'$ $M^n$

Es fácil ver que donde es la matriz elemental cuya única entrada no diagonal es en fila y columna . De esta manera, redujimos el problema original a calcular el elemento superior derecho de un producto de matrices elementales. En el

M = \prod_{j = m}^{1} \prod_{i = 0}^{j - 1} E_{i, j} (M_{i, j}),

$M=\prod_{j=m}^1\prod_{i=0}^{j-1}E_{i,j}(M_{i,j}),$

E_{i, j} (a)

$E_{i,j}(a)$

a

$a$

i

$i$

j

$j$

\oplus L

$\oplus L$ En este caso, el cálculo es el módulo

, es decir, consideramos las matrices sobre

. (En este caso, las matrices elementales pueden ser solo

, que podemos ignorar, y

, que pueden ser simuladas por una sola puerta CNOT, como se menciona en la pregunta .) Si los consideramos como matrices de enteros, obtenemos un

problema -Complete, y si tenemos en cuenta que modulo

, obtenemos una

problema -Complete.

2

$2$

F_{2}

$\mathbb F_2$

E_{i, j} (0) = I

$E_{i,j}(0)=I$

E_{i, j} (1)

$E_{i,j}(1)$

# L

$\#L$

k

$k$

{M o d}_{k} L

$\mathrm{Mod}_kL$

Emil Jeřábek apoya a Monica
fuente

Quiero decir, es

-completo para matrices elementales con coeficientes enteros no negativos. Con enteros arbitrarios, es DET-complete.

# L

$\#L$

Emil Jeřábek apoya a Monica

Lo siguiente es probablemente estándar, pero no lo había visto explícitamente antes: para mostrar que encontrar el número de caminos de longitud precisamente n en un dígrafo (posiblemente cíclico) es ⊕L- completo, tenga en cuenta que esto equivale a coeficientes de cálculo de algunos potencia de una matriz arbitraria sobre

, que es ⊕L -completo. Esta respuesta es esencialmente como una reducción de la potencia de la matriz (usando una construcción estándar de M como una matriz de bloques que consiste solo en copias de la matriz de adyacencia arbitraria de G en los bloques superiores fuera de la diagonal, y 1 en la diagonal) a los circuitos CNOT . ¡Buena respuesta!

F_{2}

$\mathbb F_2$

Niel de Beaudrap

No necesita pasar por la alimentación de matriz, cuya ⊕L-integridad es más difícil de probar. ⊕L se define contando mod 2 las rutas de aceptación de una máquina de Turing de espacio de registro no determinista (con reloj de tiempo polinómico, supongo, de modo que se garantiza que el número sea finito), que es lo mismo que contar rutas en el gráfico de configuración del máquina (es fácil organizar que todas las rutas terminen en la misma configuración, y que las rutas tengan la misma longitud, haciendo que la máquina entre en un bucle hasta que expire su reloj y luego entre en un estado de aceptación fijo).

Emil Jeřábek apoya a Monica

Supongo que al centrarme en las ideas del artículo Stucture y la importancia de las clases Logspace-MOD de Buntrock et al. , Me he acostumbrado mucho más a pensar en términos de número de caminos de longitud arbitraria en un dígrafo acíclico , y los problemas de tipo DET como los productos y poderes matriciales que están naturalmente conectados a él.

Niel de Beaudrap

¿Reducción del espacio logarítmico de los circuitos Parity-L a CNOT?

Pregunta.

Detalles

Respuestas: