Una separazione tra tipi di separazioni con oracoli quantistici

Abstract degli autori

Lavori recenti hanno mostrato che gli oracoli quantistici presentano comportamenti sottili: l’accesso a query inverse, coniugate o controllate può modificare esponenzialmente la complessità delle query di determinati compiti. Ispirati da questi lavori, introduciamo la nozione di meta-complessità della relativizzazione quantistica. Ci chiediamo: per due qualsiasi classi di complessità quantistica, rispetto a quali «tipi» di oracoli quantistici sono uguali o separate? Diverse famiglie di oracoli (o tipi di oracoli quantistici, per esempio unitari o di stato, di dimensione polinomiale o superpolinomiale, chiusi rispetto all’inversa o meno) formano un insieme parzialmente ordinato in base alla loro capacità di separare classi di complessità. Inoltre, due famiglie di oracoli A e B sono separate se esiste una coppia di classi di complessità separate rispetto a un oracolo della famiglia A, ma equivalenti rispetto a tutti gli oracoli della famiglia B. Mostriamo che questa meta-complessità può essere non banale fornendo una classificazione completa, all’interno della famiglia di famiglie di oracoli definite in questo articolo, dei modelli che possono separare le classi di complessità $\mathsf{PostBQP}$ e $\mathsf{PreciseBQP}$, la variante di $\mathsf{BQP}$ con precisione esponenziale. Nel caso non relativizzato, entrambe le classi sono uguali a $\mathsf{PP}$. Nella nostra tassonomia, restano uguali rispetto a oracoli unitari reali o di dimensione polinomiale, e anche quando è fornito l’accesso all’inversa o al coniugato. Al contrario, mostriamo una separazione rispetto a unitarie diagonali complesse di dimensione superpolinomiale con accesso solo in avanti, nonché una separazione rispetto a oracoli di preparazione di stati di un singolo qubit. Consideriamo questo un caso di prova per la meta-complessità degli oracoli, che mette in luce la sottigliezza intrinseca alla relativizzazione delle classi di complessità quantistica.