Algoritmos de optimización cuántica

Uno de los tipos más comunes de ajuste de datos es resolver el problema de mínimos cuadrados , minimizando la suma de los cuadrados de las diferencias entre los puntos de datos y la función ajustada.

El algoritmo se proporciona${\displaystyle N}$puntos de datos de entrada${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})}$y${\displaystyle M}$funciones continuas${\displaystyle f_{1},f_{2},...,f_{M}}$El algoritmo encuentra y proporciona como resultado una función continua.${\displaystyle f_{\vec {\lambda }}}$que es una combinación lineal de${\displaystyle f_{j}}$:

${\displaystyle f_{\vec {\lambda }}(x)=\sum _{j=1}^{M}f_{j}(x)\lambda _{j}}$

En otras palabras, el algoritmo encuentra los coeficientes complejos.${\displaystyle \lambda _{j}}$y por lo tanto el vector${\displaystyle {\vec {\lambda }}=(\lambda _{1},\lambda _{2},...,\lambda _{M})}$.

El algoritmo tiene como objetivo minimizar el error, que viene dado por:

${\displaystyle E=\sum _{i=1}^{N}\left\vert f_{\vec {\lambda }}(x_{i})-y_{i}\right\vert ^{2}=\sum _{i=1}^{N}\left\vert \sum _{j=1}^{M}f_{j}(x_{i})\lambda _{j}-y_{i}\right\vert ^{2}=\left\vert F{\vec {\lambda }}-{\vec {y}}\right\vert ^{2}}$

dónde${\displaystyle F}$se define como la siguiente matriz:

${\displaystyle {F}={\begin{pmatrix}f_{1}(x_{1})&\cdots &f_{M}(x_{1})\\f_{1}(x_{2})&\cdots &f_{M}(x_{2})\\\vdots &\ddots &\vdots \\f_{1}(x_{N})&\cdots &f_{M}(x_{N})\\\end{pmatrix}}}$

El algoritmo de ajuste de mínimos cuadrados cuánticos ^{[ 2 ]} utiliza una versión del algoritmo cuántico de Harrow, Hassidim y Lloyd para sistemas de ecuaciones lineales (HHL) y produce los coeficientes.${\displaystyle \lambda _{j}}$y la estimación de la calidad del ajuste${\displaystyle E}$Consta de tres subrutinas: un algoritmo para realizar una operación de pseudoinversa , una rutina para la estimación de la calidad del ajuste y un algoritmo para aprender los parámetros de ajuste.

Debido a que el algoritmo cuántico se basa principalmente en el algoritmo HHL, sugiere una mejora exponencial ^{[ 3 ]} en el caso donde${\displaystyle F}$es disperso y el número de condición (es decir, la relación entre los autovalores más grandes y más pequeños ) de ambos${\displaystyle FF^{\dagger }}$y${\displaystyle F^{\dagger }F}$es pequeño.

Las entradas del algoritmo son${\displaystyle A_{1}...A_{m},C,b_{1}...b_{m}}$y parámetros relativos a la traza de la solución , la precisión y el valor óptimo (el valor de la función objetivo en el punto óptimo).

El algoritmo cuántico ^{[ 5 ]} consta de varias iteraciones. En cada iteración, resuelve un problema de factibilidad , es decir, encuentra cualquier solución que satisfaga las siguientes condiciones (dando un umbral).${\displaystyle t}$):

${\displaystyle {\begin{array}{lr}\langle C,X\rangle _{\mathbb {S} ^{n}}\leq t\\\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\X\succeq 0\end{array}}}$

En cada iteración, un umbral diferente${\displaystyle t}$Se elige y el algoritmo produce una solución.${\displaystyle X}$de tal manera que${\displaystyle \langle C,X\rangle _{\mathbb {S} ^{n}}\leq t}$(y las demás restricciones también se cumplen) o una indicación de que no existe tal solución. El algoritmo realiza una búsqueda binaria para encontrar el umbral mínimo.${\displaystyle t}$para lo cual una solución${\displaystyle X}$aún existe: esto proporciona la solución mínima al problema SDP.

El algoritmo cuántico proporciona una mejora cuadrática con respecto al mejor algoritmo clásico en el caso general, y una mejora exponencial cuando las matrices de entrada son de bajo rango .

Para la optimización combinatoria, el algoritmo de optimización aproximada cuántica (QAOA) ^{[ 6 ]} tuvo brevemente una mejor relación de aproximación que cualquier algoritmo clásico conocido de tiempo polinomial (para un problema determinado), ^{[ 7 ]} hasta que se propuso un algoritmo clásico más eficaz. ^{[ 8 ]} La aceleración relativa del algoritmo cuántico es una cuestión de investigación abierta.

