13 de septiembre de 2017

En Praga unificando paradigmas para tratar el no clonado en lenguajes cuánticos

En este post les quiero contar de un nuevo paper que acaba de ser aceptado en el 6th International Conference on Theory and Practice of Natural Computing (TPNC 2017) que tendrá lugar en Praga (República Checa) del 18 al 20 de diciembre. Este paper lo co-autoreamos con Gilles Dowek, del Inria y la ENS Paris-Saclay (Francia). El preprint (con un extenso apéndice) lo pueden descargar desde arXiv:1601.04294, y el paper pronto va a estar disponible en LNCS. Aquí les dejo el título y resumen, y luego una explicación más amena.

Typing quantum superpositions and measurement

Alejandro Díaz-Caro & Gilles Dowek
(aceptado en TPNC, Praga, República Checa, 18-20 de diciembre de 2017)
We propose a way to unify two approaches of non-cloning in quantum lambda-calculi. The first approach is to forbid duplicating variables, while the second is to consider all lambda-terms as algebraic-linear functions. We illustrate this idea by defining a quantum extension of first-order simply-typed lambda-calculus, where the type is linear on superposition, while allows cloning base vectors. In addition, we provide an interpretation of the calculus where superposed types are interpreted as vector spaces and non-superposed types as their basis.
Explicación más amena: Hay dos maneras en la literatura de evitar el clonado de qubits (algo que prohíbe la física cuántica): Una manera es evitar que los programas utilicen sus argumentos más de una vez. De esa manera nos aseguramos de que ningún programa duplicará su argumento, y por lo tanto no podrá clonar. Para eso se utiliza lógica lineal. La otra manera es considerar que los programas distribuyen linealmente sobre las superposiciones, y así, aunque el programa clone su argumento, no clonará una superposición cuántica sino simplemente los estados de base (y eso sí es permitido). La segunda idea parece la más lógica, sin embargo, si el programa por ejemplo tienen que tomar un argumento y medirlo, esa solución no nos sirve, ya que no tomará la superposición cuántica para medirla, sino que entrará linealmente en la superposición y simplemente medirá los estados de base. La solución que proponemos acá es un híbrido de ambos: las funciones que deben tomar toda la superposición (por ejemplo para medirla), deben usar restricciones de lógica lineal (no duplicar su argumento), las otras funciones, simplemente usan álgebra lineal y distribuyen sobre el argumento.