Faster algorithm for achieving minimal-size quantum decision diagrams

Resumen Técnico: Algoritmo más rápido para lograr Diagramas de Decisión Cuántica de tamaño mínimo

Planteamiento del Problema
Los diagramas de decisión (DDs) son una estructura de datos compacta para representar estados y operaciones cuánticas, logrando la sucinta mediante la fusión de subfunciones equivalentes en una forma canónica. Aunque los Diagramas de Decisión de Mapas Invertibles Locales (LIMDDs) ofrecen teóricamente ventajas exponenciales sobre otras estructuras como los Diagramas de Decisión Multivaluados Cuánticos (QMDDs) para clases específicas de circuitos (por ejemplo, circuitos de Clifford), estas ventajas no se han materializado plenamente en las implementaciones existentes.

El cuello de botella principal es el procedimiento de forma normal, específicamente la regla de alto determinismo requerida para asegurar la canonicidad. Esta regla resuelve los grados de libertad donde dos nodos representan el mismo estado cuántico mediante un mapa invertible local (LIM). El algoritmo existente para esta regla, basado en tareas de la teoría de grupos, tiene una complejidad temporal de caso peor de $O(n^3)$ para un nodo de $n$ cúbits. Además, las implementaciones de código abierto existentes (MQT-LIMDD y LimTDD) o bien no logran alcanzar el tamaño mínimo en todos los casos, o bien omiten deliberadamente la propiedad de canonicidad para evitar la complejidad de implementación, lo que conduce a posibles crecimientos exponenciales en el recuento de nodos.

Metodología
Los autores proponen un nuevo algoritmo para transformar nodos de Pauli-LIMDD semi-reducidos en formas totalmente reducidas (canónicas), optimizando específicamente la regla de alto determinismo.

1. Mejora Algorítmica:

   • Los autores adaptan el procedimiento de Zassenhaus, un método para computar intersecciones y uniones de espacios vectoriales, para resolver el problema de minimización requerido para el alto determinismo.
   • En lugar de calcular las intersecciones de grupos estabilizadores y los cocientes por separado, construyen una "matriz de Zassenhaus" con tres registros: vectores binarios que representan palabras de Pauli, estabilizadores medios y estabilizadores derechos.
   • Al realizar la eliminación de Gauss en esta matriz utilizando las reglas de multiplicación de Pauli-LIM, encuentran simultáneamente la palabra de Pauli mínima y los generadores de estabilizador correspondientes.
   • Reducción de Complejidad:
     • Para nodos con dos hijos distintos, el algoritmo mantiene la complejidad de caso peor de $O(n^3)$ pero con una carga computacional reducida.
     • Para nodos con un único hijo (un caso común donde los DDs logran la sucinta), el problema se simplifica a minimizar un vector contra un único grupo estabilizador. Esto reduce la complejidad de $O(n^3)$ a $O(n^2)$.

2. Búsqueda Recursiva de Estabilizadores:

   • Los autores presentan un algoritmo recursivo para computar el conjunto generador del estabilizador para un nodo reducido utilizando los resultados de Zassenhaus. Esto evita cálculos redundantes de intersección de grupos, optimizando aún más el caso de $O(n^2)$ para nodos de un solo hijo.

3. Implementación (QolDDer):

   • El algoritmo se implementa en QolDDer, un nuevo simulador de Pauli-LIMDD escrito desde cero en C/C++ y de código abierto.
   • QolDDer incluye una biblioteca separada, PauliLim, para la lógica central de normalización.
   • La implementación maneja la precisión numérica tratando los escalares de punto flotante con un umbral configurable ($\delta = 10^{-13}$) y utilizando árboles de búsqueda para la comprobación de equivalencia, preservando al mismo tiempo la canonicidad.

Resultos Clave
Los autores evaluaron QolDDer frente a dos implementaciones existentes de LIMDD (MQT-LIMDD, LimTDD) y el simulador QMDD (MQT-DDSIM) utilizando los conjuntos de datos RandCliff (Clifford aleatorio) y MQT-Bench.

• Aceleración Exponencial en Circuitos de Clifford: En circuitos de Clifford aleatorios (RandCliff), QolDDer demuestra una aceleración exponencial sobre los QMDDs (MQT-DDSIM). Esto confirma la ventaja teórica de los LIMDDs, que pueden representar las salidas de circuitos de Clifford en un espacio polinomial, mientras que los QMDDs no pueden representar de forma sucinta los estados altamente entrelazados resultantes.
• Impacto de la Canonicidad:
  • Habilitar la canonicidad total (Alto Determinismo) en QolDDer resulta en tiempos de ejecución significativamente más rápidos y un recuento de nodos drásticamente menor en comparación con las versiones semi-reducidas (no canónicas) en circuitos de Clifford.
  • QolDDer supera a la implementación existente de MQT-LIMDD por un orden de magnitud en muchas instancias, debido a la implementación parcial de la canonicidad en MQT-LIMDD.
  • QolDDer es consistentemente más rápido que LimTDD (que carece de garantías de canonicidad) en circuitos de Clifford, a menudo por un factor de 25 o más, debido a la reducción del recuento de nodos lograda mediante la fusión canónica.
• Limitaciones en Benchmarks Generales: En el conjunto de datos más amplio MQT-Bench, la ventaja de rendimiento de la canonicidad no es universal. Para ciertos tipos de circuitos (por ejemplo, Redes Neuronales Cuánticas, algoritmo de Grover), los LIMs no proporcionan más fusión que los QMDDs, y la sobrecarga de mantener la canonicidad hace que QolDDer sea ligeramente más lento (por un factor constante) que MQT-DDSIM. Sin embargo, el escalado sigue siendo lineal.

Significancia y Reivindicaciones
El artículo sostiene que la barrera principal para realizar el poder teórico de los LIMDDs ha sido la falta de una implementación eficiente y totalmente canónica. Al proporcionar un algoritmo de $O(n^2)$ para el caso crítico de un solo hijo y una implementación robusta y de código abierto (QolDDer), los autores demuestran que:

1. Los LIMDDs pueden, de hecho, lograr ventajas exponenciales sobre los QMDDs para clases de circuitos específicas e importantes (circuitos de Clifford).
2. La canonicidad es esencial para alcanzar estas ventajas; sin ella, el recuento de nodos puede dispararse, anulando los beneficios de la estructura de datos.
3. El trabajo permite el desarrollo posterior de variantes de LIMDD tanto para tareas de diseño cuántico como para el análisis de sistemas basados en álgebra lineal general.

Los autores se mantienen modestos respecto a los benchmarks generales, señalando que para circuitos donde los LIM no ofrecen una fusión adicional sobre los QMDDs, la sobrecarga canónica puede no estar justificada. Se prevé que el trabajo futuro extienda estos algoritmos al grupo XP más amplio y aplique los LIMDDs a tareas como la comprobación de equivalencia de circuitos y problemas de álgebra lineal clásica.