Faster algorithm for achieving minimal-size quantum decision diagrams

Sintesi Tecnica: Algoritmo più veloce per il raggiungimento di Diagrammi decisionali quantistici di dimensione minima

Definizione del problema
I diagrammi decisionali (DD) sono una struttura dati compatta per la rappresentazione di stati e operazioni quantistiche, che ottengono la sinteticità fondendo sottofunzioni equivalenti in una forma canonica. Sebbene i Local Invertible Map Decision Diagrams (LIMDD) offrano teoricamente vantaggi esponenziali rispetto ad altre strutture come i Quantum Multiple-Valued Decision Diagrams (QMDD) per specifiche classi di circuiti (ad es. circuiti di Clifford), questi vantaggi non si sono pienamente concretizzati nelle implementazioni esistenti.

Il collo di bottiglia principale è la procedura di forma normale, specificamente la regola dell'alto determinismo (high determinism rule) richiesta per garantire la canonicità. Questa regola risolve i gradi di libertà in cui due nodi rappresentano lo stesso stato quantistico fino a una mappa invertibile locale (LIM). L'algoritmo esistente per questa regola, basato su compiti di teoria dei gruppi, ha una complessità temporale nel caso peggiore di $O(n^3)$ per un nodo a $n$ qubit. Inoltre, le attuali implementazioni open-source (MQT-LIMDD e LimTDD) o non riescono a raggiungere la dimensione minima in tutti i casi o omettono deliberatamente la proprietà di canonicità per evitare la complessità di implementazione, portando a potenziali esplosioni esponenziali nel numero di nodi.

Metodologia
Gli autori propongono un nuovo algoritmo per trasformare i nodi Pauli-LIMDD semi-ridotti in forme completamente ridotte (canoniche), ottimizzando specificamente la regola dell'alto determinismo.

1. Miglioramento algoritmico:

   • Gli autori adattano la procedura di Zassenhaus, un metodo per calcolare le intersezioni e le unioni di spazi vettoriali, per risolvere il problema di minimizzazione richiesto dall'alto determinismo.
   • Invece di calcolare separatamente le intersezioni dei gruppi stabilizzatori e i cosetti, costruiscono una "matrice di Zassenhaus" con tre registri: vettori binari che rappresentano le parole Pauli, stabilizzatori medi e stabilizzatori destri.
   • Eseguendo l'eliminazione gaussiana su questa matrice utilizzando le regole di moltiplicazione Pauli-LIM, trovano simultaneamente la parola Pauli minima e i corrispondenti generatori dello stabilizzatore.
   • Riduzione della complessità:
     • Per i nodi con due figli distinti, l'algoritmo mantiene la complessità nel caso peggiore di $O(n^3)$ ma con un overhead ridotto.
     • Per i nodi con un singolo figlio (un caso comune in cui i DD ottengono la sinteticità), il problema si semplifica nella minimizzazione di un vettore rispetto a un singolo gruppo stabilizzatore. Ciò riduce la complessità da $O(n^3)$ a $O(n^2)$.

2. Ricerca ricorsiva dello stabilizzatore:

   • Gli autori presentano un algoritmo ricorsivo per calcolare l'insieme generatore dello stabilizzatore per un nodo ridotto utilizzando i risultati di Zassenhaus. Questo evita calcoli ridondanti di intersezione dei gruppi, ottimizzando ulteriormente il caso $O(n^2)$ per i nodi con singolo figlio.

3. Implementazione (QolDDer):

   • L'algoritmo è implementato in QolDDer, un nuovo simulatore Pauli-LIMDD open-source, scritto da zero in C/C++.
   • QolDDer include una libreria separata, PauliLim, per la logica di normalizzazione centrale.
   • L'implementazione gestisce la precisione numerica trattando gli scalari in virgola mobile con una soglia configurabile ($\delta = 10^{-13}$) e utilizzando alberi di ricerca per il controllo di equivalenza, preservando al contempo la canonicità.

Risultati chiave
Gli autori hanno valutato QolDDer rispetto a due implementazioni esistenti di LIMDD (MQT-LIMDD, LimTDD) e al simulatore QMDD (MQT-DDSIM) utilizzando i dataset RandCliff (Clifford casuali) e MQT-Bench.

• Accelerazione esponenziale sui circuiti di Clifford: Su circuiti Clifford casuali (RandCliff), QolDDer dimostra un'accelerazione esponenziale rispetto ai QMDD (MQT-DDSIM). Ciò conferma il vantaggio teorico dei LIMDD, che possono rappresentare gli output dei circuiti di Clifford in spazio polinomiale, mentre i QMDD non possono rappresentare in modo sintetico gli stati altamente intrecciati risultanti.
• Impatto della canonicità:
  • Abilitare la piena canonicità (Alto Determinismo) in QolDDer produce tempi di esecuzione significativamente più rapidi e un numero di nodi drasticamente inferiore rispetto alle versioni semi-ridotte (non canoniche) sui circuiti di Clifford.
  • QolDDer supera l'implementazione esistente di MQT-LIMDD di un ordine di grandezza in molti casi, grazie all'implementazione parziale della canonicità in MQT-LIMDD.
  • QolDDer è costantemente più veloce di LimTDD (che manca di garanzie di canonicità) sui circuiti di Clifford, spesso di un fattore di 2 o più, grazie alla riduzione del numero di nodi ottenuta tramite il merging canonico.
• Limitazioni sui benchmark generali: Sul dataset più ampio MQT-Bench, il vantaggio di prestazioni della canonicità non è universale. Per certi tipi di circuiti (ad es. Reti Neurali Quantistiche, algoritmo di Grover), le LIM non forniscono un maggiore merging rispetto ai QMDD, e l'overhead del mantenimento della canonicità rende QolDDer leggermente più lento (per un fattore costante) rispetto a MQT-DDSIM. Tuttavia, la scalabilità rimane lineare.

Significatività e rivendicazioni
L'articolo sostiene che la barriera principale per realizzare il potere teorico dei LIMDD sia stata la mancanza di un'implementazione efficiente e completamente canonica. Fornendo un algoritmo $O(n^2)$ per il caso critico del singolo figlio e un'implementazione robusta e open-source (QolDDer), gli autori dimostrano che:

1. I LIMDD possono effettivamente ottenere vantaggi esponenziali rispetto ai QMDD per specifiche e importanti classi di circuiti (circuiti di Clifford).
2. La canonicità è essenziale per realizzare questi vantaggi; senza di essa, il numero di nodi può esplodere, annullando i benefici della struttura dati.
3. Il lavoro abilita lo sviluppo ulteriore di varianti LIMDD per compiti di progettazione quantistica e analisi generale di sistemi basati sull'algebra lineare.

Gli autori rimangono modesti riguardo ai benchmark generali, osservando che per i circuiti in cui le LIM non offrono un ulteriore merging rispetto ai QMDD, l'overhead canonico potrebbe non essere giustificato. Il lavoro futuro è immaginato nell'estensione di questi algoritmi al più ampio gruppo XP e nell'applicazione dei LIMDD a compiti come il controllo di equivalenza dei circuiti e problemi di algebra lineare classica.