Antecedentes sobre la Optimización Cuántica de Acceso Aleatorio (Quantum Random Access Optimization): Relajaciones cuánticas, códigos cuánticos de acceso aleatorio, esquemas de redondeo

Este material proporciona una mirada más profunda a los conceptos detrás de la Optimización Cuántica de Acceso Aleatorio.

Relajaciones

Considera un problema de optimización binaria definido sobre variables binarias $m_i\in \{-1,1\}$. La elección de utilizar variables $\pm 1$ en lugar de variables $0/1$ no es importante, pero será conveniente en términos de notación cuando comencemos a reformular este problema en términos de observables cuánticos. Estaremos interesados principalmente en problemas de optimización binaria cuadrática sin restricciones (QUBO), aunque las ideas contenidas en este documento pueden extenderse fácilmente a problemas con más que términos cuadráticos, y los problemas con variables no binarias o restringidas a menudo se pueden reformular como QUBO (aunque esta conversión generará alguna subrecarga).

Dentro de la optimización matemática, la relajación es la estrategia de tomar un problema difícil y mapearlo en una versión similar de ese problema que es (generalmente) más fácil de resolver. La idea central aquí es que para relajaciones útiles, la solución al problema relajado puede brindar información sobre el problema original y permitir encontrar heurísticamente mejores soluciones. Un ejemplo de relajación podría ser algo tan simple como tomar un problema de optimización discreto y permitir que un solucionador optimice el problema utilizando variables continuas. Una vez que se obtiene una solución para el problema relajado, el solucionador debe encontrar una estrategia para extraer una solución discreta de la solución relajada de valores continuos. Este proceso de mapear la solución relajada nuevamente al conjunto de soluciones admisibles del problema original a menudo se denomina redondeo.

Para ver un ejemplo concreto de relajación y redondeo, consulta el Algoritmo de Goemans-Williamson para MaxCut.

Sin pérdida de generalidad, el resto de este documento considerará una función objetivo MaxCut definida sobre un grafo $G=(V,E)$. Nuestro objetivo es encontrar una partición de nuestros vértices $V$ en dos conjuntos ($+1$ y $-1$), de modo que maximicemos el número de aristas que conectan ambos conjuntos. Más concretamente, a cada $v_i\in V$ se le asignará una variable binaria $m_i\in \{-1,1\}$, y definiremos el corte de una asignación de variable como:

$$\text{cut}(m)=\sum _{ij;e_{ij}\in E}\frac{1}{2}(1-m_i{m}_j)$$

Relajación Cuántica

Nuestro objetivo es definir una relajación de nuestra función objetivo MaxCut. Haremos esto mapeando las variables binarias de nuestra función objetivo en el espacio de observables de Pauli de un solo qubit e incorporando el conjunto de entradas factibles para cut($m$) en el espacio de estados de productos cuánticos de un solo qubit. Denotemos esta incrustración $F$ como:

$$F:\{-1,1{\}}^M\mapsto \mathcal{D}({\mathbb{C}}^{2^n}),$$

$$\text{cut}(m)\mapsto \text{Tr}(H\cdot F(m)),$$

donde $M=|V|$, y $H$ es un Hamiltoniano cuántico que codifica nuestra función objetivo.

Para que esto sea una relajación válida de nuestro problema, debe darse el caso de que:

$$\text{cut}(m)\ge \text{Tr}(H\cdot F(m))\mathrm{\forall }m\in \{-1,1{\}}^M.$$

Para garantizar que esto sea cierto, impondremos la condición más fuerte de que nuestra relajación conmuta con nuestra función objetivo. En otras palabras, cut($m$) es igual a la función objetivo relajada para todo $m\in \{-1,1{\}}^M$, en lugar de simplemente limitarla por arriba. Este detalle adquirirá una importancia crucial más adelante, cuando definamos explícitamente nuestra relajación cuántica.

Una Relajación Cuántica Simple

Antes de explicar el esquema completo de relajación cuántica basado en Códigos de Acceso Aleatorio Cuántico (Quantum Random Access Codes, QRAC) de un solo qubit, puede resultar útil analizar primero una versión de optimización cuántica con el que los usuarios pueden estar más familiarizados, pero que se analiza en el lenguaje de la relajación y el redondeo cuánticos.

