Approximate Degree in Classical and Quantum Computing
Die Fähigkeit (oder Unfähigkeit), boolesche Funktionen durch Polynome darzustellen oder zu approximieren, ist ein zentrales Konzept in der Komplexitätstheorie, das interaktiven und probabilistisch überprüfbaren Beweissystemen, unteren Schranken für Schaltkreise, der Quantenkomplexitätstheorie und mehr zugrunde liegt. In diesem Buch geben die Autoren einen Überblick darüber, was über einen besonders natürlichen Begriff der Approximation durch Polynome bekannt ist, der die punktweise Approximation über die reellen Zahlen erfasst.
Das Buch behandelt die jüngsten Fortschritte beim Nachweis von unteren und oberen Schranken für Näherungsgrade und beschreibt einige Anwendungen der neuen Schranken für Orakelseparationen, Quantenabfrage- und Kommunikationskomplexität sowie Schaltkreiskomplexität. Die Autoren erklären, wie mehrere dieser Fortschritte durch eine besonders einfache und elegante Technik, die so genannte duale Blockkomposition, zur Konstruktion von Lösungen für dieses duale lineare Programm erschlossen wurden. Sie beschreiben auch kurz und bündig neuere Techniken zur unteren Schranke, die auf einem neuen Komplexitätsmaß namens spektrale Sensitivität basieren. Schließlich zeigen sie, wie explizite Konstruktionen von approximierenden Polynomen durch Quantenabfragealgorithmen inspiriert wurden.
Dieses Buch bietet einen umfassenden Überblick über die grundlegenden und jüngsten Entwicklungen eines wichtigen Themas sowohl im klassischen als auch im Quantencomputing. Dem Leser wird ein beträchtlicher Wissensschatz in einer zugänglichen Form zur Verfügung gestellt, damit er die Prinzipien schnell verstehen und seine eigene Forschung vorantreiben kann.
| ISBN: | 9781638281405 |
| Autor: | |
| Verlag: | |
| Sprache: | Englisch |
| Einband: | Taschenbuch |
Derzeit verfügbar, auf Lager.
