Cambalache 3,14 - La vidriera irrespetuosa

Grafos para la Física Cuántica (I)

Desde hace unos quince años mi investigación está centrada en la Teoría de Grafos. Un grafo es un ejemplo de esos conceptos que todo el mundo usa intuitivamente y que demuestran su enorme potencial cuando caen en manos de la Matemática.

Todos hemos usado grafos alguna u otra vez. Formalmente decimos que un grafo es un par de conjuntos: vértices y aristas, de forma que las aristas son pares de puntos. Solemos representarlos (y aquí los reconoceréis) pintando los vértices como puntos (o como figuras representativas) y las aristas como líneas rectas o curvas uniendo los puntos. Aquí al lado tenéis un ejemplo, sacado de Pisito en Madrid. el problema de los tres suministros

. Por supuesto, esta no es la única forma de representar grafos, hay muchas más, pero son menos usadas. Una de las más curiosas es representar los vértices mediante círculos, de modo que una arista se representa por el contacto entre dos discos/vértices. Acabamos de mandar un artículo al Journal of Graph Algorithms and Applications donde exploramos las distintas posibilidades de esta representación si los círculos (discos, en la jerga profesional) deben colocarse tapando ciertas semillas en determinados puntos del plano. De ese artículo he sacado la imagen que acompaña estas líneas y que espero aclare un poco lo que estoy contando.

Hay mucha literatura sobre grafos a nivel de iniciación y muy buenas páginas web divulgativas. Sin ir más lejos, la parte de la wikipedia en español dedicada a esta disciplina mejora por semanas y ya es un buen punto de iniciación, si estás interesado/a.

Hará ya casi siete años que Adán Cabello estuvo buscando, a través de mi compañera de departamento y compañera suya de escuela Mª José Chaves alguien que pudiera ayudarle a aplicar la Teoría de Grafos a ciertos problemas de la Mecánica Cuántica. Como aquí el que suscribe se apunta a un bombardeo (y hasta a un tsunami), pues me ofrecí voluntario y gracias a eso hemos trabajado en varias interdisciplinariedades (y seguimos haciéndolo).

La última de ellas es una medida de la contextualidad de las proposiciones. En un mundo regido por la lógica binaria (booleana) clásica, una serie de frases pueden representarse mediante un grafo: cada vértice sería una frase (proposición, en el lenguaje lógico) y dos vértice-frases estarían ligados por una arista si fueran incompatibles entre sí. Por ejemplo, la frase Ahora hace 30 grados y Pedro tiene un C.I. de 95 es incompatible con Está helando y Pedro tiene un C.I. de 95.

numero de independencia

En cualquier grupo de proposiciones (lo que podemos llamar, un poco presuntuosamente una teoría) hay un número máximo de frases que pueden ser ciertas simultáneamente. No es difícil ver que esto se corresponde con el número de independencia del grafo correspondiente a la teoría. En efecto, el número de independencia de un grafo es el máximo número de vértices que no son mutuamente adyacentes Se representa por la letra griega &alfa;. Por ejemplo, en el grafo de la figura adjunta, el número de independencia es α=2 pues los vértices 2 y 4 son independientes y no podemos encontrar ningún grupo de tres o más vértices que lo sean. En este sentido, el número de independencia de un grafo de proposiciones en lógica clásica mide, en cierto modo, la cantidad máxima de verdad que puede contener ese grafo.

La cuestión es que si no estamos trabajando con lógica booleana, las cosas no funcionan de ese modo. Recordemos el gato de Schrödinger, que puede estar vivo o muerto simultáneamente en un mundo cuántico (esto no es exactamente así, pero me vale como ejemplo). En ese caso, las frases el gato vive y el gato no vive que son incompatibles en lógica clásica, no lo son en una teoría cuántica.

Para medir la cantidad de verdad (y de nuevo esto es una licencia poética para entendernos mejor) de una teoría cuántica, el número de independencia del grafo correspondiente no nos sirve. Tenemos que acudir a otra medida, a otro invariante del grafo. Y nuestro candidato es ahora la función θ de Lovász. θ es una cota superior de la capacidad de Shannon de un grafo que viene definida como

. La capacidad de Shannon de un grafo es mayor que su número de independencia y por tanto se verija que α < θ

Sin embargo, para nosotros θ tiene una característica que la hace destacar. El año pasado, Adán Cabello junto con científicos de trabajando en Londres, Tsinghua y Singapur, propuso θ como medida de la violación máxima de ciertas desigualdades nocontextuales. Para simplificar, podríamos pensar que θ mide la cantidad de verdad en una teoría cuántica. Teoría en el sentido de un grupo de afirmaciones.

Si tenemos un grafo escogido más o menos al azar, representando una teoría, pueden ocurrir dos cosas: que su número de independencia α sea igual a la función θ en ese grafo o que esta última sea mayor. Si son iguales, el grafo no es interesante desde un punto de vista cuántico, porque la cantidad de verdad que transmite cuánticamente hablando es la misma cantidad de verdad que transmite en el aburrido mundo clásico de las proposiciones booleanas. En cambio, si en un grafo concreto tenemos α < θ el grafo será cuánticamente interesante porque puede ayudarnos a encontrar desigualdades no contextuales con violación cuántica…, ejem, puede ayudarnos a formular teoremas y encontrar resultados en mecánica cuántica.

El primer grafo cuántico que encontramos es el pentágono o ciclo de orden 5.

Tiene número de independencia dos y su θ vale √ 5 . Decimos que es el primer grafo cuántico, en el sentido de que es el más sencillo (con menos vértices y/o aristas).

A partir de aquí podemos hacernos multitud de preguntas sobre grafos cuánticos: ¿hay infinitos? Si no, ¿cuantos hay?. ¿Cómo son? ¿Podemos identificarlos? ¿Tiene propiedades comunes? ¿Todos ellos contienen pentágonos? Si no es así ¿hay alguna familia, finita o infinita, de grafos contenidos en todos los grafos cuánticos? O. al revés ¿hay subgrafos prohibidos, es decir, que si están en un grafo hacen que este no sea cuántico? ¿Hay grafos más cuánticos que otros? ¿Cómo medir la cuanticidad de un grafo? ¿Cómo son los invariantes de los grafos cuánticos? ¿Cuanto valen su cintura, radio, diámetro, índice de conexión, colorabilidad, número de clique, vertex cover,…?

Algunas de estas preguntas os la responderé en próximos entregas de esta serie. Otras las estamos investigando. Y hay una muy importante que dejo intencionadamente en el tintero por ahora. Comentarios, en los comentarios.