Considera la incrustación

$$F^{(1)}:m\in \{-1,1{\}}^M\mapsto \{|0⟩,|1⟩{\}}^{\otimes M},$$

$$\text{cut}(m)\mapsto \text{Tr}(H^{(1)}{F}^{(1)}(m)),H^{(1)}=\sum _{ij;e_{ij}\in E}\frac{1}{2}(1-Z_i{Z}_j),$$

donde $Z_i$ indica el único qubit observable Pauli-Z definido en el $i$’ésimo qubit y términos de identidad en todos los demás qubits. Vale la pena convencerse de que esta transformación es una relajación válida de nuestro problema. En particular:

$$\text{cut}(m)=\text{Tr}(H^{(1)}{F}^{(1)}(m))\mathrm{\forall }m\in \{-1,1{\}}^M$$

Este tipo de incrustación es utilizado actualmente por muchos algoritmos de optimización cuántica a corto plazo, incluidos muchos enfoques basados en QAOA y VQE based approaches. Observa cómo, aunque la versión relajada de nuestro problema puede reproducir exactamente la función objetivo cut($m$) para entradas de la forma $\{|0⟩,|1⟩{\}}^{\otimes M}$, también somos libres de evaluar $H^{(1)}$ usando una superposición continua de dichos estados. Esto es una analogía de cómo uno podría relajar clásicamente un problema de optimización, de modo que se optimice la función objetivo utilizando valores continuos.

Fundamentalmente, una relajación sólo es útil si hay alguna forma práctica de redondear las soluciones relajadas al conjunto de soluciones admisibles del problema original. Para esta relajación cuántica particular, el esquema de redondeo se obtiene simplemente midiendo cada qubit de nuestra solución relajada en la base $Z$. La medición proyectará cualquier estado cuántico en el conjunto de estados básicos computacionales y, en consecuencia, en la imagen de $F^{(1)}$.

Relajaciones Cuánticas a través de Códigos Cuánticos de Acceso Aleatorio (QRAC)

Los códigos de acceso aleatorio cuánticos fueron delineados por primera vez en 1983 por Stephen Wiesner [2] y se utilizaron en el contexto de la teoría de la complejidad de la comunicación. No usaremos QRAC en la forma en que fueron concebidos originalmente, sino que los usaremos para definir nuestras relajaciones cuánticas. Por este motivo, no proporcionaremos una introducción completa a los RAC o QRAC, pero animaremos a los lectores interesados a buscar más información sobre ellos.

$(1,1,1)$, $(2,1,p)$, y $(3,1,p)$ Códigos Cuánticos de Acceso Aleatorio

Un $(k,1,p)$-QRAC, es un esquema para incrustar $k$ bits clásicos en un estado de 1 qubit, de modo que, dada una única copia de este estado, se puede recuperar cualquier uno de los $k$ bits con probabilidad $p$ realizando alguna medición. La relajación cuántica simple analizada en la sección anterior es un ejemplo de un $(1,1,1)$-QRAC trivial. Por conveniencia, escribiremos los QRACs $(2,1,0.854)$ y $(3,1,0.789)$ como $(2,1,p)$ y $(3,1,p)$, respectivamente. Vale la pena señalar que $(4,1,p)$-QRAC $(p>1/2)$ ha demostrado ser imposible. [3]

A medida que generalizamos el ejemplo simple anterior, será útil escribir estados de qubits individuales descompuestos en la base Hermitiana de los observables de Pauli.

$$\rho =\frac{1}{2}(I+aX+bY+cZ),|a{|}^2+|b{|}^2+|c{|}^2=1$$

Las incrustaciones $F^{(1)}$, $F^{(2)}$, y $F^{(3)}$ asociadas respectivamente con los QRACs $(1,1,1),(2,1,p),$ y $(3,1,p)$ ahora se pueden escribir de la siguiente manera:

