Deseo aprender más sobre las clases de complejidad computacional en el contexto de la computación cuántica.
El medio no es tan importante; podría ser un libro, notas de conferencias en línea o similares. Lo que más importa son los contenidos.
El material debe cubrir los conceptos básicos de las clases de complejidad computacional cuántica y discutir las similitudes, diferencias y relaciones entre ellos y quizás también con las clases clásicas de complejidad computacional.
Preferiría un tratamiento riguroso sobre uno intuitivo. El estilo del autor no importa.
En cuanto a los requisitos previos, no sé casi nada sobre el tema, por lo que tal vez sería mejor un material más autónomo. Dicho esto, probablemente no leería un libro de 1000 páginas a menos que fuera fenomenalmente bueno, cualquier cosa en el rango de 1-500 páginas podría funcionar.
En cuanto a disponibilidad, por supuesto, preferiría material que no esté detrás de un muro de pago de algún tipo y se pueda encontrar en línea, pero este no es un requisito estricto.
¿Que recomiendas?
Respuestas:
Creo que la encuesta de John Watrous es un gran lugar para comenzar (¡el profesor Watrous me la recomendó hace mucho tiempo y me he enganchado desde entonces!):
J. Watrous. Complejidad computacional cuántica. Enciclopedia de la complejidad y la ciencia del sistema, Springer, 2009. arXiv: 0804.3401 [quant-ph]
Que yo sepa, tiene las clases de complejidad más alta para la relación de página.
También me gusta mucho las notas de la conferencia de Barbados 2016 de Scott Aaronson:
S. Aaronson (con A. Bouland y L. Schaeffer). La complejidad de los estados cuánticos y las transformaciones: del dinero cuántico a los agujeros negros. ECCC TR16-109
fuente
Puedo recomendar las notas de la conferencia de Ronald de Wolf, utilizadas para un curso semestral impartido por él en Quantum Computing en el contexto del programa holandés "Mastermath".
El capítulo 10, "Teoría de la complejidad cuántica", cubre brevemente las clases de complejidad "clásicas", pero ofrece suficientes antecedentes para hablar sobre las clases de complejidad "cuánticas" y compararlas con las clásicas. No cubre todo, pero se refiere a otro material para leer más.
El capítulo 12 "Complejidad de la comunicación cuántica" también es relevante y es más técnico, principalmente porque la teoría de la complejidad de la comunicación tiene aplicaciones interesantes dentro de la computación cuántica.
fuente