Grado Aproximado en Computación Clásica y Cuántica

Título original:

Approximate Degree in Classical and Quantum Computing

Contenido del libro:

La capacidad (o incapacidad) de representar o aproximar funciones booleanas mediante polinomios es un concepto central en la teoría de la complejidad, que subyace a los sistemas de prueba interactivos y comprobables probabilísticamente, a los límites inferiores de circuitos, a la teoría de la complejidad cuántica y a otros. En este libro, los autores estudian lo que se sabe sobre una noción particularmente natural de aproximación por polinomios, que captura la aproximación puntual sobre los números reales.

Este libro cubre los avances recientes en la demostración de límites inferiores y superiores de grados aproximados y describe algunas aplicaciones de los nuevos límites a las separaciones de oráculos, la complejidad cuántica de las consultas y las comunicaciones, y la complejidad de los circuitos. Los autores explican cómo varios de estos avances han sido desbloqueados por una técnica particularmente simple y elegante, llamada composición dual de bloques, para construir soluciones a este programa lineal dual. También proporcionan una cobertura concisa de técnicas aún más recientes de límites inferiores basadas en una nueva medida de complejidad llamada sensibilidad espectral. Por último, muestran cómo las construcciones explícitas de polinomios de aproximación se han inspirado en algoritmos cuánticos de consulta.

Este libro ofrece una revisión exhaustiva de los fundamentos y desarrollos recientes de un tema importante tanto en la informática clásica como en la cuántica. El lector dispone de un considerable corpus de conocimientos condensados de forma accesible para comprender rápidamente los principios y avanzar en su propia investigación.