$$\begin{array}{r}\begin{array}{lll}\text{QRAC}& & \text{Embedding into }\rho =|\psi (m)⟩⟨\psi (m)|\\ (1,1,1)& F^{(1)}(m):\{-1,1\}& \mapsto |{\psi }_m^{(1)}⟩⟨{\psi }_m^{(1)}|=\frac{1}{2}(I+m_{0}Z)\\ (2,1,p)& F^{(2)}(m):\{-1,1{\}}^2& \mapsto |{\psi }_m^{(2)}⟩⟨{\psi }_m^{(2)}|=\frac{1}{2}(I+\frac{1}{\sqrt{2}}(m_{0}X+m_{1}Z))\\ (3,1,p)& F^{(3)}(m):\{-1,1{\}}^3& \mapsto |{\psi }_m^{(3)}⟩⟨{\psi }_m^{(3)}|=\frac{1}{2}(I+\frac{1}{\sqrt{3}}(m_{0}X+m_{1}Y+m_{2}Z))\end{array}\end{array}$$

$$\text{Tabla 1: Estados QRAC}$$

Ten en cuenta que cuando se utiliza un $(k,1,p)$-QRAC con cadenas de bits $m\in \{-1,1{\}}^M,M>k$, estas incrustaciones se escalan de forma natural vía composición por producto tensorial.

$$m\in \{-1,1{\}}^6,F^{(3)}(m)=F^{(3)}(m_0,m_1,m_2)\otimes F^{(3)}(m_3,m_4,m_5)$$

De manera similar, cuando $k\nmid M$, podemos simplemente rellenar nuestra cadena de bits de entrada con el número apropiado de valores $+1$.

$$m\in \{-1,1{\}}^4,F^{(3)}(m)=F^{(3)}(m_0,m_1,m_2)\otimes F^{(3)}(m_3,+1,+1)$$

Recuperar Bits Codificados

Dado un estado QRAC, podemos recuperar los valores de los bits codificados estimando el valor esperado del observable correspondiente de cada bit. Ten en cuenta que existe un factor de reescalado que depende de la densidad del QRAC.

$$\begin{array}{r}\begin{array}{llll}\text{Embedding}& m_0& m_1& m_2\\ \rho =F^{(1)}(m_0)& \text{Tr}(\rho Z)& & \\ \rho =F^{(2)}(m_0,m_1)& \sqrt{2}\cdot \text{Tr}(\rho X)& \sqrt{2}\cdot \text{Tr}(\rho Z)& \\ \rho =F^{(3)}(m_0,m_1,m_2)& \sqrt{3}\cdot \text{Tr}(\rho X)& \sqrt{3}\cdot \text{Tr}(\rho Y)& \sqrt{3}\cdot \text{Tr}(\rho Z)\end{array}\end{array}$$

$$\text{Tabla 2: Recuperación de bits de estados QRAC}$$

Problema de Codificado de Hamiltonianos

Usando las herramientas que hemos descrito anteriormente, podemos escribir explícitamente los Hamiltonianos que codifican las versiones relajadas de nuestro problema MaxCut. Hacemos esto sustituyendo cada variable de decisión con el observable único que se ha asignado a esa variable bajo la incrustación $F$.

$$\begin{array}{r}\begin{array}{ll}\text{QRAC}& \text{Problem Hamiltonian}\\ (1,1,1)& H^{(1)}=\sum _{ij;e_{ij}\in E}\frac{1}{2}(1-Z_i{Z}_j)\\ (2,1,p)& H^{(2)}=\sum _{ij;e_{ij}\in E}\frac{1}{2}(1-2\cdot P_{[i]}{P}_{[j]}),P_{[i]}\in \{X,Z\}\\ (3,1,p)& H^{(3)}=\sum _{ij;e_{ij}\in E}\frac{1}{2}(1-3\cdot P_{[i]}{P}_{[j]}),P_{[i]}\in \{X,Y,Z\}\end{array}\end{array}$$

$$\text{Tabla 3: Hamiltonianos MaxCut relajados después de la incorporación de QRAC}$$

