Kwantowa złożoność hamiltonowska

Oryginalny tytuł:

Quantum Hamiltonian Complexity

Zawartość książki:

Problemy satysfakcji z ograniczeń są centralnym filarem współczesnej teorii złożoności obliczeniowej. Niniejsza monografia stanowi wprowadzenie do szybko rozwijającej się dziedziny Quantum Hamiltonian Complexity (QHC), która obejmuje badanie kwantowych problemów spełniania ograniczeń.

W ciągu ostatniego półtorej dekady dziedzina ta była świadkiem fundamentalnych przełomów, począwszy od ustanowienia kwantowego twierdzenia Cooka-Levina, a skończywszy na głębokim wglądzie w strukturę 1D niskotemperaturowych układów kwantowych za pomocą tak zwanych praw powierzchniowych. Quantum Hamiltonian Complexity zapewnia czytelnikowi wprowadzenie do tematu zorientowane na informatykę, aby pomóc w pokonaniu bariery językowej między informatykami a fizykami w tej dziedzinie. W związku z tym zawiera następujące elementy: (1) motywacje i historię dziedziny, (2) glosariusz terminów fizyki materii skondensowanej wyjaśniony w języku przyjaznym dla informatyków, (3) przeglądy głównych idei z fizyki materii skondensowanej, takich jak nierozróżnialne cząstki, średnia teoria pola, sieci tensorowe i prawa obszarowe oraz (4) krótkie ekspozycje wybranych wyników opartych na informatyce w tej dziedzinie.

Na przykład, w ramach tego ostatniego, zawiera nowatorską prezentację algorytmu wielomianowego Bravyi'ego dla Quantum 2-SAT. Quantum Hamiltonian Complexity zawiera przegląd niektórych z najbardziej fundamentalnych wyników w QHC i jest idealnym źródłem informacji dla informatyków z niewielkim lub żadnym doświadczeniem w dziedzinie informacji kwantowej.