Faster algorithm for achieving minimal-size quantum decision diagrams

Resumo Técnico: Algoritmo Mais Rápido para Alcançar Diagramas de Decisão Quântica de Tamanho Mínimo

Definição do Problema
Diagramas de decisão (DDs) são uma estrutura de dados compacta para representar estados e operações quânticas, alcançando concisão ao mesclar subfunções equivalentes em uma forma canônica. Embora os Local Invertible Map Decision Diagrams (LIMDDs) ofereçam teoricamente vantagens exponenciais sobre outras estruturas como os Quantum Multiple-Valued Decision Diagrams (QMDDs) para classes específicas de circuitos (ex: circuitos de Clifford), essas vantagens não se materializaram totalmente em implementações existentes.

O principal gargalo é o procedimento de forma normal, especificamente a regra de alto determinismo necessária para garantir a canonicidade. Esta regra resolve graus de liberdade onde dois nós representam o mesmo estado quântico até uma aplicação de um mapa invertível local (LIM). O algoritmo existente para esta regra, baseado em tarefas de teoria de grupos, possui uma complexidade de tempo de pior caso de $O(n^3)$ para um nó de $n$ qubits. Além disso, as implementações de código aberto existentes (MQT-LIMDD e LimTDD) ou falham em alcançar o tamanho mínimo em todos os casos ou omitem deliberadamente a propriedade de canonicidade para evitar a complexidade de implementação, levando a potenciais explosões exponenciais na contagem de nós.

Metodologia
Os autores propõem um novo algoritmo para transformar nós de semi-reduzidos de Pauli-LIMDD em formas totalmente reduzidas (canônicas), especificamente otimizando a regra de alto determinismo.

1. Melhoria Algorítmica:

   • Os autores adaptam o procedimento de Zassenhaus, um método para computar interseções e uniões de espaços vetoriais, para resolver o problema de minimização exigido pelo alto determinismo.
   • Em vez de calcular interseções de grupos estabilizadores e cossetes separadamente, eles constroem uma "matriz de Zassenhaus" com três registradores: vetores binários representando palavras de Pauli, estabilizadores do meio e estabilizadores da direita.
   • Ao realizar a eliminação gaussiana nesta matriz usando as regras de multiplicação de Pauli-LIM, eles encontram simultaneamente a palavra de Pauli mínima e os geradores estabilizadores correspondentes.
   • Redução de Complexidade:
     • Para nós com dois filhos distintos, o algoritmo mantém a complexidade de pior caso de $O(n^3)$, mas com carga computacional reduzida.
     • Para nós com um único filho (um caso comum onde os DDs alcançam concisão), o problema simplifica-se para minimizar um vetor contra um único grupo estabilizador. Isso reduz a complexidade de $O(n^3)$ para $O(n^2)$.

2. Busca Recursiva de Estabilizadores:

   • Os autores apresentam um algoritmo recursivo para computar o conjunto gerador de estabilizadores para um nó reduzido usando os resultados de Zassenhaus. Isso evita cálculos redundantes de interseção de grupos, otimizando ainda mais o caso de $O(n^2)$ para nós de filho único.

3. Implementação (QolDDer):

   • O algoritmo é implementado no QolDDer, um novo simulador de Pauli-LIMDD escrito do zero em C/C++.
   • O QolDDer inclui uma biblioteca separada, PauliLim, para a lógica central de normalização.
   • A implementação lida com a precisão numérica tratando escalares de ponto flutuante com um limiar configurável ($\delta = 10^{-13}$) e utilizando árvores de busca para verificação de equivalência, preservando a canonicidade.

Principais Resultados
Os autores avaliaram o QolDDer contra duas implementações existentes de LIMDD (MQT-LIMDD, LimTDD) e o simulador QMDD (MQT-DDSIM) usando os conjuntos de dados RandCliff (Clifford aleatório) e MQT-Bench.

• Aceleração Exponencial em Circuitos de Clifford: Em circuitos de Clifford aleatórios (RandCliff), o QolDDer demonstra uma aceleração exponencial sobre os QMDDs (MQT-DDSIM). Isso confirma a vantagem teórica dos LIMDDs, que podem representar saídas de circuitos de Clifford em espaço polinomial, enquanto os QMDDs não conseguem representar de forma sucinta os estados altamente emaranhados resultantes.
• Impacto da Canonicidade:
  • Habilitar a canonicidade total (Alto Determinismo) no QolDDer resulta em tempos de execução significativamente mais rápidos e drasticamente menos nós em comparação com versões semi-reduzidas (não canônicas) em circuitos de Clifford.
  • O QolDDer supera a implementação existente do MQT-LIMDD em uma ordem de magnitude em muitas instâncias, atribuído à implementação parcial de canonicidade do MGT-LIMDD.
  • O QolDDer é consistentemente mais rápido que o LimTDD (que carece de garantias de canonicidade) em circuitos de Clifford, frequentemente por um fator de 25 ou mais, devido à redução na contagem de nós alcançada através da fusão canônica.
• Limitações em Benchmarks Gerais: No conjunto de dados mais amplo MQT-Bench, a vantagem de desempenho da canonicidade não é universal. Para certos tipos de circuitos (ex: Redes Neurais Quânticas, algoritmo de Grover), os LIMs não fornecem mais fusão do que os QMDDs, e o overhead de manter a canonicidade torna o QolDDer ligeiramente mais lento (por um fator constante) que o MQT-DDSIM. No entanto, o escalonamento permanece linear.

Significância e Alegações
O artigo afirma que a principal barreira para realizar o poder teórico dos LIMDDs tem sido a falta de uma implementação eficiente e totalmente canônica. Ao fornecer um algoritmo de $O(n^2)$ para o caso crítico de filho único e uma implementação robusta e de código aberto (QolDDer), os autores demonstram que:

1. Os LIMDDs podem, de fato, alcançar vantagens exponenciais sobre os QMDDs para classes de circuitos específicas e importantes (circuitos de Clifford).
2. A canonicidade é essencial para realizar essas vantagens; sem ela, a contagem de nós pode explodir, anulando os benefícios da estrutura de dados.
3. O trabalho permite o desenvolvimento futuro de variantes de LIMDD para tarefas de design quântico e análise de sistemas baseados em álgebra linear geral.

Os autores mantêm a modéstia em relação aos benchmarks gerais, observando que para circuitos onde os LIMs não oferecem fusão adicional sobre os QMDDs, o overhead canônico pode não ser justificado. O trabalho futuro prevê estender esses algoritmos para o grupo XP mais amplo e aplicar os LIMDDs a tarefas como verificação de equivalência de circuitos e problemas de álgebra linear clássica.