Ten en cuenta que aquí, $P_{[i]}$ indica un observable de Pauli de un solo qubit correspondiente a la variable de decisión $i$. El índice entre corchetes aquí es para dejar claro que $P_{[i]}$ no necesariamente actuará sobre el qubit $i$, porque $(2,1,p)$ y $(3,1,p)$ ya no tiene una relación 1:1 entre qubits y variables de decisión.

Conmutación de la Relajación Cuántica

Ten en cuenta que para los QRACs $(2,1,p)$ y $(3,1,p)$, estamos asociando múltiples variables de decisión a cada qubit. Esto significa que a cada variable de decisión se le asigna un observable de Pauli de un solo qubit único y algunos subconjuntos de estos observables de Pauli se definirán en los mismos qubits. Potencialmente, esto puede plantear un problema al intentar garantizar la condición de conmutatividad comentada anteriormente

Observa que bajo el $(3,1,p)$-QRAC, cualquier término en nuestra función objetivo de la forma $(1-x_i{x}_j)$ se asignará a un término del Hamiltoniano de la forma $(1-3\cdot P_{[i]}{P}_{[j]})$. Si ambos $P_{[i]}$ y $P_{[j]}$ actúan sobre diferentes qubits, entonces $P_{[i]}\cdot P_{[j]}=P_{[i]}\otimes P_{[j]}$ y este término de nuestro Hamiltoniano se comportará como esperamos.

Sin embargo, si $P_{[i]}$ y $P_{[j]}$ actúan en el mismo qubit, los dos Paulis se compondrán directamente. Recordemos que las matrices de Pauli forman un grupo y son autoinversas, por lo que podemos deducir que el producto de dos Paulis distintas dará otro elemento del grupo y no será la identidad.

En la práctica, esto significa que nuestra relación de conmutación se romperá y $\text{cut}(m)\ne \text{Tr}(H^{(1)}{F}^{(3)}(m))$

Para restaurar la conmutación de nuestra codificación con nuestra función objetivo, debemos introducir una restricción adicional en la forma de nuestro problema Hamiltoniano. Específicamente, debemos garantizar que las variables de decisión que comparten una ventaja en nuestro grafo de entrada $G$ no se asignen al mismo qubit bajo nuestra incrustración $F$

$$\mathrm{\forall }{e}_{ij}\in E,F^{(3)}(\dots ,m_i,\dots ,m_j,\dots )=F^{(3)}(\dots ,m_i,\dots )\otimes F^{(3)}(\dots ,m_j,\dots )$$

En [1] esto se logra encontrando una coloración del grafo G tal que ningún vértice con el mismo color comparta una arista, y luego asignando variables al mismo qubit solo si tienen el mismo color.

Esquemas de Redondeo Cuántico

Debido a que es poco probable que la solución final que obtenemos para el problema relajado ${\rho }_{\text{relax}}$ sea similar a $F$, necesitamos una estrategia para mapear ${\rho }_{\text{relax}}$ a la imagen de $F$ para que podamos extraer una solución a nuestro problema original.

En [1] hay dos estrategias propuestas para redondear ${\rho }_{\text{relax}}$ a $m\in \{-1,1{\}}^M$.

Redondeo Semideterminista

Una opción natural para extraer una solución es utilizar los resultados de la Tabla $2$ y simplemente estimar $\text{Tr}(P_{[i]}{\rho }_{\text{relax}})$ para todo $i$ para poder asignar un valor a cada variable $m_i$. El procedimiento descrito en la Tabla $2$ estaba pensado para usarse en estados en la imagen de $F$; sin embargo, ahora lo estamos aplicando a estados de entrada arbitrarios. La consecuencia práctica es que ya no mediremos un valor cercano a {$\pm 1$}, {$\pm \sqrt{2}$}, o {$\pm \sqrt{3}$}, como es de esperar para los QRACs $(1,1,1)$, $(2,1,p)$, y $(3,1,p)$, respectivamente.

Manejamos esto devolviendo el signo del valor esperado, lo que lleva al siguiente esquema de redondeo.