QAOA consta de los siguientes pasos:

1. Definición de un hamiltoniano de coste${\displaystyle H_{C}}$de tal manera que su estado fundamental codifica la solución al problema de optimización.
2. Definición de un hamiltoniano de mezclador${\displaystyle H_{M}}$.
3. Definiendo los oráculos${\displaystyle U_{C}(\gamma )=\exp(-\imath \gamma H_{C})}$y${\displaystyle U_{M}(\alpha )=\exp(-\imath \alpha H_{M})}$, con parámetros${\displaystyle \gamma }$y α.
4. Aplicación repetida de los oráculos${\displaystyle U_{C}}$y${\displaystyle U_{M}}$, en el orden:${\displaystyle U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})=\coprod _{i=1}^{N}(U_{C}(\gamma _{i})U_{M}(\alpha _{i}))}$
5. Preparar un estado inicial, que es una superposición de todos los estados posibles y aplicar${\displaystyle U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})}$al estado.
6. Utilizar métodos clásicos para optimizar los parámetros${\displaystyle {\boldsymbol {\gamma }},{\boldsymbol {\alpha }}}$y medir el estado de salida del circuito optimizado para obtener la solución óptima aproximada del hamiltoniano de costo. Una solución óptima será aquella que maximice el valor esperado del hamiltoniano de costo.${\displaystyle H_{C}}$.

La estructura del algoritmo, es decir, el uso de hamiltonianos de costo y mezclador, se inspira en el teorema adiabático cuántico , que establece que, partiendo de un estado fundamental de un hamiltoniano dependiente del tiempo, si el hamiltoniano evoluciona lo suficientemente lento, el estado final será un estado fundamental del hamiltoniano final. Además, el teorema adiabático puede generalizarse a cualquier otro autoestado siempre que no haya superposición (degeneración) entre diferentes autoestados a lo largo de la evolución. Identificando el hamiltoniano inicial con${\displaystyle H_{M}}$y el hamiltoniano final con${\displaystyle H_{C}}$, cuyos estados fundamentales codifican la solución al problema de optimización de interés, se puede aproximar el problema de optimización como la evolución adiabática del hamiltoniano desde un estado inicial hasta uno final, cuyo estado fundamental (auto) proporciona la solución óptima. En general, QAOA se basa en el uso de operadores unitarios que dependen de${\displaystyle 2p}$ángulos (parámetros), donde${\displaystyle p>1}$es un número entero de entrada, que puede identificarse como el número de capas del oráculo.${\displaystyle U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})}$Estos operadores se aplican iterativamente sobre un estado que es una superposición cuántica de igual peso de todos los estados posibles en la base computacional. En cada iteración, el estado se mide en la base computacional y la función booleana${\displaystyle C(z)}$se estima. Los ángulos se actualizan luego de forma clásica para aumentar${\displaystyle C(z)}$. Después de repetir este procedimiento un número suficiente de veces, el valor de${\displaystyle C(z)}$es casi óptimo, y el estado que se está midiendo también está cerca de ser óptimo. En la figura se muestra un circuito de ejemplo que implementa QAOA en una computadora cuántica. Este procedimiento se ilustra con el siguiente ejemplo de cómo encontrar la cobertura mínima de vértices de un grafo. ^{[ 9 ]}

El objetivo es encontrar una cobertura mínima de vértices para un grafo: un conjunto de vértices tal que cada arista del grafo contenga al menos uno de los vértices de la cobertura. Por lo tanto, estos vértices "cubren" todas las aristas. Buscamos una cobertura de vértices con el menor número posible de vértices. Las coberturas de vértices se pueden representar mediante una cadena de bits, donde cada bit indica si el vértice correspondiente está presente en la cobertura. Por ejemplo, la cadena de bits 0101 representa una cobertura formada por el segundo y el cuarto vértice de un grafo con cuatro vértices.

Consideremos el grafo que se muestra en la figura. Tiene cuatro vértices y existen dos coberturas mínimas de vértices para este grafo: los vértices 0 y 2, y los vértices 1 y 2. Estos se pueden representar respectivamente mediante las cadenas de bits 1010 y 0110. El objetivo del algoritmo es muestrear estas cadenas de bits con alta probabilidad. En este caso, el hamiltoniano de costo tiene dos estados fundamentales, |1010⟩ y |0110⟩, que coinciden con las soluciones del problema. El hamiltoniano del mezclador es la suma simple y no conmutativa de operaciones de Pauli-X en cada nodo del grafo y se define como:

