El juego arbitrado cuántico en el procesamiento de información cuántica es una clase de juegos en la teoría general de los juegos cuánticos . [1] Se juega entre dos jugadores, Alice y Bob, y es arbitrado por un árbitro. El árbitro genera la recompensa para los jugadores después de interactuar con ellos durante un número fijo de rondas, mientras intercambia información cuántica .
Definición
Un -vuelve el árbitro cuántico realizarondas de interacción con el jugador Alice y Bob. Cada interacción implica recibir algunos estados cuánticos de Alice y Bob, procesar los estados cuánticos junto con el estado "sobrante" de la interacción anterior, producir algún estado de salida y enviar parte del estado de salida a los jugadores. Al final derondas, el árbitro procesa el estado final recibido de los jugadores y decide el pago para Alice y Bob. El papel del árbitro es transmitir qubits a los jugadores Alice y Bob. El trabajo del árbitro es enredar los qubits, que se argumenta que es esencial en los juegos cuánticos. Cuando Alice y Bob devuelven los qubits al árbitro, el árbitro luego verifica sus estados finales. [2]
Matemáticamente, un árbitro de n vueltas es una coestrategia de medición cuyos espacios de entrada y espacios de salida son de la forma
- y
para espacios euclidianos complejos y .
representar el mensaje enviado por el árbitro a Alice y Bob durante el turno , y corresponden a sus respuestas. Al final de giros, el árbitro produce una salida
Un -El juego arbitrado cuántico de turnos consiste en un árbitro de n turnos junto con funciones que mapea cada salida de medición a la recompensa de Alice y Bob.
Los juegos individuales con árbitros cuánticos pueden imponer restricciones específicas a las estrategias que Alice y Bob pueden elegir. Por ejemplo, en los juegos no locales [3] y los juegos de pseudo-telepatía , [4] A Alice y Bob se les permite compartir enredos, pero se les prohíbe comunicarse. En general, estas restricciones pueden no aplicarse en juegos con arbitraje cuántico.
Se considera que una lengua L tiene un juego arbitrado con error ε si tiene un verificador de tiempo polinomial que cumple estas condiciones: para cada cadena x∈L Alice (la que prueba sí) puede convencer al árbitro de que acepte x con probabilidad de al menos 1- ε independientemente de la estrategia de Bob (el no prover) y para cada cadena x∈L Bob puede convencer al árbitro de rechazar x con una probabilidad de al menos 1-ε independientemente de la estrategia de Alice. [5]
Juego arbitrado cuántico de suma cero
Similar a un juego clásico de suma cero , un juego arbitrado cuántico de suma cero [1] es un juego arbitrado cuántico con la restricción adicional.
Es natural suponer que Alice y Bob juegan estrategias independientes en un juego arbitrado cuántico de suma cero, ya que no puede ser ventajoso para ambos jugadores comunicarse directamente entre sí o compartir inicialmente un estado de entrelazamiento {referencia}. En este caso, la estrategia de Alice y Bob se puede representar mediante
- y
dónde es el conjunto de todas las estrategias de n vueltas que tienen espacio de entrada y espacio de salida .
La estrategia combinada es entonces .
Teorema mínimo-máximo
Definir , y , entonces la recompensa esperada de Alice es
La estrategia óptima para Alice radica en el problema mínimo-máximo
- .
La igualdad anterior se cumple porque se han extraído de compactos y convexos conjuntos y . Se llama teorema mínimo-máximo para juegos cuánticos de suma cero.
Juego arbitrado cuántico de un turno
Los juegos arbitrados cuánticos de un turno son un subconjunto de juegos arbitrados cuánticos (QRG) donde hay dos jugadores ilimitados (Alice y Bob) y un árbitro limitado computacionalmente. Se llaman juegos de un turno o QRG1 porque solo hay un turno por juego. El juego funciona haciendo que cada jugador envíe una matriz de densidad al árbitro, quien luego conecta esos estados en su circuito cuántico. El ganador del juego se decide por el resultado del circuito donde, Alice gana la mayoría de las veces cuando el circuito produce un "sí" o | 1> estado y Bob gana la mayoría de las veces cuando un "no" o | 0> estado es producido por el circuito. [6] Un turno consiste en que el árbitro envía un mensaje al prover (Alice o Bob) y luego Alice o Bob envían una respuesta al árbitro. [5] El orden del juego es el siguiente: Alice envía al árbitro su matriz de densidad, luego el árbitro procesa el estado de Alice y envía un estado a Bob, Bob luego mide el estado y envía un resultado clásico al árbitro, el árbitro luego comprueba la medida de Bob y produce un "sí", lo que significa que Alice gana o un "no" y Bob gana. [5]
Juego con arbitraje cuántico de Bell State
En un juego arbitrado cuántico de Bell State, hay tres participantes, Alice, Bob y el árbitro. El juego consta de tres puertas. Detrás de cada puerta hay una x o una o (estado de giro hacia arriba o estado de giro hacia abajo). El árbitro les da a Alice y Bob tres condiciones sobre lo que hay detrás de cada una de las puertas. Por ejemplo, las condiciones podrían ser: 1) Las puertas 1 y 2 tienen lo mismo. 2) Las puertas 2 y 3 tienen lo mismo. 3) Las puertas 1 y 3 son diferentes.
El objetivo de este juego es que Alice y Bob encuentren un par coincidente detrás de las puertas. En términos cuánticos, esto significa que Alice y Bob producen estados de densidad coincidentes. Durante el juego, Alice y Bob no pueden comunicarse, pero pueden elaborar estrategias antes de que comience el juego. Lo hacen al compartir un par de fotones entrelazados. La estrategia permite que Alice y Bob maximicen sus cambios de ganancia. Sin una estrategia, Alice y Bob tienen 2/3 de posibilidades de ganar. Al diseñar estrategias, la probabilidad de Alice y Bob de producir estados cuánticos coincidentes aumenta de 2/3 a 3/4. [7]
Juego de arbitraje cuántico de CHSH
Juego arbitrado por CHSH
Un ejemplo de un juego arbitrado cuántico es un juego arbitrado cuántico CHSH. Un juego CHSH usa forma binaria para representar salidas (es decir, 0 y 1). En este juego, Alice y Bob juegan juntos contra una casa hipotética y no se les permite comunicarse entre ellos. Alice y Bob reciben cada uno un qubit aleatorio del árbitro. Para ganar el juego, necesitan proporcionar salidas (ayb) que maximicen a⊕b = xy. [7]
Análisis clásico de un juego arbitrado por CHSH
(x, y) | (a, b) | (0,0) | (0,1) | (1,0) | (1,1) |
---|---|---|---|---|
(0,0) | 1/2 | 0 | 0 | S * (1/2) |
(0,1) | 1/2 | 0 | 0 | 1/2 |
(1,0) | 1/2 | 0 | 0 | 1/2 |
(1,1) | 0 | 1/2 | 1/2 | 0 |
La mejor estrategia para Alice y Bob es devolver siempre un estado de 0 al árbitro. [7] Si hacen esto como lo demuestra el gráfico, ganan con una probabilidad del 75%. [7] Debido a estas probabilidades, la casa decide que si Alice y Bob ganan ganan 1 punto pero si pierden pierden 3 puntos. Esto da un pago de probabilidad de. Lo que asegura que todos se equilibren.
Análisis cuántico de un juego arbitrado cuántico de CHSH
Alice y Bob pueden usar estados entrelazados para manipular el juego a su favor. Alice y Bob reciben un fotón en el estado entrelazado | ψ⟩ = √2 [| 0⟩ | 0⟩ + | 1⟩ | 1⟩]. [7] Si Alice recibe x = 1, puede aplicar el Unitario Û (π / 4) a su qubit y luego medirlo, si recibe x = 0, todo lo que necesita hacer es medir su qubit. Si Bob obtiene y = 0, aplica Û (π / 8) y lo mide y si recibe y = 1, aplica Û (-π / 8) y luego lo mide. [7] El uso de esta estrategia les permite tener una probabilidad máxima de ganar de S =, lo que permite que Alice y Bob ganen todo el tiempo. [7]
Prueba interactiva cuántica con probadores de la competencia
Una prueba interactiva cuántica con dos probadores en competencia es una generalización del sistema de prueba interactivo cuántico de un solo probador . [8] [9] Puede ser modelado por juegos arbitrados de suma cero donde Alice y Bob son los probadores que compiten, y el árbitro es el verificador. Se supone que el árbitro está limitado computacionalmente (circuito cuántico de tamaño polinómico), mientras que Alice y Bob pueden estar computacionalmente irrestrictos. Alice, Bob y el árbitro reciben una cadena común, y después de rondas fijas de interacciones (intercambiando información cuántica entre los probadores y el árbitro), el árbitro decide si Alice gana o Bob gana.
RG clásico
En el escenario clásico, RG puede verse como el siguiente problema. Alice, Bob y el árbitro reciben una declaración. Alice está tratando de convencer al árbitro de que la declaración es verdadera, mientras que Bob está tratando de convencer al árbitro de que la declaración es falsa. El árbitro, que tiene un poder de cálculo limitado, examinará las pruebas proporcionadas por Alice y Bob, les hará preguntas y, al final del día, decidirá qué jugador tiene la razón (gana). El objetivo es que el árbitro encuentre un algoritmo tal que si la afirmación es verdadera, hay una forma de que Alice gane con una probabilidad mayor de 3/4, y si la afirmación es falsa, hay una forma de que Bob gane con probabilidad mayor que 3/4. Esta probabilidad es igual a 1-ε. [5]
En el lenguaje de la teoría de la complejidad, un problema de promesa tiene un juego arbitrado clásico (RG clásico) si existe un árbitro descrito por cómputo aleatorio de tiempo polinomial , tal que
- 1. para cada , hay una estrategia para que Alice gane con probabilidad ≥ 3/4, y
- 2. para cada , hay una estrategia para que Bob gane con probabilidad ≥ 3/4.
Se sabe que RG = EXP . [10] [11]
QRG
Los sistemas de prueba interactivos cuánticos con probadores competidores son una generalización del RG clásico donde el árbitro ahora está restringido a circuitos cuánticos generados en tiempo polinómico y puede intercambiar información cuántica con los jugadores. [1] Por lo tanto, QRG puede verse como el siguiente problema. Alice, Bob y el árbitro reciben alguna declaración (puede implicar un estado cuántico). Alice está tratando de convencer al árbitro de que la declaración es cierta, mientras que Bob está tratando de convencer al árbitro de que la declaración es falsa. El árbitro puede hacer preguntas a los probadores a través de estados cuánticos, recibir respuestas en estados cuánticos y analizar los estados cuánticos recibidos utilizando una computadora cuántica. Después de comunicarse con Alice y Bob porrondas, el árbitro decide si la declaración es verdadera o falsa. Si hay una forma de que el árbitro tome una decisión correcta con probabilidad ≥ 3/4, el juego está en QRG. Esta probabilidad es ≥ 1-ε. [5]
Más formalmente, QRG denota la clase de complejidad para todos los problemas de promesa que tienen juegos con árbitros cuánticos definidos de la siguiente manera. Dada una cuerda, un problema de promesa está en QRG si hay un árbitro representado por un circuito cuántico generado en tiempo polinomial tal que
- 1. si , existe una estrategia para que Alice gane con probabilidad ≥ 3/4, y
- 2. si , existe una estrategia para que Bob gane con probabilidad ≥ 3/4.
Resulta que QRG = EXP: permitir que el árbitro use un circuito cuántico y envíe o reciba información cuántica no le da al árbitro ningún poder adicional. EXP ⊆ QRG se deriva del hecho de que EXP = RG ⊆ QRG. demostró QRG ⊆ EXP mediante una formulación de QRG utilizando programas semidefinidos (SDP).
Formulación de programas semidefinidos
Para un juego arbitrado cuántico, al final de todas las interacciones, el árbitro genera uno de los dos resultados posibles para indicar si Alice gana o Bob gana .
Configuración da como resultado un juego arbitrado cuántico cuyo valor es la máxima probabilidad de ganar para Alice.
Usando la misma notación que el juego arbitrado cuántico de suma cero como arriba, el árbitro está representado por operadores , Alice puede elegir una estrategia de y Bob de . Definir
- , y
- ,
dónde es el operador de traza parcial .
El árbitro sale con probabilidad , y con probabilidad . puede considerarse como una co-estrategia que fusiona la estrategia de Alice con la del árbitro.
Para cualquier estrategia dada Alice elige, la probabilidad máxima de ganar para Bob es
- ,
que, por la propiedad de la representación de la estrategia , es igual a
- .
Por lo tanto, para maximizar la probabilidad de ganar de Alice, , la máxima probabilidad de ganar para Bob, debe minimizarse en todas las estrategias posibles. El objetivo es entonces calcular
- .
Este problema de minimización puede expresarse mediante el siguiente problema SDP: [1]
- .
La dimensión del espacio de entrada y salida de este SPD es exponencial (de los estados del producto tensorial) en , y el SDP tiene un polinomio de tamaño en la dimensión de su espacio de entrada y salida. Dado que existen algoritmos eficientes que pueden resolver SDP en tiempo polinomial, [12] [13] [14] se deduce que QRG ⊆ EXP.
Ver también
- Teorema mínimo-máximo
- Programación semidefinida
- QIP (complejidad)
Referencias
- ^ a b c d Gutoski, G; Watrous J (2007). Hacia una teoría general de los juegos cuánticos . Actas del Trigésimo Noveno Simposio Anual de ACM sobre Teoría de la Computación . pag. 565. arXiv : quant-ph / 0611234 . Código bibliográfico : 2006quant.ph.11234G . doi : 10.1145 / 1250790.1250873 . ISBN 9781595936318. S2CID 2329605 .
- ^ "Que comiencen los juegos cuánticos" . Mundo de la física . 2002-10-02 . Consultado el 11 de noviembre de 2020 .
- ^ Inteligente; Hoyer P .; Toner B .; Watrous J. (2004). "Consecuencias y límites de las estrategias no locales". Actas de la 19ª Conferencia Anual del IEEE sobre Complejidad Computacional : 236–249. arXiv : quant-ph / 0404076 . Código Bibliográfico : 2004quant.ph..4076C .
- ^ Brassard, G .; Broadbent A .; Tapp A. (2005). "Pseudo-telepatía cuántica". Fundamentos de la Física . 35 (11): 1877-1907. arXiv : quant-ph / 0407221 . Código Bibliográfico : 2005FoPh ... 35.1877B . doi : 10.1007 / s10701-005-7353-4 . S2CID 7395322 .
- ^ a b c d e Gutoski, Gus; Watrous, John (2005). "Pruebas interactivas cuánticas con probadores de la competencia". Stacs 2005 . Apuntes de conferencias en informática. 3404 . págs. 605–616. arXiv : cs / 0412102 . doi : 10.1007 / 978-3-540-31856-9_50 . ISBN 978-3-540-24998-6. S2CID 15662983 .
- ^ Ghosh, Soumik (2020). "Un estudio de los juegos arbitrados cuánticos de un turno" (PDF) . U Waterloo . Consultado el 11 de octubre de 2020 .
- ^ a b c d e f g h Web.Stanford.Edu , 2020, http://web.stanford.edu/~oas/SI/QM/notes/SIQMWeek3.pdf.
- ^ Kitaev, A; Watrous J (2000). "Paralelización, amplificación y simulación de tiempo exponencial del sistema de prueba interactivo cuántico". Actas del 32º Simposio de AMC sobre Teoría de la Computación : 608–617.
- ^ Watrous, J (2003). "PSPACE tiene sistemas de prueba interactivos cuánticos de ronda constante". Informática Teórica . 292 (3): 575–588. doi : 10.1016 / s0304-3975 (01) 00375-9 .
- ^ Koller, D; Megido N. (1992). "La complejidad de los juegos de suma cero de dos personas en forma extensiva". Juegos y comportamiento económico . 4 (4): 528–552. CiteSeerX 10.1.1.30.7625 . doi : 10.1016 / 0899-8256 (92) 90035-q .
- ^ Feige, U; Kilian J (1997). Haciendo juegos cortos . Actas del vigésimo noveno simbosio anual de ACM sobre teoría de la computación . págs. 506–516. CiteSeerX 10.1.1.5.1990 . doi : 10.1145 / 258533.258644 . ISBN 978-0897918886. S2CID 15664449 .
- ^ KHACHIYAN, L (1979). "Un algoritmo de tiempo polinomial en programación lineal". Matemáticas soviéticas - Doklady . 20 : 191-194.
- ^ Grötschel, M ; Lovász L .; Schrijver, A. (1988). Algoritmos geométricos y optimización combinatoria . Algoritmos y Combinatoria. Saltador. ISBN 978-3-642-97883-8.
- ^ Nesterov, Yurii; Nemirovskii, Arkadii (1994). Algoritmos polinomiales de punto interior en programación convexa (PDF) . Estudios SIAM en Matemática Aplicada. 13 . doi : 10.1137 / 1.9781611970791 . ISBN 978-0-89871-319-0.