Generalized LIMDDs: Succinctness and Canonicity for Decision Diagrams Modulo a Group

Resumen Técnico: LIMDDs Generalizados: Concisión y Canonicidad para Diagramas de Decisión Módulo un Grupo

Planteamiento del Problema
Los Diagramas de Decisión Binaria Ordenados (OBDDs) representan funciones como autómatas mínimos donde los nodos corresponden a residuales (subfunciones) y la reducción se basa en el cociente de Myhill–Nerode (igualdad de residuales). Las generalizaciones de los OBDDs, como los Diagramas de Decisión con Valores de Arista (EVDDs) y los Diagramas de Decisión de Mapas Invertibles Locales (LIMDDs), introducen etiquetas de arista desde un dominio $L$ para fusionar nodos cuyos residuales concuerdan mediante una transformación de etiqueta. Específicamente, los Pauli-LIMDDs fusionan nodos si sus residuales pertenecen a la misma órbita bajo el grupo de Pauli, permitiendo una representación sucinta de estados estabilizadores.

El artículo aborda las limitaciones de los enfoques de grupo fijo. Si bien ampliar el grupo de etiquetas $G$ puede, teóricamente, aumentar la concisión al fusionar más nodos, plantea tres cuestiones críticas:

1. ¿Mantienen los $G$-LIMDDs formas normales únicas computables en tiempo polinómico?
2. ¿Cuánta ganancia de concisión proporciona realmente un grupo $G$ más grande?
3. ¿Qué consultas y transformaciones siguen siendo tratables a medida que el grupo se expande?

Trabajos previos sobre Rotation LIMDDs ($k=0$) mostraron beneficios prácticos pero carecieron de pruebas de separación asintótica. Por el contrario, ir más allá de los grupos (anti-)diagonales conlleva el riesgo de perder la propiedad "local" requerida para una construcción eficiente de abajo hacia arriba, lo que potencialmente obligaría a una reconstrucción completa del diagrama para determinar la equivalencia.

Metodología
Los autores introducen una familia de grupos de dos parámetros para generalizar los LIMDDs, definida por:

• Orden de la Raíz ($q$): El orden de las rotaciones de fase $R_q = \text{diag}(1, e^{2\pi i/q})$.
• Aridad de Control ($k$): El número máximo de cúbits de control para rotaciones controladas $C_h R_q$ (donde $h \le k$).
• Salto de Bit ($X$): La inclusión opcional de la puerta de salto de bit.

La familia se denota como $\langle C_{\le k} R_q \rangle$ (diagonal) y $\langle C_{\le k} R_q, X \rangle$ (anti-diagonal). El Pauli-LIMDD original corresponde a $k=0, q=2$ con $X$.

La metodología consiste en:

1. Definición del Grupo de Etiquetas: Formalización de la estructura del grupo donde los elementos son productos de rotaciones de fase controladas y saltos de bit opcionales. Los autores demuestran que para estos grupos específicos, la "división de capa" (cómo un elemento del grupo actúa sobre los cofactores de un nodo) preserva una estructura algebraica específica, permitiendo que la equivalencia de los residuales se decida localmente.
2. Análisis de Concisión: Uso de estados de hipergrafo y sus generalizaciones (estados de hipergrafo sesgados) como objetos separadores. Los autores construyen estados específicos que tienen representaciones de tamaño lineal en grupos de parámetros superiores, pero que requieren un tamaño exponencial en grupos de parámetros inferiores.
3. Construcción de Canonicidad: Desarrollo de un sistema de reducción de cinco reglas ($R1$–$R5$) para computar una forma normal única. Una contribución técnica clave es la identificación del dominio correcto para la regla de "Alto Determinismo" ($R4$), que minimiza la etiqueta de arista alta sobre un coset. Los autores demuestran que este coset incluye un "factor libre" derivado de la división de capa, un detalle omitido en trabajos anteriores.
4. Verificación de Tratabilidad: Análisis de la complejidad de cinco consultas estándar (Muestreo, Medición, Igualdad, Producto Interno, Fidelidad) y ocho aplicaciones de puertas (incluyendo $X, Z, T, H, \text{SWAP}, \text{CX}$).

Contribuciones Clave y Resultados

