Juego arbitrado cuántico

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 emite el pago para los jugadores después de interactuar con ellos durante un número fijo de rondas, mientras intercambian información cuántica .

Definición

Un árbitro cuántico de turnos realiza rondas de interacción con los jugadores 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 un estado de salida y enviar parte del estado de salida a los jugadores. Al final de las rondas, el árbitro procesa el estado final recibido de los jugadores y decide el pago para Alice y Bob. El papel del árbitro es pasar cúbits a los jugadores Alice y Bob. El trabajo del árbitro es entrelazar los cúbits, lo que se considera esencial en los juegos cuánticos. Cuando Alice y Bob devuelven los cúbits al árbitro, este verifica sus estados finales. ^[2] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Juegos arbitrados cuánticos

Matemáticamente, un árbitro de n turnos es una coestrategia de medición cuyos espacios de entrada y espacios de salida son de la forma ${\displaystyle \{R_{a}:a\in \Sigma \}}$ ${\displaystyle {\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}}$ ${\displaystyle {\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}}$

${\displaystyle {\mathcal {X}}_{k}={\mathcal {A}}_{k}\otimes {\mathcal {B}}_{k}}$y ${\displaystyle {\mathcal {Y}}_{k}={\mathcal {C}}_{k}\otimes {\mathcal {D}}_{k}}$

para espacios euclidianos complejos y . ${\displaystyle {\mathcal {A}}_{k},{\mathcal {B}}_{k},{\mathcal {C}}_{k}}$ ${\displaystyle {\mathcal {D}}_{k},\ 1\leq k\leq n}$

${\displaystyle {\mathcal {A}}_{k},{\mathcal {B}}_{k}}$representan el mensaje enviado por el árbitro a Alice y Bob durante el turno y corresponden a sus respuestas. Al final de los turnos, el árbitro produce un resultado ${\displaystyle k}$ ${\displaystyle {\mathcal {C}}_{k},{\mathcal {D}}_{k}}$ ${\displaystyle n}$ ${\displaystyle a\in \Sigma }$

Un juego arbitrado cuántico de n turnos consta de un árbitro de n turnos junto con funciones que asignan cada salida de medición a la recompensa de Alice y Bob. ${\displaystyle n}$ ${\displaystyle V_{A},V_{B}:\Sigma \mapsto \mathbb {R} }$ ${\displaystyle a}$

Los juegos arbitrados cuánticamente 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 pseudotelepatía ^[4] , Alice y Bob pueden compartir el entrelazamiento, pero tienen prohibido comunicarse. En general, es posible que dichas restricciones no se apliquen en los juegos arbitrados cuánticamente.

Se considera que un lenguaje L tiene un juego arbitrado con error ε si tiene un verificador de tiempo polinomial que satisface estas condiciones: para cada cadena x∈L Alice (la que demuestra que sí) puede convencer al árbitro de aceptar x con una probabilidad de al menos 1-ε independientemente de la estrategia de Bob (la que demuestra que no) 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]

Juegos 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 . ${\displaystyle V_{A}(a)+V_{B}(a)=0}$

Es natural suponer que Alice y Bob juegan estrategias independientes en un juego arbitrado cuántico de suma cero, ya que no puede ser simultáneamente 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 puede representarse mediante

${\displaystyle A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})}$y ${\displaystyle B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})}$

donde es el conjunto de todas las estrategias de n turnos que tienen espacio de entrada y espacio de salida . ${\displaystyle {\mathcal {S}}_{n}({\mathcal {X}}_{1\cdots n},{\mathcal {Y}}_{1\cdots n})}$ ${\displaystyle {\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}}$ ${\displaystyle {\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}}$

La estrategia combinada es entonces . ${\displaystyle A\otimes B}$

Teorema de mínimo-máximo

Defina , y , entonces el resultado esperado de Alice es ${\displaystyle V(a)=V_{A}(a)=-V_{B}(a)}$ ${\displaystyle R=\sum _{a\in \Sigma }V(a)R_{a}}$ ${\displaystyle \sum _{a\in \Sigma }V(a)\langle A\otimes B,R_{a}\rangle =\langle A\otimes B,R\rangle }$

La estrategia óptima para Alice radica entonces en el problema mínimo-máximo.

