Nessuna amplificazione che preservi la dimensione con consigli quantistici

Abstract degli autori

Marriott e Watrous hanno mostrato che i giochi quantistici Merlin--Arthur ammettono una riduzione generica dell’errore senza aumentare la dimensione del testimone [Computational Complexity, 2005]. In questo lavoro mostriamo che questa proprietà di amplificazione che preserva la dimensione dello stato non vale per la computazione quantistica in tempo polinomiale con consigli quantistici. In particolare, presentiamo problemi decisionali per i quali anche una riduzione additiva dell’errore che tende a zero richiede un consiglio più lungo. Più precisamente, per ogni lunghezza di advice limitata da un polinomio $m(n)\geq n^4$ e ogni limite di errore $\varepsilon(n)$ che rimane al di sotto di $1/2$ di almeno un termine inversamente polinomiale, esiste una funzione positiva $δ$ con $δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)$ tale che $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}m$; per $\varepsilon$ costante, il divario è $O(\sqrt{\log m/m})$. Qui, $\mathsf{BQP}_\varepsilon/\mathsf{q}m$ è la classe dei linguaggi riconoscibili con errore al più $\varepsilon(n)$ da un algoritmo quantistico in tempo polinomiale con uno stato di advice di $m(n)$ qubit che dipende soltanto dalla lunghezza dell’input $n$. Lo mostriamo dimostrando una separazione più forte, $\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m$, dove $\mathsf{P}_{\varepsilon}/\mathsf{r}m$ è la classe dei linguaggi riconoscibili con errore al più $\varepsilon(n)$ da un algoritmo deterministico in tempo polinomiale con una stringa di advice di $m(n)$ bit estratta da una distribuzione che dipende soltanto da $n$.