Vai al contenuto
Quantum.world

The Signal

Søren Fuglede Jørgensen presenta una dimostrazione della NP-completezza della sintesi Clifford con limite sul numero di gate

Søren Fuglede Jørgensen dimostra che decidere se un operatore Clifford possa essere implementato entro un limite specificato di gate è un problema NP-completo in diversi modelli di risorse. Le riduzioni collegano i cammini hamiltoniani nei grafi a griglia ai limiti sul numero di gate, con implicazioni per l’ottimizzazione esatta dei circuiti.

Søren Fuglede Jørgensen presenta una dimostrazione della NP-completezza della sintesi Clifford con limite sul numero di gate

È possibile sintetizzare circuiti Clifford per sistemi con molti qubit, ma trovare il circuito più breve entro un limite sul numero di gate è un problema diverso: Søren Fuglede Jørgensen dimostra che la sua versione decisionale è NP-completa. Il risultato riguarda la minimizzazione esatta delle risorse, non la possibilità di produrre un circuito funzionante. La distinzione è importante per i compilatori che devono trovare un compromesso tra il numero di gate e il tempo e l’impegno necessari per cercare un’implementazione migliore.

Fonte arxiv.org

Presentato ad arXiv il 29 ottobre, lo studio dimostra la difficoltà del problema in diversi modelli di costo dei gate, inclusi circuiti costruiti con gate CNOT e circuiti che possono usare qualsiasi gate Clifford a due qubit. Le riduzioni partono dal problema del cammino hamiltoniano nei grafi a griglia, codificando l’esistenza di un cammino come la questione se un operatore Clifford possa essere implementato entro un limite specificato di gate.

Trovare un circuito non significa trovare il più breve

Le operazioni Clifford sono fondamentali per la correzione degli errori quantistici e la distillazione di stati magici; inoltre, i compilatori sostituiscono sottocircuiti Clifford per ridurre le risorse usate da programmi più grandi. I metodi di sintesi esistenti coprono un’ampia gamma di casi: alcuni gestiscono in modo efficiente un numero elevato di qubit, ma possono produrre circuiti con un numero di gate o una profondità elevati, mentre i metodi esatti cercano circuiti ottimali per casi di dimensioni piccole o intermedie. Il risultato di Jørgensen riguarda il costo di garantire la soluzione migliore, non la possibilità per un compilatore di generare un circuito equivalente.

«Dimostriamo che il problema di sintetizzare un circuito quantistico per un dato operatore Clifford usando al massimo una quantità specificata di risorse è NP-completo per diversi modelli di risorse di interesse pratico.»

Søren Fuglede Jørgensen, autore dello studio

Un cammino su una griglia diventa un limite sul numero di gate

La dimostrazione si basa su lavori precedenti che mostrano la difficoltà della sintesi con soli CNOT. Un cammino hamiltoniano deve visitare ogni vertice di un grafo esattamente una volta; nella riduzione, gli spostamenti tra vertici adiacenti della griglia corrispondono ad aggiornamenti CNOT. Qubit aggiuntivi «registratori» conservano informazioni sul cammino nella trasformazione finale del circuito, mentre un limite sul numero di gate scelto con cura esclude le implementazioni che saltano la sequenza richiesta.

Jørgensen estende la costruzione ai circuiti Clifford completi, nei quali i gate a singolo qubit potrebbero altrimenti offrire scorciatoie rispetto alla sequenza CNOT prevista. L’abstract dello studio afferma che le riduzioni usano un numero di qubit quadratico rispetto al numero di vertici della griglia. Il teorema principale individua anche una classe ristretta di operatori bersaglio per i quali la difficoltà sussiste già: operatori rappresentati da matrici unitriangolari inferiori che soddisfano una specifica condizione algebrica.

La difficoltà sussiste in diversi modelli di costo

Il risultato presuppone la connettività completa: qualsiasi coppia di qubit può interagire. Esclude inoltre qubit ancillari aggiuntivi. Nel modello centrale, i gate Clifford a singolo qubit sono gratuiti e il limite tiene conto dei CNOT; la dimostrazione si estende poi a limiti che conteggiano gate Clifford arbitrari a due qubit, a modelli che attribuiscono un costo ai gate a singolo qubit e a modelli nei quali i gate SWAP sono gratuiti.

Queste varianti rendono il teorema rilevante anche al di là di un singolo elenco di gate specifico per un dato hardware, ma non dimostrano che ogni istanza pratica di ottimizzazione sia difficile. La NP-completezza riguarda le istanze nel caso peggiore e la questione decisionale: se esista un circuito entro il limite dato. Un circuito proposto può essere verificato in modo efficiente e gli algoritmi possono comunque produrre circuiti utili, anche se non ottimali, senza risolvere il problema del minimo esatto.

Al risultato sulla profondità si aggiunge quello sul numero di gate

Lo studio distingue il proprio risultato dal lavoro di Luna Lima Keller e Richard Kueng, che dimostra la NP-completezza di un problema di sintesi Clifford vincolato dalla profondità del circuito. La profondità misura il numero di livelli sequenziali di gate necessari a un circuito; Jørgensen studia il numero di gate. I due studi affrontano quindi obiettivi di ottimizzazione diversi, anziché contraddirsi.

Questa distinzione pone ai progettisti di compilatori due limiti distinti relativi al caso peggiore di cui tenere conto: la minimizzazione del numero di gate e quella del numero di livelli. Per il risultato di Jørgensen sul numero di gate, la costruzione concreta parte da un’istanza del problema del cammino hamiltoniano in un grafo a griglia e la trasforma in un operatore Clifford bersaglio con un limite specificato sul numero di gate.

Fonti

  1. arXiv
  2. arXiv
  3. arXiv
  4. arXiv (full text)

Notizie correlate

Esplora

Altri articoli