Complessità delle interrogazioni quantistiche rumorose tramite la sensibilità frazionaria a blocchi

Abstract degli autori

Studiamo la complessità delle interrogazioni quantistiche in diversi modelli di accesso imperfetto all’oracolo e ricaviamo limiti inferiori attraverso un quadro comune basato sulla sensibilità frazionaria a blocchi ($\operatorname{fbs}$). Per un oracolo negligente che esegue l’interrogazione corretta con probabilità $1-p$, dimostriamo un limite inferiore in funzione di $\operatorname{fbs}(f,0^n)$. Mostriamo inoltre, forse sorprendentemente, che la negligenza non deve necessariamente eliminare i vantaggi quantistici: qualsiasi funzione $f$ può essere trasformata in una funzione parziale $f'$ la cui complessità delle interrogazioni con un oracolo negligente conserva essenzialmente quella delle interrogazioni quantistiche di $f$. Ciò fornisce funzioni parziali con vantaggi quantistici esponenziali anche in presenza di interrogazioni negligenti e, in particolare, esclude l’esistenza di un limite inferiore generale in funzione di $\operatorname{fbs}(f)$ per le funzioni parziali in questo modello. Per altri due modelli, otteniamo limiti inferiori generali in funzione di $\operatorname{fbs}(f)$ per tutte le funzioni booleane. Per gli algoritmi ibridi che usano $Q$ interrogazioni coerenti e $C$ interrogazioni classiche, dimostriamo la relazione di compromesso $C+Q^2=Ω(\operatorname{fbs}(f))$. Per un modello rumoroso con defasamento IID, in cui ogni interrogazione defasa indipendentemente il registro degli indici delle interrogazioni con tasso $p$, dimostriamo che sono necessarie $Ω\!\left(p\,\operatorname{fbs}(f)\right)$ interrogazioni. Infine, introduciamo una famiglia più ampia di modelli di defasamento variabile nel tempo e individuiamo una risorsa variazionale che è sempre limitata inferiormente da $\operatorname{fbs}(f)$. Il calcolo di questa risorsa si riduce a un problema di ottimizzazione convessa, offrendo un modo semplice per ricavare limiti inferiori per nuovi schemi di rumore. Come applicazioni, ritroviamo i limiti per i modelli ibrido e con defasamento IID e determiniamo la complessità delle interrogazioni per la ricerca non strutturata quando il tasso di defasamento cresce nel tempo.