Grade aproximative în calculul clasic și cuantic

Titlul original:

Approximate Degree in Classical and Quantum Computing

Conținutul cărții:

Capacitatea (sau incapacitatea) de a reprezenta sau aproxima funcții booleene prin polinoame este un concept central în teoria complexității, care stă la baza sistemelor de dovezi interactive și verificabile probabilistic, limitelor inferioare ale circuitelor, teoriei complexității cuantice și multe altele. În această carte, autorii analizează ceea ce se știe despre o noțiune deosebit de naturală de aproximare prin polinoame, care surprinde aproximarea punctuală pe numere reale.

Această carte acoperă progresele recente privind demonstrarea limitelor inferioare și superioare ale gradului de aproximare și descrie unele aplicații ale noilor limite la separările oracolelor, interogarea cuantică și complexitatea comunicării, precum și complexitatea circuitelor. Autorii explică modul în care mai multe dintre aceste progrese au fost deblocate de o tehnică deosebit de simplă și elegantă, numită compoziția blocului dual, pentru construirea soluțiilor la acest program liniar dual. Ei oferă, de asemenea, o acoperire concisă a tehnicilor și mai recente de delimitare inferioară bazate pe o nouă măsură de complexitate numită sensibilitate spectrală. În cele din urmă, ei arată cum construcțiile explicite de polinoame aproximative au fost inspirate de algoritmi cuantici de interogare.

Această carte oferă o revizuire cuprinzătoare a fundamentelor și a evoluțiilor recente ale unui subiect important atât în calculul clasic, cât și în cel cuantic. Cititorul dispune de un ansamblu considerabil de cunoștințe condensate într-o formă accesibilă pentru a înțelege rapid principiile și pentru a-și continua propriile cercetări.