Približný stupeň v klasickom a kvantovom počítaní

Pôvodný názov:

Approximate Degree in Classical and Quantum Computing

Obsah knihy:

Schopnosť (alebo neschopnosť) reprezentovať alebo aproximovať boolovské funkcie polynómami je ústredným pojmom v teórii zložitosti, na ktorom sú založené interaktívne a pravdepodobnostne kontrolovateľné dôkazové systémy, dolné hranice obvodov, teória kvantovej zložitosti a ďalšie. V tejto knihe autori skúmajú, čo je známe o obzvlášť prirodzenom pojme aproximácie polynómami, ktorý zachytáva bodovú aproximáciu v reálnych číslach.

Táto kniha sa zaoberá nedávnym pokrokom v dokazovaní približných dolných a horných hraníc stupňov a opisuje niektoré aplikácie nových hraníc na oddeľovanie veštieb, kvantovú zložitosť dotazov a komunikácie a zložitosť obvodov. Autori vysvetľujú, ako sa viaceré z týchto pokrokov podarilo odomknúť pomocou mimoriadne jednoduchej a elegantnej techniky, nazývanej duálna bloková kompozícia, na konštrukciu riešení tohto duálneho lineárneho programu. Poskytujú tiež stručné pokrytie ešte novších techník dolných hraníc založených na novej miere zložitosti nazývanej spektrálna citlivosť. Nakoniec ukazujú, ako sa explicitné konštrukcie aproximujúcich polynómov inšpirovali kvantovými algoritmami dotazovania.

Táto kniha poskytuje ucelený prehľad o základoch a najnovšom vývoji dôležitej témy v oblasti klasických aj kvantových počítačov. Čitateľ má k dispozícii značné množstvo poznatkov zhustených do prístupnej formy, aby rýchlo pochopil princípy a mohol pokračovať vo vlastnom výskume.