Dobry materiał wprowadzający na temat kwantowych klas złożoności obliczeniowej

10

Chciałbym dowiedzieć się więcej o klasach złożoności obliczeniowej w kontekście obliczeń kwantowych.

Medium nie jest tak ważne; może to być książka, notatki z wykładów online lub tym podobne. Najważniejsza jest zawartość.

Materiał powinien obejmować podstawy kwantowych klas złożoności obliczeniowej i omawiać podobieństwa, różnice i relacje między nimi, a być może także klasyczne klasy złożoności obliczeniowej.

Wolałbym rygorystyczne traktowanie niż intuicyjne. Styl autora nie ma znaczenia.

Jeśli chodzi o warunki wstępne, nie wiem prawie nic na ten temat, więc może więcej samodzielnych materiałów byłoby lepszych. Biorąc to pod uwagę, prawdopodobnie nie przeczytałbym książki na 1000 stron, chyba że byłaby fenomenalnie dobra, wszystko w zakresie 1-500 stron mogłoby działać.

Jeśli chodzi o dostępność, wolałbym oczywiście materiał, który nie znajduje się za jakąś zaporą i można go znaleźć w Internecie, ale nie jest to ścisły wymóg.

Co polecasz?

complexity-theory resource-request Kiro
źródło
Ogólnie rzecz biorąc, pozyskiwanie rekomendacji dla klasy lub innych materiałów nie jest rozważane w temacie witryny Stack Exchange; ale pomijając ten problem, temat Twojego wpisu tak naprawdę nie dotyczy tematu „obliczeń kwantowych”. Nauczanie pojęć złożoności obliczeniowej lepiej pasuje do naszej strony z informatyki .
Robert Cartaino,
@RobertCartaino Dziękuję za opinię, pozwól mi spróbować zająć się swoimi punktami. Prosiłam o materiały do ​​samokształcenia, a afaikowe prośby o zasoby są dozwolone w ramach parametrów . Postaram się jak najlepiej zmodyfikować pytanie, aby było na dany temat.
Kiro,
1
@MEE Tyle, że nie zastanawiałeś się nad sednem tego tematu - nauczanie podstaw złożoności obliczeniowej jest po prostu zbieżne z doświadczeniem w dziedzinie obliczeń kwantowych. Nazywam to problemem „ulubionego napoju dla programistów” . Jest to kwestia informatyki, w której dodanie „w kontekście obliczeń kwantowych” nie czyni z tego żadnego problemu na ten temat w tym przypadku. Bez znaczenia; użytkownik nie ma pytania na ten temat i po prostu chce udać się gdzie indziej, aby znaleźć te informacje. Cokolwiek zdecydujesz.
Robert Cartaino,
@RobertCartaino ok, rozumiem teraz twój punkt, źle zrozumiałem powód zamknięcia. W związku z tym chciałbym wycofać mój ponownie otwarty głos, ale ponieważ nie jest to możliwe, głosowałem za zamknięciem tego pytania.
MEE - Przywróć Monikę
1
@RobertCartaino „podstawy złożoności obliczeniowej są po prostu zbieżne ze specjalistyczną wiedzą z zakresu obliczeń kwantowych”. Zgadzam się, że „podstawy” są zbieżne, ale myślę, że pytanie, które jest obecnie zadawane, jest wystarczająco tematyczne, że mogę odnieść się do notatek z wykładów na temat obliczenia kwantowe jako odpowiedź. Zgadzam się, że poprzednia wersja rzeczywiście byłaby przypadkiem „ ulubionego napoju dla programistów ”, ale myślę, że do tej pory została rozwiązana.
Dyskretna jaszczurka

Odpowiedzi:

7

Myślę, że ankieta Johna Watrousa jest świetnym miejscem do rozpoczęcia (profesor Watrous polecił mi ją dawno temu i od tego czasu jestem uzależniony!):

J. Watrous. Kwantowa złożoność obliczeniowa. Encyklopedia złożoności i nauki o systemie, Springer, 2009. arXiv: 0804.3401 [quant-ph]

Według mojej najlepszej wiedzy, ma on najwyższy stosunek klas złożoności do strony.

Bardzo podoba mi się też Notatka z wykładu Barbados 2016 Scotta Aaronsona:

S. Aaronson (z A. Bouland i L. Schaeffer). Złożoność stanów kwantowych i transformacji: od pieniędzy kwantowych do czarnych dziur. ECCC TR16-109

Sanketh Menda
źródło
3

Mogę polecić notatki z wykładu Ronalda de Wolfa, wykorzystane podczas semestralnego kursu wykładanego przez niego na temat obliczeń kwantowych w kontekście holenderskiego programu „Mastermath”.

Rozdział 10 „Teoria złożoności kwantowej”, krótko omawia „klasyczne” klasy złożoności, ale daje wystarczające podstawy do rozmowy o klasach złożoności „kwantowej” i porównania ich z klasycznymi. Nie obejmuje wszystkiego, ale odnosi się do innych materiałów do dalszego czytania.

Rozdział 12 „Złożoność komunikacji kwantowej” jest również istotny i bardziej techniczny, głównie dlatego, że do teorii złożoności komunikacji ma interesujące zastosowania w obliczeniach kwantowych.

Dyskretna jaszczurka
źródło