Investigando la complejidad en gráficos cuánticos

Los problemas que involucran la estructura de grafos son esenciales al estudiar la complejidad clásica. Esto incluye tareas como encontrar Cliques, Conjuntos Independientes o coloreos. Un paso natural es examinar problemas similares relacionados con grafos cuánticos, que sirven como una generalización de los grafos clásicos. Sin embargo, definir problemas de decisión claros para grafos cuánticos no es sencillo, lo que hace que las conexiones entre grafos cuánticos y complejidad estén menos exploradas.

En este trabajo, nos enfocamos en estudiar el problema de cliques para grafos cuánticos. Utilizamos el vínculo entre grafos cuánticos y canales cuánticos. Las entradas para nuestros problemas se presentan como canales cuánticos generados por circuitos. Esta conexión implícita ayuda a definir el grafo cuántico correspondiente. Este enfoque nos permite repensar los problemas de cliques y conjuntos independientes para grafos clásicos usando circuitos de canales deterministas o ruidosos, que dan lugar a grafos de confusión. Demostramos que al modificar la colección de canales en este contexto, podemos derivar problemas completos para clases de complejidad específicas. Esto muestra un problema de complejidad clásica cuya versión cuántica natural es diferente de lo que se asume comúnmente.

Para validar nuestros resultados en el contexto cuántico, aplicamos métodos inspirados en la autoevaluación. Presentamos una nueva prueba sobre cómo se puede reducir un problema específico a otro a través de cliques en grafos cuánticos. Además, examinamos la complejidad de una versión del problema de conjunto independiente para grafos cuánticos y ofrecemos ideas iniciales que sugieren que puede tener generalmente una complejidad más baja que en el escenario clásico, donde los problemas de cliques y conjuntos independientes son equivalentes.

El trabajo fundamental de Shannon sobre la capacidad de error cero crea un vínculo robusto entre canales ruidosos y teoría de grafos. Shannon estableció que para cualquier canal ruidoso clásico, se puede asociar un grafo correspondiente, llamado grafo de confusión, que captura propiedades críticas del canal. Notablemente, el grafo de confusión tendrá un conjunto independiente (en contraste con un clique) de un cierto tamaño si y solo si existe un conjunto de entradas distintas que tienen una probabilidad cero de confundirse como salidas.

Un grafo cuántico extiende el concepto de un grafo para incluir canales cuánticos, permitiéndonos adoptar la noción gráfica de confusión. Una colección de estados forma un conjunto independiente si la superposición promedio de estos estados es suficientemente pequeña. Los grafos cuánticos han sido examinados desde diferentes perspectivas, incluyendo capacidad de canal y juegos no locales.

Dada la importancia de los grafos en la complejidad clásica, surge la pregunta de si es igualmente importante estudiar grafos cuánticos en el ámbito de la teoría de complejidad cuántica. En el contexto clásico, determinar si un grafo contiene un clique (o conjunto independiente) es un problema completo bien conocido. La clase de complejidad reconocida como el equivalente cuántico del escenario clásico sugiere que las estructuras de prueba son reemplazadas por estados cuánticos generales. Kitaev resaltó este punto de vista al demostrar la completud de un problema cuántico específico, trazando paralelismos con instancias clásicas. Otros problemas completos también han demostrado transformarse en desafíos cuánticos completos.

Sorprendentemente, ha habido una investigación limitada sobre la complejidad de estos problemas en entornos cuánticos. Se realizaron estudios iniciales, pero para abordar completamente nuestro contexto, sería necesario asumir que los estados de entrada son estados producto. Una versión cuántica alternativa es una clase que contiene el problema del conjunto independiente pero opera bajo diferentes supuestos donde las pruebas se dan exclusivamente como estados producto. Hay pocos problemas completos conocidos en comparación con los numerosos problemas completos observados en entornos clásicos.

En este artículo, nos enfocamos específicamente en los problemas de decisión relacionados con encontrar cliques y conjuntos independientes dentro de grafos cuánticos. Describimos instancias de problemas como circuitos de canales cuánticos, que a su vez indican grafos cuánticos (sistemas de operadores). Además, consideramos versiones de los problemas de cliques y conjuntos independientes para grafos clásicos, donde en lugar de una descripción gráfica explícita, se proporciona una descripción de circuito de un canal ruidoso, determinando implícitamente un grafo a través de su grafo de confusión.

#Resumen de Resultados

Para canales deterministas y ruidosos clásicos, establecemos que nuestras versiones de los problemas de cliques y conjuntos independientes son completas para clases de complejidad específicas. Luego, profundizamos en estos problemas en relación con los canales cuánticos, donde mostramos que están contenidos dentro de una clase de complejidad reconocida y demostramos que el problema de cliques es difícil. Además, al cuantificar sobre una clase restringida de canales, recuperamos otro problema completo.

Nuestro trabajo presenta una jerarquía de problemas de decisión que captura la completud a través de cuatro clases de complejidad significativas y apoya la visión de que una de las clases es un contraparte cuántica natural.