$$\begin{array}{r}{m}_i=\{\begin{array}{rl}+1& \text{Tr}(P_{[i]}{\rho }_{\text{relax}})>0\\ X\sim \{-1,1\}& \text{Tr}(P_{[i]}{\rho }_{\text{relax}})=0\\ -1& \text{Tr}(P_{[i]}{\rho }_{\text{relax}})<0\end{array}\end{array}$$

Donde $X$ es una variable aleatoria que devuelve -1 o 1 con la misma probabilidad.

Observa que el redondeo semideterminista recuperará fielmente $m$ de $F(m)$ con una probabilidad de falla que disminuye exponencialmente con el número de iteraciones utilizados para estimar cada $\text{Tr}(P_{[i]}{\rho }_{\text{relax}})$

Redondeo de Estado Mágico

Figura 1 Tres codificaciones diferentes, los estados y las bases de medición, de variables en un solo qubit. (a) Una variable por qubit. (b) Dos variables por qubit. (c) Tres variables por qubit. Tomado de [1].

En lugar de buscar distinguir de forma independiente cada $m_i$, el redondeo mágico de estados se selecciona aleatoriamente una base de medición que distinguirá perfectamente un par particular de estados QRAC ortogonales $\{F(m),F(\overline{m})\}$, donde $\overline{m}$ indica que cada bit de $m$ ha sido invertido.

Sea $\mathcal{M}$ el procedimiento de redondeo aleatorio que toma como entrada un estado ${\rho }_{\text{relax}}$ y muestrea una cadena de bits $m$ midiendo en una base mágica seleccionada aleatoriamente.

$${\mathcal{M}}^{\otimes n}({\rho }_{\text{relax}})\to F(m)$$

Primero, observa que para $(1,1,1)$-QRAC, solo hay una base para elegir y el esquema de redondeo de estado mágico es esencialmente equivalente al esquema de redondeo semideterminista.

Para los QRAC $(2,1,p)$ y $(3,1,p)$, si aplicamos el esquema de redondeo de estado mágico a un estado QRAC $F(m)$ de $n$ qubits, tendremos una probabilidad $2^{-n}$ y $4^{-n}$ de elegir la base correcta en cada qubit para extraer perfectamente la solución $m$. Dicho de otra manera, si nos dan un estado desconocido $F(m)$ la probabilidad de que ${\mathcal{M}}^{\otimes n}(F(m))\mapsto F(m)$ disminuya exponencialmente con el número de qubits medidos; es mucho más probable que se asigne a algún otro $F(m^{\ast })$. . De manera similar, cuando realizamos un redondeo mágico en un estado arbitrario ${\rho }_{\text{relax}}$, tenemos probabilidades igualmente bajas de elegir aleatoriamente la base mágica óptima para todos los $n$ qubits. Afortunadamente, el redondeo de estados mágicos ofrece un límite inferior en la relación de aproximación bajo ciertas condiciones.

Sea $F(m^{\ast })$ el estado de mayor energía en la imagen de F, y sea ${\rho }^{\ast }$ el estado propio máximo de H.

$$\mathrm{\forall }{\rho }_{\text{relax}}\text{s.t.}\text{Tr}(F(m^{\ast })\cdot H)\le \text{Tr}({\rho }_{\text{relax}}\cdot H)\le \text{Tr}({\rho }^{\ast }\cdot H)$$

$$\frac{\text{expected fval}}{\text{optimal fval}}=\frac{\mathbb{E}\left[\text{Tr}(H\cdot {\mathcal{M}}^{\otimes n}({\rho }_{\text{relax}}))\right]}{\text{Tr}(H\cdot F(m^{\ast }))}\ge \frac{5}{9}$$

Referencias

[1] Bryce Fuller et al., “Approximate solutions of combinatorial problems via quantum relaxations,” (2021), arXiv:2111.03167,

[2] Stephen Wiesner, “Conjugate coding,” SIGACT News, vol. 15, issue 1, pp. 78-88, 1983. link

[3] Masahito Hayashi et al., “(4,1)-Quantum random access coding does not exist—one qubit is not enough to recover one of four bits,” New Journal of Physics, vol. 8, number 8, pp. 129, 2006. link