Complessità distribuzionale delle query quantistiche

Abstract degli autori

La complessità delle query quantistiche presenta diverse proprietà desiderabili per il calcolo congiunto: per esempio, un teorema di composizione secondo cui $Q(f\circ g)=Θ(Q(f)Q(g))$ per tutte le funzioni booleane $f$ e $g$; un teorema di somma diretta secondo cui calcolare $k$ copie di una funzione (o di un problema di ricerca) costa $Ω(k)$ volte quanto calcolarne una sola; e un teorema di prodotto diretto secondo cui, per le funzioni booleane, persino riuscire a risolvere il problema della somma diretta con probabilità esponenzialmente piccola richiede un costo pari a $Ω(k)$ volte quello necessario per calcolare una sola copia con errore limitato. Tuttavia, tutti questi risultati valgono esclusivamente per la complessità delle query quantistiche nel caso peggiore. Per esempio, se abbiamo una distribuzione fissa $μ$ sugli input, il teorema della somma diretta non dice nulla sulla complessità delle query quantistiche necessaria per calcolare $k$ copie di $f$ quando l’input è estratto dalla distribuzione prodotto $μ^k$, invece di considerare il caso peggiore. (Si noti che, sebbene un teorema minimax standard di tipo Yao garantisca l’esistenza di una distribuzione difficile per il problema della somma diretta, non garantisce che tale distribuzione sia una distribuzione prodotto.) Un problema analogo si presenta per il teorema del prodotto diretto e per quello di composizione: nessuno di questi risultati tiene conto delle distribuzioni. In questo lavoro forniamo limiti inferiori distribuzionali per il calcolo congiunto nei problemi di composizione, somma diretta e prodotto diretto. Nel corso del lavoro introduciamo alcuni nuovi strumenti per trattare i limiti inferiori della complessità delle query quantistiche, tra cui (a) una nuova variante «moltiplicativa» della norma $γ_2$ (che usiamo al posto del metodo dell’avversario moltiplicativo per dimostrare il teorema del prodotto diretto) e (b) una nuova misura della complessità delle query quantistiche «priva di Shaltiel», che mostriamo caratterizzare il comportamento rispetto alla composizione della complessità distribuzionale delle query quantistiche e possedere proprietà desiderabili.