Grado di approssimazione nel calcolo classico e quantistico

Titolo originale:

Approximate Degree in Classical and Quantum Computing

Contenuto del libro:

La capacità (o l'incapacità) di rappresentare o approssimare funzioni booleane mediante polinomi è un concetto centrale nella teoria della complessità, alla base dei sistemi di prova interattivi e verificabili probabilisticamente, dei limiti inferiori dei circuiti, della teoria della complessità quantistica e altro ancora. In questo libro, gli autori analizzano le conoscenze su una nozione particolarmente naturale di approssimazione mediante polinomi, che cattura l'approssimazione puntuale sui numeri reali.

Il libro illustra i recenti progressi nella dimostrazione di limiti inferiori e superiori di grado approssimato e descrive alcune applicazioni dei nuovi limiti alle separazioni di oracoli, alla complessità quantistica delle interrogazioni e delle comunicazioni e alla complessità dei circuiti. Gli autori spiegano come molti di questi progressi siano stati raggiunti grazie a una tecnica particolarmente semplice ed elegante, chiamata composizione di blocchi duali, per costruire soluzioni a questo programma lineare duale. Inoltre, forniscono una trattazione concisa di tecniche di lower bound ancora più recenti, basate su una nuova misura di complessità chiamata sensibilità spettrale. Infine, mostrano come le costruzioni esplicite di polinomi approssimati siano state ispirate da algoritmi di interrogazione quantistica.

Questo libro fornisce una rassegna completa dei fondamenti e dei recenti sviluppi di un argomento importante per l'informatica classica e quantistica. Il lettore ha a disposizione un notevole bagaglio di conoscenze condensato in una forma accessibile per comprendere rapidamente i principi e approfondire le proprie ricerche.