Operatori di Clifford con trapdoor e applicazioni

Abstract degli autori

Gli operatori di Clifford casuali hanno numerose applicazioni nella computazione quantistica, tra cui il benchmark randomizzato, gli shadow classici e l’autenticazione quantistica. Tuttavia, campionare e implementare un operatore di Clifford scelto uniformemente a caso su $n$ qubit comporta una complessità quasi quadratica, a causa delle dimensioni del gruppo di Clifford. Introduciamo un metodo crittografico per superare questi ostacoli: distribuzioni di operatori di Clifford con trapdoor, i cui campioni sono computazionalmente indistinguibili da operatori di Clifford scelti uniformemente a caso, ma che, grazie alla trapdoor, possono essere implementati molto più rapidamente. Costruiamo una distribuzione di operatori di Clifford con trapdoor i cui elementi possono essere campionati e implementati in tempo quasi lineare, sotto una variante dell’ipotesi dell’apprendimento della parità con rumore. Le nostre costruzioni consentono di applicare rapidamente il tableau alle etichette di Pauli per la simulazione classica e possono anche essere ottimizzate per ottenere implementazioni con profondità polilogaritmica. Nel farlo, costruiamo matrici con trapdoor su campi finiti che consentono di moltiplicare in modo efficiente sia per una matrice sia per la sua inversa, risolvendo una questione aperta lasciata da Vaikuntanathan e Zamir [SODA'26]. Usiamo queste costruzioni per ottenere protocolli più rapidi basati su operatori di Clifford casuali. Esploriamo inoltre le loro applicazioni alle riduzioni dal caso peggiore al caso medio per problemi relativi a matrici e operatori di Clifford, tra cui la moltiplicazione iterata di matrici e la sintesi di circuiti Clifford. In particolare, dimostriamo la difficoltà di raggruppare in batch i circuiti Clifford: sintetizzare circuiti che applicano lo stesso operatore di Clifford a più registri è difficile almeno quanto la moltiplicazione di matrici nel caso peggiore, anche quando la sintesi riesce per una piccola frazione costante di operatori di Clifford casuali. Questo risultato si estende alle implementazioni approssimate mediante circuiti quantistici generici.