Ricerca rapida di corrispondenze con template nei circuiti quantistici mediante un ipergrafo

Abstract degli autori

L’ottimizzazione dei circuiti quantistici è un passaggio fondamentale per eseguire in modo efficiente gli algoritmi quantistici. La ricerca di corrispondenze con template si è affermata come uno dei principali approcci per semplificare i circuiti quantistici, ma deve affrontare la difficoltà intrinseca di tenere conto della commutatività dei gate. L’algoritmo più avanzato per questo tipo di ricerca si basa su una rappresentazione a grafo aciclico orientato (DAG). Pur gestendo in modo soddisfacente la commutatività dei gate, questa tecnica non preserva la connettività locale propria dei circuiti quantistici, con una conseguente complessità di ricerca relativamente elevata. In questo articolo presentiamo una rappresentazione mediante ipergrafo (HG) che tiene conto della commutatività: raggruppa i gate commutanti in un unico supernodo, preservando tutta la connettività locale. Ciò consente di estendere le corrispondenze localmente senza riesaminare il resto del circuito, limitando gli aggiornamenti incrementali alle immediate vicinanze. I risultati sperimentali mostrano che, su benchmark sia casuali sia aritmetici, il nostro algoritmo di ricerca basato su HG è da 11 a 606 volte più veloce dell’implementazione basata su DAG in Qiskit (Iten et al., 2022), pur mantenendo la stessa qualità dell’ottimizzazione. L’accelerazione aumenta con le dimensioni del circuito, confermando che preservare la località e la connettività è fondamentale per rendere scalabile l’ottimizzazione dei circuiti quantistici.