Przybliżony stopień w obliczeniach klasycznych i kwantowych

Oryginalny tytuł:

Approximate Degree in Classical and Quantum Computing

Zawartość książki:

Zdolność (lub niezdolność) do reprezentowania lub przybliżania funkcji boolowskich za pomocą wielomianów jest centralnym pojęciem w teorii złożoności, leżącym u podstaw interaktywnych i probabilistycznie sprawdzalnych systemów dowodowych, dolnych granic obwodów, teorii złożoności kwantowej i nie tylko. W tej książce autorzy dokonują przeglądu tego, co wiadomo na temat szczególnie naturalnego pojęcia aproksymacji wielomianami, obejmującego punktową aproksymację na liczbach rzeczywistych.

W książce omówiono najnowsze postępy w dowodzeniu dolnych i górnych ograniczeń stopnia przybliżonego oraz opisano niektóre zastosowania nowych ograniczeń do separacji wyroczni, kwantowej złożoności zapytań i komunikacji oraz złożoności obwodów. Autorzy wyjaśniają, w jaki sposób kilka z tych postępów zostało odblokowanych dzięki szczególnie prostej i eleganckiej technice, zwanej podwójną kompozycją blokową, do konstruowania rozwiązań tego podwójnego programu liniowego. W zwięzły sposób omawiają także najnowsze techniki wyznaczania dolnej granicy na podstawie nowej miary złożoności zwanej wrażliwością spektralną. Na koniec pokazują, w jaki sposób jawne konstrukcje wielomianów aproksymujących zostały zainspirowane kwantowymi algorytmami zapytań.

Niniejsza książka stanowi kompleksowy przegląd podstawowych i najnowszych osiągnięć w ważnym temacie zarówno w obliczeniach klasycznych, jak i kwantowych. Czytelnik ma do dyspozycji znaczną ilość wiedzy skondensowanej w przystępnej formie, aby szybko zrozumieć zasady i kontynuować własne badania.