${\displaystyle \max _{A}\min _{B}\langle A\otimes B,R\rangle =\min _{B}\max _{A}\langle A\otimes B,R\rangle }$.

La igualdad anterior se cumple porque se extraen de conjuntos compactos y convexos y . Se denomina teorema de mínimo-máximo para juegos cuánticos de suma cero. ${\displaystyle A,B}$ ${\displaystyle {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})}$ ${\displaystyle {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})}$

Juegos de un turno

Los juegos de arbitraje cuántico de un turno son un subconjunto de los juegos de arbitraje cuántico (QRG) en los que hay dos jugadores ilimitados (Alice y Bob) y un árbitro limitado computacionalmente. Se denominan 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 estado "sí" o |1> y Bob gana la mayoría de las veces cuando el circuito produce un estado "no" o |0>. ^[6]  Un turno consiste en que el árbitro envía un mensaje al probador (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, luego Bob mide el estado y envía un resultado clásico al árbitro, luego el árbitro verifica la medición de Bob y produce un "sí" lo que significa que Alice gana o produce un "no" y Bob gana. ^[5]

Juegos del estado de Bell

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 de fotones que coincidan 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 compartiendo un par de fotones entrelazados. La elaboración de estrategias permite que Alice y Bob maximicen sus posibilidades de ganar. Sin estrategias, Alice y Bob tienen una probabilidad de 2/3 de ganar. Al elaborar estrategias, la probabilidad de Alice y Bob de producir estados cuánticos coincidentes aumenta de 2/3 a 3/4. ^[7]

Prueba interactiva cuántica con probadores en competencia

Una prueba interactiva cuántica con dos probadores en competencia es una generalización del sistema de prueba interactiva cuántica de un solo probador . ^{[8] [9]} Puede modelarse mediante juegos arbitrados de suma cero donde Alice y Bob son los probadores en competencia y el árbitro es el verificador. Se supone que el árbitro está limitado computacionalmente (circuito cuántico de tamaño polinomial), mientras que Alice y Bob pueden no tener restricciones computacionales. Alice, Bob y el árbitro reciben una cadena común y, después de rondas fijas de interacciones (intercambio de información cuántica entre los probadores y el árbitro), el árbitro decide si Alice gana o Bob.

Juegos clásicos

En el contexto clásico, el RG puede verse como el siguiente problema. A Alicia, Bob y el árbitro se les da una afirmación. Alicia intenta convencer al árbitro de que la afirmación es verdadera mientras que Bob intenta convencer al árbitro de que la afirmación es falsa. El árbitro, que tiene un poder de cómputo limitado, analizará las pruebas proporcionadas por Alicia y Bob, les hará preguntas y, al final del día, decidirá qué jugador tiene razón (gana). El objetivo es que el árbitro encuentre un algoritmo tal que si la afirmación es verdadera, haya una manera de que Alicia gane con una probabilidad mayor que 3/4, y si la afirmación es falsa, haya una manera de que Bob gane con una 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 un cálculo aleatorio de tiempo polinomial , tal que ${\displaystyle L=(L_{\text{yes}},L_{\text{no}})}$

1. para cada , existe una estrategia para que Alice gane con probabilidad ≥ 3/4, y ${\displaystyle x\in L_{\text{yes}}}$

2. para cada , existe una estrategia para que Bob gane con probabilidad ≥ 3/4. ${\displaystyle x\in L_{\text{no}}}$

Se sabe que RG = EXP . ^{[10] [11]}

Juegos cuánticos

Los sistemas de prueba interactivos cuánticos con probadores que compiten son una generalización del RG clásico donde el árbitro ahora está restringido a circuitos cuánticos generados en tiempo polinomial 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 una declaración (que puede involucrar un estado cuántico). 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 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 durante las rondas, el árbitro decide si la declaración es verdadera o falsa. Si hay una manera para que el árbitro tome una decisión correcta con probabilidad ≥ 3/4, el juego está en QRG. Esta probabilidad es ≥ 1-ε. ^[5] ${\displaystyle n}$

Más formalmente, QRG denota la clase de complejidad para todos los problemas de promesa que tienen juegos arbitrados cuánticamente definidos de la siguiente manera. Dada una cadena , un problema de promesa está en QRG si hay un árbitro representado por un circuito cuántico generado en tiempo polinomial tal que ${\displaystyle x}$ ${\displaystyle L=(L_{\text{yes}},L_{\text{no}})}$

1. si , existe una estrategia para que Alicia gane con probabilidad ≥ 3/4, y ${\displaystyle x\in L_{\text{yes}}}$

2. Si , existe una estrategia para que Bob gane con probabilidad ≥ 3/4. ${\displaystyle x\in L_{\text{no}}}$

Resulta que QRG = EXP, lo que permite al árbitro utilizar un circuito cuántico y enviar o recibir información cuántica no le otorga ningún poder adicional. EXP ⊆ QRG se deduce del hecho de que EXP = RG ⊆ QRG. Se demostró QRG ⊆ EXP mediante una formulación de QRG utilizando programas semidefinidos (SDP).

Formulación de programa semidefinido

En un juego arbitrado cuántico, al final de todas las interacciones, el árbitro emite uno de los dos resultados posibles para indicar si gana Alice o gana Bob . ${\displaystyle \{a,b\}}$ ${\displaystyle (a)}$ ${\displaystyle (b)}$

El resultado es un juego arbitrado cuántico cuyo valor es la máxima probabilidad de ganar para Alicia. ${\displaystyle V(a)=1,V(b)=0}$

Usando la misma notación que el juego arbitrado cuántico de suma cero como se mencionó anteriormente, el árbitro está representado por los operadores , Alice puede elegir una estrategia de , y Bob de . Definir ${\displaystyle \{R_{a},R_{b}\}}$ ${\displaystyle A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})}$ ${\displaystyle B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})}$