${\displaystyle H_{C}=-0.25Z_{3}+0.5Z_{0}+0.5Z_{1}+1.25Z_{2}+0.75(Z_{0}Z_{1}+Z_{0}Z_{2}+Z_{2}Z_{3}+Z_{1}Z_{2})}$

${\displaystyle H_{M}=X_{0}+X_{1}+X_{2}+X_{3}}$

La implementación del algoritmo QAOA para este circuito de cuatro cúbits con dos capas del ansatz en qiskit (ver figura) y su posterior optimización dan como resultado la distribución de probabilidad para los estados que se muestra en la figura. Esto demuestra que los estados |0110⟩ y |1010⟩ tienen las mayores probabilidades de ser medidos, tal como se esperaba.

En principio, el valor óptimo de${\displaystyle C(z)}$Se puede alcanzar una precisión arbitraria, lo cual está garantizado por el teorema adiabático ^{[ 10 ] [ 11 ]} o, alternativamente, por la universalidad de las unitarias QAOA ^{[ 12 ]} . Sin embargo, es una cuestión abierta si esto se puede lograr de manera factible. Por ejemplo, se demostró que QAOA presenta una fuerte dependencia de la relación entre la restricción y las variables del problema (densidad del problema), lo que impone una restricción limitante a la capacidad del algoritmo para minimizar una función objetivo correspondiente ^{[ 13 ]} .

Pronto se reconoció que una generalización del proceso QAOA consiste esencialmente en la aplicación alternada de un paseo cuántico en tiempo continuo sobre un grafo subyacente, seguido de un cambio de fase dependiente de la calidad aplicado a cada estado de la solución. Este QAOA generalizado se denominó QWOA (Algoritmo de Optimización Basado en Paseos Cuánticos). ^{[ 14 ]}

En el artículo ¿Cuántos cúbits se necesitan para la supremacía computacional cuántica? enviado a arXiv, ^{[ 15 ]} los autores concluyen que un circuito QAOA con 420 cúbits y 500 restricciones requeriría al menos un siglo para ser simulado utilizando un algoritmo de simulación clásico que se ejecute en supercomputadoras de última generación, por lo que eso sería suficiente para la supremacía computacional cuántica .

Una comparación rigurosa de QAOA con algoritmos clásicos puede proporcionar estimaciones sobre la profundidad.${\displaystyle p}$y el número de cúbits necesarios para la ventaja cuántica. Un estudio del algoritmo QAOA y MaxCut muestra que${\displaystyle p>11}$es necesario para obtener una ventaja escalable. ^{[ 16 ]}

Se han propuesto varias variaciones a la estructura básica de QAOA ^{[ 17 ]} , que incluyen variaciones en el ansatz del algoritmo básico. La elección del ansatz generalmente depende del tipo de problema, como problemas combinatorios representados como grafos o problemas fuertemente influenciados por el diseño del hardware. Sin embargo, el diseño del ansatz debe equilibrar la especificidad y la generalidad para evitar el sobreajuste y mantener la aplicabilidad a una amplia gama de problemas. Por esta razón, el diseño de ansatz óptimos para QAOA es un tema ampliamente investigado. Algunas de las variantes propuestas son:

1. QAOA multiángulo ^{[ 18 ]}
2. QAOA expresivo (XQAOA) ^{[ 19 ]}
3. QAOA+ ^{[ 20 ]}
4. QAOA contraadiabático digitalizado ^{[ 21 ]}
5. Ansatz de operador alternante cuántico ^{[ 22 ]} , que permite restricciones en el problema de optimización, etc.

Otra variante de QAOA se centra en técnicas de optimización de parámetros, cuyo objetivo es seleccionar el conjunto óptimo de parámetros iniciales para un problema dado y evitar mesetas estériles, que representan parámetros que conducen a autoestados que corresponden a mesetas en el paisaje energético del hamiltoniano de coste.

Finalmente, se ha observado un gran interés en la investigación sobre el aprovechamiento de hardware específico para mejorar el rendimiento de QAOA en diversas plataformas, como iones atrapados, átomos neutros, cúbits superconductores y computadoras cuánticas fotónicas. Los objetivos de estos enfoques incluyen superar las limitaciones de conectividad del hardware y mitigar los problemas relacionados con el ruido para ampliar la aplicabilidad de QAOA a una amplia gama de problemas de optimización combinatoria.