Le unitarie pseudocasuali di tipo funzione generano processi quantistici pseudocasuali

Abstract degli autori

Le unitarie casuali di Haar forniscono un modello canonico dell’evoluzione quantistica casuale generica, ma richiedono in genere una complessità esponenziale sia di descrizione sia circuitale. Sebbene le unitarie pseudocasuali emulino in modo efficiente una singola unitaria casuale di Haar, molti compiti richiedono un’intera famiglia riutilizzabile di operazioni dall’aspetto indipendentemente casuale. Introduciamo le unitarie pseudocasuali di tipo funzione (PRFU), che generano una famiglia di questo tipo, indicizzata da etichette pubbliche, usando una sola chiave breve. Distinguiamo l’accesso con etichette classiche da quello con etichette coerenti e dimostriamo la sicurezza contro query quantistiche adattive. Per le etichette classiche, forniamo una costruzione generica a partire da una funzione pseudocasuale post-quantistica e da un’unitaria pseudocasuale. Per le etichette coerenti, usiamo un framework indicizzato di registrazione dei percorsi per analizzare l’interferenza tra etichette e dimostriamo la sicurezza di una costruzione basata su primitive di funzione e permutazione sicure contro attacchi quantistici. Mostriamo inoltre che le PRFU generano canali pseudocasuali e comb quantistiche con memoria privata, sicuri contro interventi adattivi e sessioni concorrenti. Combinando le PRFU con l’incollaggio unitario, otteniamo una famiglia a chiave singola di unitarie pseudocasuali, le cui larghezze dei registri supportate possono essere scelte dopo la generazione della chiave. Tra le ulteriori applicazioni figurano l’autenticazione quantistica specifica per nonce, le query QRAM mascherate coerentemente e l’emulazione efficiente di dinamiche quantistiche casuali a tempi multipli. I nostri risultati estendono la pseudocasualità quantistica dalle singole operazioni a famiglie di dinamiche quantistiche dall’aspetto casuale, generate in modo efficiente.