#Grafos Cuánticos y Grafos de Confusibilidad

Un canal ruidoso clásico puede caracterizarse por una matriz de transición de probabilidad que describe las posibilidades de recibir ciertas salidas dado entradas específicas. El grafo de confusión correspondiente se define en base a los vértices que exhiben aristas cada vez que dos entradas pueden producir la misma salida con una probabilidad no cero. Un conjunto particular forma un conjunto independiente si la probabilidad de que cualquier par distinto de entradas lleve a la misma salida es cero.

En el contexto cuántico, los canales ruidosos clásicos son reemplazados por canales cuánticos. Estos son representados por mapas completamente positivos que preservan la traza. Cada Canal Cuántico se correlaciona con un sistema de operadores construido a partir de la combinación lineal de todos los productos de un conjunto de operadores de Kraus. Este sistema de operadores, independiente de su representación de Kraus, nos permite ampliar el concepto de grafo de confusión en relación con el estudio de las capacidades de error cero de los canales cuánticos.

Una colección de estados ortonormales puede ser distinguida con certeza a través de un canal si y solo si son ortogonales. Los grafos cuánticos ofrecen un marco para generalizar otros conceptos de la teoría de grafos clásica, como cliques y coloreos de grafos.

#Grafos Clásicos como Grafos Cuánticos

Los grafos clásicos pueden ser incrustados en grafos cuánticos. Al comenzar con un grafo no dirigido, podemos definir un sistema de operadores tomando la combinación de vértices que satisfacen condiciones específicas. Dos grafos son isomorfos si son equivalentes unitariamente. Dado un canal ruidoso, varios métodos pueden dar lugar a un canal cuántico correspondiente.

Existen vínculos establecidos entre parámetros de grafos clásicos y sus contrapartes cuánticas. Por lo tanto, podemos establecer conexiones entre cliques, conjuntos independientes y coloreos en ambos entornos, manteniendo esta correspondencia entre grafos clásicos y cuánticos.

#El Complemento de un Grafo Cuántico

Para un grafo, el complemento consiste en los mismos vértices, con aristas definidas por la ausencia de aristas en el grafo original. Sin embargo, extender esta definición a grafos cuánticos no tiene un método único acordado. Una táctica sencilla podría ser considerar el complemento ortogonal, pero este enfoque puede no producir un sistema de operadores.

Sin una forma única de definir un complemento de grafo para grafos cuánticos, se desafía la complejidad de los problemas de decisión basados en cliques y conjuntos independientes porque no pueden ser reducidos a través de operaciones de complemento. Por lo tanto, puede incluso ser posible que estos problemas exhiban diferentes complejidades.

#Conjuntos Independientes Cuánticos y Cliques Cuánticos

Se ha sugerido la existencia de generalizaciones cuánticas de muchos parámetros de grafos al estudiar juegos no locales. La existencia de cliques y conjuntos independientes en grafos clásicos puede conectarse a estrategias perfectas en juegos no locales correspondientes. En ciertas situaciones, las estrategias cuánticas pueden superar a las clásicas, llevando a la formación de cliques y conjuntos independientes cuánticos para grafos clásicos.

La dificultad de determinar el valor cuántico de un juego no local es notablemente indecidible. Esto se relaciona con los parámetros de grafos mencionados y ilustra que determinar la existencia de cliques o conjuntos independientes cuánticos en grafos clásicos o cuánticos es igualmente indecidible. En este trabajo, abordamos la complejidad de encontrar cliques y conjuntos independientes en grafos y grafos cuánticos sin analizar directamente cliques o conjuntos independientes cuánticos.

#Los Problemas de Clique/Conjunto Independiente para Grafos Cuánticos

Encontrar cliques o conjuntos independientes en grafos ha sido estudiado extensamente y da lugar a problemas completos. La estructura de entrada para estos problemas generalmente proporciona descripciones explícitas de vértices y aristas de grafos. Sin embargo, al representar grafos cuánticos, surgen desafíos, ya que los grafos cuánticos son subespacios lineales, a menudo requiriendo descripciones de base de tamaño exponencial.

Para navegar este problema, consideramos grafos cuánticos definidos por canales cuánticos subyacentes, lo que nos permite presentar instancias de problemas como diagramas de circuito que describen las acciones del canal mientras determinan simultáneamente las propiedades de un grafo cuántico subyacente.

#Presentando Grafos Cuánticos como Circuitos Cuánticos

Diferentes canales pueden producir el mismo grafo de confusión, indicando que la construcción no está definida inyectivamente. Sin embargo, dado cualquier grafo, siempre es factible construir un canal cuántico correspondiente con ciertas probabilidades de transición. Por lo tanto, evaluar todos los canales cuánticos puede abarcar todos los grafos cuánticos.

#Cliques Aproximadas y Conjuntos Independientes

Definimos claramente cliques y conjuntos independientes aproximados en relación con canales cuánticos. Para facilitar la presentación, nos enfocamos en casos con parámetros específicos. Requerimos que los estados de entrada sean completamente ortogonales, alineándonos con las perspectivas clásicas.

