Quantum correlations and graphs

Abstract

Esta tesis doctoral trata de diversos aspectos de la teoría cuántica (TC), que abarcan desde el campo de los fundamentos de la disciplina (en particular, la búsqueda de un conjunto de principios que seleccionen y distingan a la TC en el panorama de las teorías probabilísticas generales) hasta el reino de las aplicaciones en información y computación cuánticas. Todos los problemas que hemos abordado en nuestra investigación tienen un rasgo distintivo común: la teoría de grafos parece ser especialmente adecuada para describirlos y tratarlos. Y no sólo eso: el lenguaje y las herramientas de la teoría de grafos proporcionan una poderosa y nueva percepción que permite arrojar luz sobre tales problemas, y representan además un importante impulso para futuros desarrollos. Precisamente, uno de los problemas que tuvimos que plantearnos en esta tesis, desde el primer momento, fue decidir su título. El alcance de la tesis era demasiado amplio como para poderlo comprimir en un título que fuese significativo, preciso y relativamente corto, y esto explica nuestra elección final: Quantum correlations and graphs, es decir,Correlaciones cuánticas y grafos, una declaración intencionadamente de amplio espectro y algo vaga con la que intentamos capturar los principales aspectos de nuestra investigación, quizá sin éxito. En lo que concierne a la alusión a los grafos en el título, la principal razón para nuestra concisión es la siguiente: la tesis está dividida en dos partes en las que los grafos constituyen la herramienta matemática ubicua y versátil sobre la cual hemos basado toda nuestra investigación. Sin embargo, hemos de hacer notar que los grafos significan cosas muy distintas y juegan papeles bien diferentes en cada parte de la tesis. En la Parte I, que está dedicada a los grafos de exclusividad de desigualdades no contextuales (NC), los grafos dan cuenta de experimentos en los cuales algunas medidas se llevan a cabo sobre ciertos estados: los vértices de uno de tales grafos representan eventos, en tanto que las aristas describen relaciones de exclusividad mutua entre eventos, y sobre la base de dichos grafos nosotros construimos desigualdades NC y calculamos sus valores límite a partir de algunos números combinatorios propios de los grafos. En la Parte II, que está dedicada específicamente a los denominados estados grafo, los grafos por el contrario representan estados cuánticos entrelazados de muchos qubits. El grafo no sólo proporciona una ayuda para escribir el generador del estado grafo, sino que también sirve por así decir como una plantilla o guía para su preparación: los vértices representan qubits, y las aristas describen subsiguientes operaciones de entrelazamiento cada una de la cuales involucra a dos qubits. Todo esto prueba cuán fructífera y versátil llega a ser la teoría de grafos cuando se aplica a algunos problemas fundamentales en TC, lo que constituye una de la principales ideas que alientan la tesis. Entre estas dos partes de la tesis, en apariencia desligadas, hay no obstante una profunda conexión, que se explica con detalle al final de la tesis. En pocas palabras: hay una construcción que partiendo de cualquier grafo conexo de tres o más vértices que describe a un estado grafo lleva a un grafo de mayor orden y tamaño, siendo ´este último un grafo de exclusividad cuyos vértices representan todos los posibles eventos consistentes con el grupo estabilizador del estado grafo original, y cuyas aristas conectan eventos mutuamente excluyentes. Tal procedimiento transcribe en términos de teoría de grafos la conexión existente entre un estado grafo y una desigualdad de Bell violada máximamente por la TC. Otro comentario importante tiene que ver con correlaciones cuánticas, el otro elemento que aparece con concisión en el título: proporcionamos una definición general de correlaciones cuánticas en la Sec. 1.2.4, a la que referimos al lector para más detalle. Nosotros seleccionamos dos tipos de correlaciones cuánticas: correlaciones cuánticas proyectivas, y correlaciones cuánticas tipo Bell. Debemos enfatizar el hecho de que en la primera parte de esta tesis, a menos que se diga expresamente lo contrario, por correlaciones cuánticas se entenderá que se trata de correlaciones cuánticas proyectivas, es decir, correlaciones entre los resultados demedidas conjuntas de observables cuánticos proyectivos. Las razones para esta elección se aportan en la p. 46. Por otro lado, nuestro principal interés en la segunda parte de la tesis es la clasificación y preparación óptima de estados grafo. En este caso, las correlaciones cuánticas (en particular, correlaciones cuánticas tipo Bell) aparecen implícitamente al discutir la conexión existente entre los grafos de exclusividad, los estados grafo y una clase de desigualdades de Bell violada máximamente por los estados grafo. Con todas estas consideraciones en mente, pasamos a continuación a hacer una descripción resumida de nuestro trabajo de investigación. La tesis que presentamos, como ha quedado dicho, está estructurada en dos partes: 1. La Parte I se titulaGrafos de exclusividad de desigualdades no contextuales, y está organizada en cuatro capítulos: • Capítulo 1:Aproximación a las correlaciones cuánticas mediante teoría de grafos. Éste es un capítulo introductorio, cuyo principal propósito es proporcionar el mínimo trasfondo teórico necesario para discutir los problemas y resultados de la primeraparte de la tesis, además de presentar nuestros primeros resultados más básicos. Comenzamos en la Sec. 1.1 con una descripción concisa y autocontenida del marcogeneral de las teorías operacionales, siguiendo las Refs. [1, 2]. Esta introducción concluye con la definición de exclusividad mutua entre eventos, en términos operacionales. Ello nos permite conectar la observación de Specker acerca de la mensurabilidad dos a dos y la mensurabilidad conjunta en TC con el principio de exclusividad(E), es decir, con el hecho de que la suma de las probabilidades de un conjunto de eventos mutuamente excluyentes dos a dos no puede exceder de 1. En la Sec. 1.2 pasamos revista a diferentes tipos de correlaciones entre resultados de medidas realizadas en un sistema, según las predicciones de ciertas teorías físicas. Seguimos las Refs. [3, 4, 5] en la discusión de las correlaciones locales, cuánticas, no-signalingand generales. Nos ocupamos de dos tipos de correlaciones cuánticas: proyectivas ytipo Bell, y seguidamente centramos nuestra atención en las correlaciones cuánticasproyectivas, proporcionando razones para dicha elección en la primera parte de la tesis. En la Sec. 1.3 definimos correlaciones no contextuales, e introducimos el concepto de desigualdad NC. La Sec. 1.4 se dedica a presentar la aproximación a las correlaciones cuánticas mediante teoría de grafos de Cabello-Severini-Winter (CSW), recogida en las Refs. [6, 7], atendiendo específicamente a dos resultados principales y varias propuestas de posible desarrollo ulterior de dichos autores, en las cuales se basa nuestra investigación. Presentamos nuestros primeros resultados básicos en la Sec. 1.5, relativos a la clasificación de los llamados grafos cuánticos contextuales (QCG), y concluimos resumiendo las conexiones entre esta clasificación y los problemas abordados en capítulos subsiguientes. • Capítulo 2: Grafos de exclusividad básicos en correlaciones cuánticas. En este capítulo nos ocupamos de un problema fundamental: entender por qué la TC viola únicamente ciertas desigualdades NC, e identificar los principios físicos que impiden violaciones mayores que las producidas por la TC. Utilizamos, como herramienta principal a lo largo del capítulo, el grafo de exclusividad de una desigualdad NC que ya se ha introducido previamente en la Sec. 1.4.2. En la Sec. 2.3, presentamos una condición necesaria para la existencia de correlaciones cuánticas contextuales: demostramos que la TC viola únicamente aquellas desigualdades NC cuyos grafos de exclusividad contienen, como subgrafos inducidos, ciclos impares de cinco o más vértices y/o sus complementos. En la Sec. 2.4, mostramos que se puede obtener una cota inferior de la dimensión (i. e., del número de estados perfectamente distinguibles) del sistema cuántico utilizado para violar la desigualdad NC mediante la identificación de subgrafos inducidos en el grafo de exclusividad de la desigualdad NC. El resultado de la Sec. 2.3 sugiere que las desigualdades NC cuyos grafos de exclusividad son o bien un ciclo impar o bien su complemento son especialmente importantes para entender la manera en que la TC viola desigualdades NC. En la Sec. 2.5 mostramos que los ciclos impares son los grafos de exclusividad de una familia bien conocida de desigualdades NC, y que hay también una familia de desigualdades NC cuyos grafos de exclusividad son los complementos de los ciclos impares. Además, caracterizamos los valores máximos no contextual y cuántico de estas desigualdades NC y proporcionamos los estados cuánticos y las medidas que conducen a sus violaciones cuánticas máximas. Finalmente, en la Sec. 2.6 presentamos algunos resultados que ofrecen evidencias que apoyan la conjetura de que el principio E selecciona exactamente la máxima violación cuántica de la desigualdades NC discutidas en la Sec. 2.5. Finalizamos el capítulo con material adicional en la Sec. 2.7, en la que presentamos una tabla que cuenta el número de subgrafos de exclusividad básicos inducidos en los grafos de exclusividad de algunas desigualdades NC y demostraciones de Kochen-Specker (KS) conocidas. • Capítulo 3:Correlaciones cuánticas completamente contextuales. Las correlaciones cuánticas son contextuales. Sin embargo, en general, nada impide la existencia de correlaciones incluso más contextuales aún. El propósito del Capítulo 3 es identificar y poner a prueba una desigualdad NC en la cual la violación cuántica no pueda ser mejorada por ninguna hipotética teoría post-cuántica, y utilizarla para obtener experimentalmente correlaciones en las que la fracción de correlaciones no contextuales sea lo más pequeña posible. Tales correlaciones se generan experimentalmente a partir de los resultados de test secuenciales compatibles realizados sobre un sistema cuántico de cuatro estados codificado en la polarización y el camino de un solo fotón. Para abordar dicho propósito, utilizamos una de las ideas clave del Capítulo 1 (en particular, las Secs. 1.4.6 y 1.5.1): la aplicación de la aproximación de CSW mediante teoría de grafos a las correlaciones cuánticas (Ref. [7]) sobre la base de nuestra clasificación de los QCG (Ref. [8]) permite diseñar experimentos con contextualidad cuántica “a la carta”, mediante la selección de grafos con las propiedades deseadas. El Capítulo 3 presenta un destacado ejemplo de este programa: utilizamos el enfoque teórico-gráfico de CSW a fin de identificar y realizar un experimento con test cuánticos secuenciales y compatibles, que produce correlaciones con la mayor contextualidad permitida por la suposición de no-disturbance (ND) (v´ease Ec. (1.20)), cuya validez se asume también para teorías post-cuánticas. Con ese objetivo, en la Sec. 3.2 introducimos en primer lugar una medida de contextualidad de las correlaciones, el llamado contenido no contextualWNC, de modo que el valor WNC = 0 corresponde a la contextualidad máxima. A continuación, mostramos cómo obtener experimentalmente cotas superiores medibles deWNC. Más tarde, en la Sec. 3.3, mostramos en qué modo la teoría de grafos nos permite identificar experimentos en que la cota superior de WNC predicha por la TC es igual a cero, y aplicamos ese método para seleccionar un experimento para el cualWNC = 0. Esto implica a su vez utilizar nuestra clasificación de los QCG para seleccionar un grafo con las propiedades combinatorias deseadas, i. e., un grafo cuántico completamente contextual (QFCG). Encontramos que hay únicamente cuatro QFCG con menos de 11 vértices, e identificamos aquí el que requiere un sistema cuántico con la dimensión mínima necesaria para producir la máxima violación cuántica de la desigualdad NC asociada a dicho grafo de exclusividad. Además, proporcionamos la desigualdad NC, el estado cuántico y las medidas conducentes a la máxima violación cuántica. Finalmente, en la Sec. 3.4, describimos y llevamos a cabo el experimento que pone a prueba dicha desigualdad NC, y discutimos los resultados obtenidos, que ponen de manifiesto correlaciones para las que WNC < 0.06. • Capítulo 4: Redes sociales cuánticas. Para cerrar la primera parte de la tesis, este capítulo propone una interesante aplicación de las ideas expuestas en los capítulos precedentes. Consideramos una tarea de teoría de la información, en concreto la maximización de cierta probabilidad promedio, para la cual el enfoque de CSW basado en teoría de grafos constituye un marco natural. Para dicha tarea, la TC no sólo supera a las teorías clásicas, sino que también en algunos casos no puede ser mejorada utilizando hipotéticas teorías post-cuánticas. El aspecto novedoso aquí es que el enfoque se hace más atractivo al tender un puente con otra disciplina, la de las ciencias sociales, en la que la teoría de grafos proporciona una herramienta principal en el análisis, y esta conexión abre la posibilidad a posteriores aplicaciones insospechadas. Enfocamos nuestra atención en las redes sociales (RS), un objeto de estudio tradicional en las ciencias sociales. Empezamos con la observación de que, si bien una RS viene típicamente descrita por un grafo en que los vértices representan actores de la red y las aristas representan el resultado de su mutua interacción, dicho grafo no captura la naturaleza de las interacciones ni explica por qué un actor está conectado o no a otros actores de la RS. Desde esta perspectiva, el grafo da una descripción incompleta de la RS. El objetivo de este capítulo es discutir las RS sobre la base de las interacciones generales que pueden dar lugar a ellas. En la Sec. 4.1 introducimos un enfoque físico a las RS en que cada actor está caracterizado por un test sí-no sobre un sistema físico. Este enfoque permite considerar RS más generales (RSG), más allá de aquéllas generadas por interacciones basadas en propiedades pre-existentes, como ocurre en las RS clásicas (RSC). También ponemos de manifiesto la diferencia entre una RSG y una RSC descritas por el mismo grafo, por medio de una tarea simple para la cual la probabilidad promedio de éxito está acotada superiormente de manera diferente dependiendo de la naturaleza de las interacciones que definen la RS. En la Sec. 4.2 introducimos las RS cuánticas (RSQ), como un ejemplo de RS más allá de las RSC. En una RSQ, un actor i está caracterizado por un test acerca de si el sistema está o no en un estado cuántico |ψi›. Nosotros demostramos que las RSQ superan a las RSC para la tarea previamente mencionada y en ciertos grafos. Identificamos los más simples de entre dichos grafos, y mostramos que los grafos en que las RSQ superan a las RSC son cada vez más frecuentes a medida que crece el número de vértices. En la Sec. 4.3 consideramos grafos para los que las RSQ superan a las RSC, pero ninguna RSG supera a la mejor RSQ, e identificamos todos los grafos con menos de 11 vértices con esa propiedad. Es más, analizamos también el hecho de que, mientras que la ventaja cuántica usualmente requiere la preparación del sistema en un estado cuántico específico, según crece la complejidad de la red este requerimiento llega a ser innecesario: existen grafos para los cuales la ventaja cuántica es independiente del estado cuántico. Nosotros identificamos el grafo más simple de esta clase. El capítulo finaliza con algunas observaciones acerca de las posibles implicaciones prácticas de estas ideas, en la Sec. 4.4; y con un breve apéndice con detalles técnicos acerca de las herramientas y procedimientos necesarios para alcanzar nuestros resultados, en la Sec. 4.5. 2. La Parte II lleva por título Estados grafo: Clasificación y preparación óptima, y está estructurada en cinco capítulos: • Capítulo 5:Introducción: Formalismo de estabilizador y estados grafo. Es éste un capítulo introductorio, cuyo propósito es proporcionar las definiciones principales, y el mínimo trasfondo teórico necesario para sentar las bases para ladiscusión de los resultados de la segunda parte de la tesis. El capítulo se organiza endos secciones: La Sec. 5.1 se dedica a introducir el formalismo de estabilizador. Presentamos, en una forma autocontenida y compacta, algunos conceptos básicos y definiciones junto con la notación y las técnicas que se utilizarán en los siguientes capítulos. Discutimos brevemente el grupo de Pauli, y consideramos estados estabilizados y operadores estabilizadores, en general; y a continuación ponemos énfasis específicamente en los conceptos de estabilizador y generador, y en estados de estabilizador, que serán utilizados con profusión más tarde. Entre las operaciones unitarias destacamos el papel importante de las operaciones pertenecientes al grupo de Clifford, que serán de mucha utilidad cuando más tarde tratemos con los estados grafo y sus propiedades de entrelazamiento. La Sec. 5.2 enfoca la atención sobre los estados grafo, ejemplos particulares de estados de estabilizador que constituyen el objeto de estudio en esta parte de nuestra investigación. Presentamos una lista condensada de posibles aplicaciones de los estados grafo en teoría cuántica de la información. Se dan dos definiciones de estado grafo en la Sec. 5.2.1: la primera constituye una receta para la preparación de un estado grafo, que utiliza el grafo correspondiente como una plantilla o modelo. La segunda constituye una caracterización algebraica del generador del estado grafo sobre la base del propio grafo. En la Sec. 5.2.2 nos ocupamos de los estados grafo entendidos como un “laboratorio teórico” para el entrelazamiento multipartito, y describimos algunos resultados relevantes obtenidos previamente por otros autores en relación con el problema general de la clasificación del entrelazamiento en estados cuánticos puros, que proporcionan el escenario conceptual para nuestras contribuciones. Terminamos la exposición con un resumen sucinto acerca de la clasificación de los estados grafo de hasta 7 qubits en clases de equivalencia bajo operaciones locales de Clifford (LC), que fue llevada a cabo por nuestros predecesores Hein, Eisert y Briegel (HEB) en la Ref. [9], la cual puede considerarse el punto de partida de nuestro trabajo sobre estados grafo. • Capítulo 6:Entrelazamiento en estados grafo de ocho qubits. En este capítulo extendemos hasta ocho qubits la clasificación de los estados grafo de acuerdo a la equivalencia LC llevada a cabo en la Ref. [9], con la que cerramos el capítulo precedente. Van den Nest, Dehaene y De Moor (VDD) encontraron en la Ref. [10] que la aplicación sucesiva de una transformación con una descripción gráfica simple es suficiente para generar la clase de equivalencia completa de estados grafo bajo operaciones locales unitarias (LU) pertenecientes al grupo de Clifford, también conocida como órbita. Esta transformación simple recibe el nombre de complementación local, transformación que en definitiva permite generar las ´orbitas de todos los estados grafo de n qubits no equivalentes bajo operaciones LC; en particular, las 101 ´orbitas correspondientes a los estados grafo de 8 qubits, cuya clasificación es la meta de este capítulo. Para establecer un orden entre las clases de equivalencia nosotros utilizamos los criterios propuestos en las Refs. [9, 11], es decir, (a) número de qubits, (b) mínimo número de puertas controlled-Znecesario para la preparación, (c) la medida de Schmidt, y (d) los índices de rango. Estos criterios se introducen y describen en la Sec. 6.2. En la Sec. 6.3 presentamos nuestros resultados: para cada una de estas clases de equivalencia obtenemos un representante que requiere el mínimo número de puertas controlled-Z para su preparación y mínima profundidad de preparación. Además, calculamos la medida de Schmidt para la partición 8-partita, y los rangos de Schmidt para todas las particiones bipartitas. En la Sec. 6.4 presentamos nuestras conclusiones y señalamos algunos problemas pendientes, que atañen principalmente a las limitaciones del uso de los criterios precedentes como etiquetas que distingan de forma no ambigua entre cualquier par de clases de equivalencia bajo LC de estados grafo de hasta ocho qubits. Este asunto es abordado en el siguiente capítulo. • Capítulo 7: Conjunto compacto de invariantes que caracteriza a estados grafo de hasta ocho qubits. El conjunto de medidas de entrelazamiento propuesto por HEB en la Ref. [9] para estados grafo de n qubits falla a la hora de distinguir entre clases de equivalencia bajo operaciones LC (clases LC) que no son equivalentes entre sí, paran ≥ 7. Por tanto, no podemos utilizar estos invariantes para decidir a qué clase de entrelazamiento pertenece un estado grafo dado. Recíprocamente, si dispusiésemos de un conjunto de invariantes con esas características, entonces podríamos utilizarlo para etiquetar de manera no ambigua cada una de las clases. Por otro lado, el conjunto de invariantes propuesto por VDD en la Ref. [12] distingue entre clases no equivalentes, pero contiene demasiados invariantes (más de 2 ×1036 para n = 7) para ser práctico. En este capítulo resolvemos el problema de decidir a qué clase de entrelazamiento pertenece un estado grafo de n ≤ 8 qubits mediante el cálculo de algunas propiedades intrínsecas del estado, por tanto sin necesidad de generar la clase LC completa. La Sec. 7.1 es un resumen condensado de ideas y conceptos que ya se han presentado en capítulos previos, y que permiten seguir las discusiones subsiguientes. En la Sec. 7.2, por conveniencia, empezamos recordando la definición de estado grafo a través de la caracterización algebraica del generador, y repasamos el efecto de la complementación local sobre los operadores de estabilización. Luego, en la Sec. 7.2.1, introducimos un nuevo concepto básico del formalismo de estabilizador, a saber, el soporte de un operador de estabilización, y las clases de equivalencia relativas a los soportes. Estos conceptos son necesarios en la Sec. 7.2.2, donde analizamos algunos de los resultados acerca de invariantes propuestos por VDD que serán útiles en nuestra discusión. En la Sec. 7.3 presentamos y discutimos los resultados de nuestra investigación: confirmamos la conjetura formulada en la Ref. [12] de que los invariantes de VVD tipo r = 1 son suficientes para distinguir entre las 146 clases de equivalencia LC para estados grafo de hasta ocho qubits. Además, introducimos un nuevo conjunto compacto de invariantes relacionado con los propuestos por VDD, los llamados invariantes cardinalidad-multiplicidad (C-M), y demostramos que cuatro de tales invariantes C-M son suficientes para distinguir entre todas las clases LC no equivalentes para estados grafo con n ≤ 8 qubits. • Capítulo 8:Preparación ´optima de estados grafo. En este capítulo aprovechamos tanto la clasificación de los estados grafo en clases de equivalencia LC (Cap. 6) como la identificación de tales clases sobre la base de un conjunto compacto de invariantes bajo operaciones LC (Cap. 7). Mostramos cómo preparar cualquier estado grafo de hasta 12 qubits con: (a) el mínimo número de puertas controlled-Z, y (b) la mínima profundidad de preparación. Asumimos en la preparación sólo puertas de un qubit, y puertas controlled-Z. El método explota el hecho de que cualquier estado grafo pertenece a una clase de equivalencia bajo operaciones LC: si uno necesita preparar un estado grafo |G› y sabe que dicho estado pertenece a una clase específica, entonces uno puede preparar |G›mediante la preparación del estado |G’›, equivalente bajo operaciones LC, que requiere el menor número de puertas entrelazadoras y la menor profundidad de preparación de esa clase LC (Refs. [9, 11, 13]), y a continuación transformando |G’› en|G› por medio de operaciones unitarias de un qubit. En la Sec. 8.1, por comodidad, recordamos la definición de estado grafo en la que se usa el grafo como una plantilla o modelo para su preparación a través de la aplicación de una serie de puertas controlled-Z. Definimos el concepto de profundidad de preparación, y a continuación discutimos cómo el problema de la profundidad de preparación está relacionado con un problema clásico en teoría de grafos, el de la determinación del índice cromático o número cromático de aristas de un grafo: el mínimo número de colores requerido para conseguir un coloreado propio de aristas del grafo. En la Sec. 8.2, extendemos hasta 12 qubits la clasificación de los estados grafo de acuerdo con sus propiedades de entrelazamiento (en clases LC), e identificamos cada clase utilizando para ello únicamente un conjunto reducido de invariantes (invariantes C-M). En la Sec. 8.3, proporcionamos un representante de la clase con las dos propiedades (a) y (b), si ´este existe, o en caso contrario uno con la propiedad (a) y otro con la propiedad (b). Todos estos resultados, que ocupan varios cientos de megabytes, se organizan en dos tablas, una para n < 12 y otra para n = 12, que se presentan como material suplementario en la Ref. [14]. En la Sec. 8.4 explicamos cómo obtener las puertas de un qubit necesarias, y proporcionamos como material suplementario en la Ref. [15] un programa de ordenador para, dado el grafo Gcorrespondiente al estado grafo que uno desea preparar, generar una secuencia de operaciones de complementación local que conecte G con el correspondiente (o los correspondientes) grafo(s) ´optimo(s). Finalmente, en la Sec. 8.5 ilustramos el método completo con un ejemplo. Como material para terminar este capítulo, hemos añadido la Sec. 8.6, donde discutimos sucintamente una generalización de los estados grafo conocida como estadoshipergrafo, de la cual los anteriores constituyen un subconjunto. Tras presentar las definiciones principales, y describir algunos de los resultados más recientes acerca de la exploración de las propiedades de entrelazamiento y características no clásicas de los estados hipergrafo, señalamos posibles futuras extensiones de nuestras contribuciones en relación con los estados grafo, en particular el análisis de la profundidad de preparación de un estado hipergrafo dado y su posible procedimiento óptimo de preparación. • Capítulo 9: Propuesta experimental para el protocolo cuántico “Guess My Number”. El objetivo de este capítulo es presentar, de una manera sencilla y directa, un protocolo experimental de reducción de la complejidad de la comunicación basado en el uso de recursos cuánticos, conocido como el protocolo “Guess My Number” (GMN). El punto clave radica en que los participantes en el protocolo GMN comparten un estado cuántico entrelazado, y este estado cuántico es precisamente un estado grafo, el estado Greenberger-Horne-Zeilinger (GHZ) de tres (o de cuatro) qubits. En los Caps. 6–8 hemos centrado nuestra atención en los estados grafo desde el punto de vista de la teoría del entrelazamiento. También hemos presentado resumidamente muchas de las principales aplicaciones de los estados grafo en teoría cuántica de la información en la Sec. 5.2. Entre ellas mencionamos la complejidad de la comunicación, para la cual los estados grafo constituyen recursos interesantes y ventajosos debido a su genuino entrelazamiento multipartito. Comenzamos en la Sec.9.1.1 pasando revista de manera resumida a algunos conceptos básicos relacionados con la complejidad de la comunicación, a fin de proporcionar el mínimo trasfondo conceptual necesario. Enfatizamos el hecho de que los estados grafo, como otros estados cuánticos entrelazados, constituyen un valioso recurso que puede ser compartido por los participantes en aquellos escenarios correspondientes al denominado modelo de entrelazamiento de la complejidad de la comunicación. Nuestro propósito en las siguientes secciones es presentar en detalle uno de esos escenarios, que involucra un protocolo de comunicación basado en el juego GMN, con la peculiaridad de que los participantes comparten específicamente un estado grafo. Describimos el protocolo original GMN asistido por entrelazamiento para la reducción de la complejidad de la comunicación, introducido por Steane y van Dam, en la Sec. 9.2, y a continuación analizamos las dificultades de una realización experimental de dicho protocolo: ésta requeriría producir y detectar estados GHZ de tres qubits con una eficiencia η > 0.70, lo que a su vez requeriría detectores de un fotón de eficiencia σ > 0.89. Presentamos nuestra versión modificada del protocolo GMN en la Sec. 9.3: proponemos ciertos cambios que hacen que el protocolo GMN modificado sea experimentalmente factible. Discutimos seguidamente la mejor estrategia clásica (que implica intercambio de bits, utilizando aleatoriedad compartida), la estrategia cuántica alternativa (intercambio de bits sobre la base del uso ingenioso de un estado grafo compartido), y luego hacemos una comparación entre sus rendimientos para determinar la ventaja cuántica respecto a la variante clásica, a través del análisis de la probabilidad de éxito en el juego GMN. Finalmente, en la Sec. 9.4, discutimos los requisitos de eficiencia de detección de fotones necesarios para realizar el experimento en el laboratorio, y realizamos una propuesta experimental concreta para tal experimento. En el experimento propuesto, la reducción cuántica de la complejidad de la comunicación multipartita requeriría una eficiencia η > 0.05, que se puede lograr con detectores conσ > 0.47, para cuatro participantes, y η > 0.17 (σ > 0.55) para tres participantes. Concluimos el capítulo dando cuenta de la subsiguiente realización del experimento por parte de Zhang et al. en la Ref. [16], con los resultados esperados: los participantes separados entre sí que comparten el estado (grafo) entrelazado, pueden computar una función de inputs distribuidos mediante el intercambio de menos información clásica que la requerida utilizando cualquier estrategia clásica. La tesis termina con una sección separada en la p. 171, donde explicamos en cierto detalle la conexión entre las Partes I y II. En la p. 185 se recoge un resumen con las conclusiones de la tesis. Los artículos en que se basa esta tesis, junto con otras contribuciones, se relacionan en la p. 193. Por comodidad, se proporciona un índice con los acrónimos más frecuentemente utilizados a lo largo de la tesis en la p. 197. Finalmente, tras la bibliografía, presentamos un anexo con los artículos originales que dan soporte a la tesis.