${\displaystyle \Omega _{a}(A)=\operatorname {Tr} _{{\mathcal {C}}_{1\cdots n}\otimes {\mathcal {A}}_{1\cdots n}}((A\otimes I_{{\mathcal {D}}_{1\cdots n}\otimes B_{1\cdots n}})R_{a})}$, y

${\displaystyle \Omega _{b}(A)=\operatorname {Tr} _{{\mathcal {C}}_{1\cdots n}\otimes {\mathcal {A}}_{1\cdots n}}((A\otimes I_{{\mathcal {D}}_{1\cdots n}\otimes B_{1\cdots n}})R_{b})}$,

¿Dónde está el operador de traza parcial ? ${\displaystyle \operatorname {Tr} _{\mathcal {X}}(Z)}$

El árbitro produce con probabilidad , y con probabilidad . puede considerarse como una coestrategia que fusiona la estrategia de Alice con la del árbitro. ${\displaystyle a}$ ${\displaystyle \langle A\otimes B,R_{a}\rangle =\langle B,\Omega _{a}(A)\rangle }$ ${\displaystyle b}$ ${\displaystyle \langle A\otimes B,R_{b}\rangle =\langle B,\Omega _{b}(A)\rangle }$ ${\displaystyle \{\Omega _{a}(A),\Omega _{b}(A)\}}$

Para cualquier estrategia que elija Alice, la probabilidad máxima de ganar para Bob es ${\displaystyle A}$

${\displaystyle \max _{B}\langle B,\Omega _{b}(A)\rangle }$,

que, por la propiedad de la representación de la estrategia, es igual a

${\displaystyle \min\{p\geq 0:\Omega _{b}(A)\leq pQ,\ Q\in {\text{co-}}{\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})\}}$.

Por lo tanto, para maximizar la probabilidad de victoria de Alice, , la probabilidad máxima de victoria de Bob, debe minimizarse en todas las estrategias posibles. El objetivo es entonces calcular ${\displaystyle p}$

${\displaystyle {\begin{array}{rl}\min &p\\{\text{subject to}}&\Omega _{b}(A)\leq pQ,\\&A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n}),\\&Q\in {\text{co-}}{\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})\end{array}}}$.

Este problema de minimización se puede expresar mediante el siguiente problema SDP: ^[1]