Al observar salidas de muestra de estos canales, podemos derivar probabilidades de no confusión. Esto se alinea con las interpretaciones clásicas de la confusión. Notamos que el requisito de que los estados de entrada sean puros no es esencial, ya que es suficiente asumir que pueden ser puros debido a la convexidad.

#Problemas de Clique y Conjunto Independiente

El problema de clique de canales cuánticos se enmarca como un problema de promesa que se centra en circuitos que producen cliques dentro de un contexto de canal cuántico. El problema de conjunto independiente sigue una estructura similar. Ambos problemas de promesa están definidos con parámetros de completud y solidez, donde las instancias afirmativas consisten en circuitos que conducen a cliques o conjuntos independientes.

Al conectar estos problemas con descripciones de circuitos, la complejidad de las instancias se alinea con el tamaño del circuito usado para calcular resultados en lugar de la descripción explícita del sistema de operadores.

#Revisando el Caso Clásico

Al examinar cliques y conjuntos independientes en grafos clásicos descritos a través de circuitos, determinamos la complejidad de resolver estos problemas. El tamaño de la instancia del problema está directamente vinculado al tiempo de computación necesario para establecer relaciones de adyacencia en lugar de depender de descripciones explícitas.

En casos deterministas, el grafo de confusión comprende subgrafos completos, haciendo que estos problemas sean relacionables con el problema de colisión bien estudiado, que examina si los elementos de un dominio comparten la misma imagen.

#El Caso Probabilístico

En contraste, las funciones probabilísticas transmiten ruido, ofreciendo un contexto más rico. Dependiendo de las transiciones, cualquier grafo puede materializarse desde algún canal ruidoso, enfatizando la complejidad de determinar cliques y conjuntos independientes.

Este artículo profundiza en estas complejidades en entornos deterministas, probabilísticos y cuánticos para cliques y conjuntos independientes. Establece relaciones entre estos varios problemas de decisión y muestra su completud para clases de complejidad específicas.

#Resultados Principales

Nuestras contribuciones destacan la complejidad de problemas decidibles en varios entornos: determinista, probabilística, cuántica y escenarios cuánticos restringidos. Demostramos que determinar cliques a través de estos escenarios conduce a completud para clases de complejidad notables. De manera similar, encontramos que los problemas de conjuntos independientes mantienen esta completud.

#Técnicas de Prueba

Nuestras estrategias de prueba se vieron influenciadas por técnicas de autoevaluación y métodos para delegar la computación cuántica. Si podemos probar ciertas propiedades para un canal en relación con cliques, podemos combinar eso con otros canales para asegurar posibles cliques entre los estados restantes.

Enfatizamos la importancia de las sumas directas en circuitos cuánticos. Al situar un modelo de circuito extendido que incorpora tanto canales unitarios como no unitarios, mantenemos aproximaciones y construcciones eficientes.

#Circuitos No Unitarios y Sumas Directas

Desarrollamos una técnica para componer circuitos cuánticos, mejorando la cantidad de canales para mostrar cómo pueden combinarse de manera eficiente. Este proceso nos permite extraer más información sobre posibles cliques de canales seleccionados.

#Autoevaluación para Cliques

Esta construcción ayuda a transferir ideas de autoevaluación a la identificación de cliques cuánticos. Ilustramos estrategias de prueba que muestran la relación entre ciertas propiedades de los canales y la presencia de cliques.

#Conjuntos Independientes

Esta metodología resulta crucial para abordar cliques, pero presenta desafíos para los conjuntos independientes. La complejidad de garantizar que los estados pertenezcan a conjuntos independientes diverge del enfoque simple utilizado para cliques.

#Canales que Rompen el Entrelazamiento y QMA

Nuestras pruebas profundizan en la complejidad de subclases específicas de canales que rompen el entrelazamiento, lo que nos lleva a investigar más la completud del problema del conjunto independiente en el contexto cuántico.

#Relación con Otros Trabajos

Nuestro trabajo se relaciona estrechamente con estudios previos mientras expande y aclara distinciones entre varios problemas. Aún con algunas discrepancias en la terminología y construcción, encontramos superposiciones significativas e inspiraciones compartidas.

#Problemas Abiertos

A partir de nuestro trabajo, surgen varias preguntas abiertas, especialmente en torno a los problemas de decisión relacionados con conjuntos independientes en grafos cuánticos.

A medida que exploramos varias avenidas de investigación, incluidos los problemas de coloreo y otros problemas de decisión gráfica, reconocemos el potencial de descubrir nuevas conexiones con la teoría de complejidad.

#Conclusión

Al estudiar la complejidad de los grafos cuánticos, navegamos a través de varios conceptos fundamentales y empleamos numerosos enfoques para aclarar y expandir nuestra comprensión de estas estructuras cuánticas. La intersección de los principios de complejidad clásica con teorías cuánticas ofrece un emocionante frente para la futura exploración.