Approximate Degree in Classical and Quantum Computing
A Boole-függvények polinomokkal való reprezentálásának vagy közelítésének képessége (vagy képtelensége) a komplexitáselmélet központi fogalma, amely az interaktív és valószínűségileg ellenőrizhető bizonyítási rendszerek, az áramkörök alsó határai, a kvantumkomplexitás-elmélet és sok más fogalom alapjául szolgál. Ebben a könyvben a szerzők áttekintik, hogy mit tudunk a polinomokkal való közelítés egy különösen természetes fogalmáról, amely a valós számok feletti pontszerű közelítést ragadja meg.
Ez a könyv a közelítő fokú alsó és felső korlátok bizonyítása terén elért legújabb eredményeket tárgyalja, és ismerteti az új korlátok néhány alkalmazását a bábuelválasztások, a kvantum lekérdezési és kommunikációs bonyolultság, valamint az áramkörök bonyolultsága terén. A szerzők elmagyarázzák, hogy ezen előrelépések közül többet egy különösen egyszerű és elegáns technikával, az úgynevezett duális blokkkompozícióval sikerült feloldani, amely e duális lineáris program megoldásainak megkonstruálására szolgál. Emellett tömören ismertetik a még újabb, spektrális érzékenységnek nevezett új komplexitási mértékre épülő alsó korlátos technikákat is. Végül bemutatják, hogy a közelítő polinomok explicit konstrukcióit hogyan inspirálták a kvantum lekérdezési algoritmusok.
Ez a könyv átfogó áttekintést nyújt a klasszikus és a kvantumszámítástechnika egyik fontos témakörének alapvető és legújabb fejleményeiről. Az olvasó jelentős ismeretanyagot sűrített, közérthető formában kap az alapelvek gyors megértéséhez és saját kutatásai továbbviteléhez.