Titre original :
Approximate Degree in Classical and Quantum Computing
Contenu du livre :
La capacité (ou l'incapacité) de représenter ou d'approximer des fonctions booléennes par des polynômes est un concept central de la théorie de la complexité, qui sous-tend les systèmes de preuve interactifs et vérifiables de manière probabiliste, les limites inférieures des circuits, la théorie de la complexité quantique, et bien d'autres choses encore. Dans cet ouvrage, les auteurs font le point sur les connaissances relatives à une notion particulièrement naturelle d'approximation par des polynômes, capturant l'approximation ponctuelle sur les nombres réels.
Ce livre couvre les progrès récents dans la démonstration des limites inférieures et supérieures des degrés approximatifs et décrit quelques applications des nouvelles limites aux séparations d'oracles, à la complexité quantique des requêtes et des communications, et à la complexité des circuits. Les auteurs expliquent comment plusieurs de ces progrès ont été réalisés grâce à une technique particulièrement simple et élégante, appelée composition de blocs duaux, pour construire des solutions à ce programme linéaire dual. Ils fournissent également une couverture concise des techniques de limites inférieures encore plus récentes basées sur une nouvelle mesure de complexité appelée sensibilité spectrale. Enfin, ils montrent comment les constructions explicites de polynômes approximatifs ont été inspirées par les algorithmes quantiques.
Ce livre fournit un examen complet des fondements et des développements récents d'un sujet important de l'informatique classique et quantique. Le lecteur dispose d'un ensemble considérable de connaissances condensées sous une forme accessible pour comprendre rapidement les principes et poursuivre ses propres recherches.
Autres informations sur le livre :
| ISBN : | 9781638281405 |
| Auteur : | |
| Éditeur : | |
| Langue : | anglais |
| Reliure : | Broché |
Achat:
Actuellement disponible, en stock.