${\displaystyle {\begin{array}{rll}\min &\operatorname {Tr} (P_{1})\\{\text{subject to}}&\Omega _{b}(A_{n})\leq Q,\\&\operatorname {Tr} _{{\mathcal {C}}_{k}}(A_{k})=A_{k-1}\otimes I_{{\mathcal {A}}_{k}}&(2\leq k\leq n),\\&\operatorname {Tr} _{{\mathcal {C}}_{1}}(A_{1})=I_{{\mathcal {A}}_{1}},\\&Q_{k}=P_{k}\otimes I_{{\mathcal {D}}_{k}}&(1\leq k\leq n),\\&\operatorname {Tr} _{{\mathcal {B}}_{k}}(P_{k})=Q_{k-1}&(2\leq k\leq n),\\&A_{k}\in \operatorname {Pos} ({\mathcal {C}}_{1\cdots k}\otimes A_{1\cdots k})&(1\leq k\leq n),\\&Q_{k}\in \operatorname {Pos} ({\mathcal {D}}_{1\cdots k}\otimes B_{1\cdots k})&(1\leq k\leq n),\\&P_{k}\in \operatorname {Pos} ({\mathcal {D}}_{1\cdots k}\otimes B_{1\cdots k})&(1\leq k\leq n),\\\end{array}}}$.

La dimensión del espacio de entrada y salida de este SPD es exponencial (a partir de los estados del producto tensorial) en , y el SDP tiene un tamaño polinomial 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. ${\displaystyle n}$

Véase también

• Teorema de mínimo-máximo
• Programación semidefinida
• QIP (complejidad)

Referencias

1. Gutoski, G; Watrous J (2007). "Hacia una teoría general de los juegos cuánticos". Actas del trigésimo noveno simposio anual de la ACM sobre teoría de la computación . págs. 565–574. arXiv : quant-ph/0611234 . Bibcode :2006quant.ph.11234G. doi :10.1145/1250790.1250873. ISBN . 9781595936318. Número de identificación del sujeto  2329605.
2. "Que comiencen los juegos cuánticos". Physics World . 2002-10-02 . Consultado el 2020-11-11 .
3. Cleve, R; 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.
4. Brassard, G. ; Broadbent A. ; Tapp A. (2005). "Pseudotelepatí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.
5. Gutoski, Gus; Watrous, John (2005). "Pruebas interactivas cuánticas con probadores en competencia". Stacs 2005. Apuntes de clase en informática. Vol. 3404. págs. 605–616. arXiv : cs/0412102 . doi :10.1007/978-3-540-31856-9_50. ISBN . 978-3-540-24998-6.S2CID15662983  .​
6. Ghosh, Soumik (2020). "Un estudio de juegos arbitrados cuánticos de un turno" (PDF) . U Waterloo . Consultado el 11 de octubre de 2020 .
7. Web.Stanford.Edu , 2020, http://web.stanford.edu/~oas/SI/QM/notes/SIQMWeek3.pdf.
8. Kitaev, A; Watrous J (2000). "Paralelización, amplificación y simulación temporal exponencial de un sistema de prueba interactivo cuántico". Actas del 32.º Simposio AMC sobre teoría de la computación : 608–617.
9. Watrous, J (2003). "PSPACE tiene sistemas de prueba interactivos cuánticos de ronda constante". Ciencias de la Computación Teórica . 292 (3): 575–588. doi : 10.1016/s0304-3975(01)00375-9 .
10. Koller, D; Megiddo 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. 
11. Feige, U; Kilian J (1997). "Making games short (Extended abstract)". Actas del vigésimo noveno simposio anual de la ACM sobre teoría de la computación - STOC '97 . págs. 506–516. CiteSeerX 10.1.1.5.1990 . doi :10.1145/258533.258644. ISBN.  978-0897918886.S2CID15664449  .​
12. KHACHIYAN, L (1979). "Un algoritmo de tiempo polinomial en programación lineal". Matemáticas soviéticas - Doklady . 20 : 191–194.
13. Grötschel, M .; Lovász, L.; Schrijver, A. (1988). Algoritmos geométricos y optimización combinatoria . Algoritmos y combinatoria. Springer. ISBN 978-3-642-97883-8.
14. Nesterov, Yurii; Nemirovskii, Arkadii (1994). Algoritmos polinomiales de punto interior en programación convexa (PDF) . Estudios SIAM en Matemática Aplicada. vol. 13. doi :10.1137/1.9781611970791. ISBN 978-0-89871-319-0.S2CID117194167  .​