Recursos para la complejidad de la comunicación cuántica

8

Hace poco conocí este interesante tema de " complejidad de la comunicación ". En palabras simples, Wikipedia lo define como:

En la informática teórica, la complejidad de la comunicación estudia la cantidad de comunicación requerida para resolver un problema cuando la entrada al problema se distribuye entre dos o más partes. Fue presentado por Andrew Yao en 1979, quien investigó el siguiente problema que involucra a dos partes separadas, tradicionalmente llamadas Alice y Bob. Alice recibe una cadena de n bits y Bob otra n cadena de bits y , y el objetivo es que uno de ellos (dice Bob) para calcular una función determinada f ( x , y )xnyf(x,y)con la menor cantidad de comunicación entre ellos. Por supuesto, siempre pueden tener éxito si Alice envía toda su cadena de n bits a Bob, quien luego calcula la función , pero la idea aquí es encontrar formas inteligentes de calcular f con menos de n bits de comunicación. Tenga en cuenta que en la complejidad de la comunicación, no nos preocupa la cantidad de cómputo realizado por Alice o Bob, ni el tamaño de la memoria utilizada.ff

Ahora, estaba revisando las primeras páginas de este artículo: " Complejidad de comunicación cuántica (una encuesta) - Brassard ". Aparentemente, parece que si las partes que no se comunican están previamente enredadas, entonces se pueden comunicar más bits de información que en el caso clásico. El periódico se ve bien, así que leeré más. Sin embargo, ¿hay otros documentos o textos importantes que sean "lecturas obligatorias" al aprender sobre la "complejidad de la comunicación cuántica"? (Estoy principalmente interesado en el lado teórico / algorítmico)

Sanchayan Dutta
fuente

Respuestas:

5

Un avance reciente que no está cubierto en esa encuesta son las hojas de trucos . Ver,

Separaciones en la complejidad de la comunicación utilizando hojas de trucos y complejidad de la información ; Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee y Miklos Santha; arXiv: 1605.01142 [cuant-ph]

Puede ser una buena idea familiarizarse primero con el marco de la hoja de trucos.

Separaciones en la complejidad de la consulta utilizando hojas de trucos ; Scott Aaronson, Shalev Ben-David, Robin Kothari; arXiv: 1511.01937 [cuant-ph]

Personalmente, me gusta pensar en la complejidad de la consulta en su conjunto en lugar de especializarme en la complejidad de la comunicación. Una gran cantidad de teoremas de la complejidad consulta tradicional puede ser levantada en la complejidad de comunicación, y de hecho eso es lo que hacen en el papel por encima.

Sanketh Menda
fuente