Ez egy áttekintő jellegű előadás, amolyan bevezető a kvantum
bonyolultságelmelétbe. Eldobjuk azt a feltételezést, hogy a
hagyományos Turing géppel gyorsan megoldható problémákat tekintjük
hatékonynak, hanem ehelyett azokat amik kvantumszámítógéppel polinom
időben megoldhatóak. Ez egy sor új bonyolultsági osztályt hiv életre,
megteremtve ezzel a bonyolultságelmélet egy új ágát. Ebben az
előadásban két bonyolultsági osztályt tekintünk át. Röviden beszélünk
arról miket tekintünk polinom időben megoldható problémáknak (ez a P
kvantumos általánosítása). Az előadás nagy részében pedig azokról a
problémákról beszelünk amik hatékonyan bizonyíthatóak (ez az NP
általánosítása). Definiálni fogjuk a megfelelő osztályt és
megvizsgáljuk a különböző tulajdonságait. Látni fogunk példát ami arra
utal hogy a kvantumos osztály nem egyenlő a klasszikussal, és látni
fogunk a 3SAT-hoz hasonló teljes problémát is. Az idő függvényében
beszelünk a hibavalószínűség redukciójáról, illetve az osztály olyan
változatáról aminek már nincs klasszikus analógiája. Ebben a modellben
lehetőség van az NP-teljes problémák logaritmikus méretű tanúval
történő bizonyítására.

Az előadásban minden szükséges fogalmat definiálni fogunk, így csak
alapvető lineáris algebrai ismeretekre lesz szükség. A P, NP
bonyolultsági osztály ismerete előnyt jelent.