• Jerarquía de Concisión: El artículo establece una jerarquía exponencial estricta dentro de la familia.

  • Aumentar la aridad de control $k$ (de $h$ a $k$ donde $h < k$) produce ganancias de concisión exponenciales.
  • Aumentar el orden de la raíz $q$ (de $p$ a $q$ donde $p \nmid q$) produce ganancias exponenciales.
  • La adición del salto de bit $X$ proporciona una tercera dimensión de separación exponencial.
  • Objetos Separadores: Se demuestra que los estados de hipergrafo (y sus variantes sesgadas) tienen representaciones de tamaño lineal en Tower-LIMDDs. Específicamente, un estado de $k$-hipergrafo se representa mediante un Tower-$\langle C_{\le k-2} R_p \rangle$-LIMDD. Por el contrario, estos estados requieren un tamaño exponencial en grupos con un $k$ menor o un $q$ incompatible.
  • Transformada de Fourier Cuántica (QFT): La matriz QFT se muestra como representable mediante un Tower-$\langle R_{2^n} \rangle$-LIMDD de tamaño lineal, confirmando observaciones experimentales de trabajos previos.

• Canonicidad y Reducción:

  • Los autores proporcionan un sistema de reducción de cinco reglas ($R1$–$R5$) que produce una forma normal única para cada miembro de la familia.
  • Regla $R4$ (Alto Determinismo): El artículo corrige un error sutil en algoritmos de canonicidad previos. Demuestran que el conjunto de etiquetas equivalentes a la arista alta de un nodo es un coset de la forma $\langle C_{\le k-1} R_q \rangle \cdot \text{Stab}(v_0) \cdot L_1 \cdot \text{Stab}(v_1)$. La inclusión del factor libre $\langle C_{\le k-1} R_q \rangle$ es crucial y surge de la división de capa de los elementos del grupo.
  • Complejidad: La forma normal es computable en tiempo polinómico relativo al tamaño del LIMDD (para un $k$ fijo). Esto se basa en la representación de los elementos del grupo como vectores sobre $\mathbb{Z}_q$ y el uso de la reducción de Howell para computar los representantes de los cosets.

• Tratabilidad:

  • La frontera de la tratabilidad es invariante en toda la familia.
  • Tiempo Polinómico: El Muestreo, la Medición, la Igualdad y la aplicación de puertas diagonales ($Z, T, R_m, C_k R_m$) permanecen en P.
  • Dureza: El Producto Interno y la Fidelidad siguen siendo difíciles (a menos que P=NP) para grupos que contienen $Z$ (es decir, $2|q$).
  • Puertas Intratables: La aplicación de $H, \text{SWAP}$ o $CX$ no es aplicable en tiempo polinómico para ninguna clase de la familia, ya que estas operaciones pueden causar un crecimiento exponencial en el tamaño del diagrama.

• Límite de Localidad: El artículo demuestra que la propiedad (anti-)diagonal es un límite duro para la reducción local. Si el grupo contiene matrices que no son (anti-)diagonales (por ejemplo, la puerta Hadamard $H$), la equivalencia de los residuales ya no es una propiedad local de los hijos; un nodo que parece distinto localmente puede volverse redundante cuando se añade un padre. Esto fuerza una reconstrucción del diagrama no local y potencialmente de tiempo exponencial.

Significancia
El artículo afirma determinar completamente el orden de concisión de una amplia familia de diagramas de decisión módulo un grupo, cerrando la brecha entre los Pauli-LIMDDs y los diagramas de rotación de fase más generales. Demuestra que expandir el grupo para incluir controles de mayor aridad y raíces de mayor orden produce mejoras de concisión exponenciales demostrables sin sacrificar la capacidad de computar una forma normal única en tiempo polinómico.

El trabajo establece la tratabilidad de las operaciones fundamentales en toda esta familia, mostrando que la eficiencia de los LIMDDs es robusta frente a estas generalizaciones. Además, identifica el límite algebraico preciso (los grupos (anti-)diagonales) más allá del cual la construcción "local" de los diagramas de decisión falla, proporcionando un límite teórico para esta clase de representaciones sucintas. Los resultados caracterizan a los estados de hipergrafo como la clase precisa de estados que admiten representaciones de tamaño lineal en esta familia, ofreciendo una nueva perspectiva sobre la estructura de los estados cuánticos generados por circuitos conmutativos (IQP).