Gutes Einführungsmaterial zu Quantencomputer-Komplexitätsklassen

10

Ich möchte mehr über rechnerische Komplexitätsklassen im Kontext des Quantencomputers erfahren.

Das Medium ist nicht so wichtig; Es kann sich um ein Buch, Online-Vorlesungsunterlagen oder ähnliches handeln. Am wichtigsten sind die Inhalte.

Das Material sollte die Grundlagen von Quantencomputer-Komplexitätsklassen abdecken und die Ähnlichkeiten, Unterschiede und Beziehungen zwischen ihnen und möglicherweise auch mit klassischen Computerkomplexitätsklassen diskutieren.

Ich würde eine strenge Behandlung einer intuitiven vorziehen. Der Stil des Autors spielt keine Rolle.

Was die Voraussetzungen betrifft, weiß ich so gut wie nichts über das Thema, daher wäre vielleicht mehr in sich geschlossenes Material besser. Davon abgesehen würde ich wahrscheinlich kein 1000-Seiten-Buch lesen, wenn es nicht phänomenal gut wäre. Alles im Bereich von 1 bis 500 Seiten könnte funktionieren.

In Bezug auf die Verfügbarkeit würde ich natürlich Material bevorzugen, das sich nicht hinter einer Paywall befindet und online verfügbar ist, aber dies ist keine strenge Anforderung.

Was empfehlen Sie?

complexity-theory resource-request Kiro
quelle
Im Allgemeinen wird das Einholen von Empfehlungen für eine Klasse oder andere Materialien nicht zum Thema einer Stack Exchange-Site betrachtet. Abgesehen von diesem Thema geht es in Ihrem Beitrag nicht wirklich um das Thema "Quantencomputer". Das Unterrichten der Konzepte der rechnerischen Komplexität passt besser zu unserer Website für Informatik .
Robert Cartaino
@ RobertCartaino Vielen Dank für das Feedback, lassen Sie mich versuchen, Ihre Punkte anzusprechen. Ich habe Material zum Selbststudium angefordert, und afaik- Ressourcenanfragen sind innerhalb von Parametern zulässig . Ich werde mein Bestes geben, um die Frage so zu ändern, dass sie zum Thema gehört.
Kiro
1
@MEE Außer, dass Sie den Kern dieses nicht zum Thema gehörenden Themas beschönigt haben - das Unterrichten der Grundlagen der Komplexität von Berechnungen ist nur ein Zufall für das Fachwissen des Quantencomputers. Ich nenne das "das Lieblingsgetränk der Programmierer" . Es handelt sich um ein Informatikproblem, bei dem das Hinzufügen von "im Kontext des Quantencomputers" in diesem Fall nicht mehr zum Thema führt. Ganz gleich; Der Benutzer hat keine Frage zu diesem Thema und möchte einfach woanders hingehen, um diese Informationen zu finden. Was auch immer Sie sich entscheiden.
Robert Cartaino
@ RobertCartaino ok, ich verstehe deinen Standpunkt jetzt, ich habe den Schließungsgrund falsch verstanden. Daher möchte ich meine Wiedereröffnungsabstimmung jetzt zurückziehen, aber da dies nicht möglich ist, habe ich dafür gestimmt, diese Frage zu schließen.
MEE - Stellen Sie Monica am
1
@RobertCartaino "Die Grundlagen der rechnerischen Komplexität sind nur ein Zufall für das Fachwissen des Quantencomputers." Ich stimme zu, dass die "Grundlagen" zusammenfallen, aber ich denke, dass die derzeit gestellte Frage thematisch genug ist, dass ich mich auf Vorlesungsunterlagen beziehen kann Quantencomputer als Antwort. Ich bin damit einverstanden, dass die vorherige Version tatsächlich ein Fall von " dem Lieblingsgetränk der Programmierer " wäre, aber ich denke, das ist inzwischen gelöst.
Diskrete Eidechse

Antworten:

7

Ich denke, die Umfrage von John Watrous ist ein großartiger Ausgangspunkt (Professor Watrous hat sie mir vor langer, langer Zeit empfohlen und ich bin seitdem begeistert!):

J. Watrous. Quantenberechnungskomplexität. Encyclopedia of Complexity and System Science, Springer, 2009. arXiv: 0804.3401 [quant-ph]

Nach meinem besten Wissen hat es das höchste Verhältnis von Komplexitätsklassen zu Seiten.

Ich mag auch Scott Aaronsons Barbados Lecture Notes 2016 sehr:

S. Aaronson (mit A. Bouland und L. Schaeffer). Die Komplexität von Quantenzuständen und Transformationen: Vom Quantengeld zu schwarzen Löchern. ECCC TR16-109

Sanketh Menda
quelle
3

Ich kann die Vorlesungsunterlagen von Ronald de Wolf empfehlen , die für einen Semesterkurs verwendet werden, den er im Rahmen des niederländischen Mastermath-Programms über Quantencomputer unterrichtet.

Kapitel 10 "Quantenkomplexitätstheorie" behandelt kurz die "klassischen" Komplexitätsklassen, bietet jedoch genügend Hintergrundinformationen, um über die "Quantenkomplexitätsklassen" zu sprechen und sie mit den klassischen zu vergleichen. Es deckt nicht alles ab, sondern verweist auf anderes Material zur weiteren Lektüre.

Kapitel 12 "Quantenkommunikationskomplexität" ist ebenfalls relevant und technischer, hauptsächlich da die Theorie der Kommunikationskomplexität interessante Anwendungen innerhalb der Quantenberechnung hat.

Diskrete Eidechse
quelle