A quantum unstructured search algorithm for discrete optimisation: the use case of portfolio optimisation

Resumen Técnico: Un Algoritmo de Búsqueda Cuántica No Estructurada para la Optimización Discreta

Planteamiento del Problema
El artículo aborda el desafío de resolver problemas de optimización discreta, específicamente la optimización combinatoria, donde las variables son binarias y no se pueden definir derivadas. Mientras que los métodos basados en gradientes son efectivos para variables continuas, fallan en espacios discretos, que a menudo son NP-duros. Los enfoques cuánticos existentes, como el marco de Optimización Binaria No Restringida Cuadrática (QUBO), están limitados a funciones objetivo que contienen únicamente términos de primer y segundo orden. Además, muchos algoritmos de optimización cuántica actuales (por ejemplo, Algoritmos Cuánticos Variacionales) dependen de bucles híbridos clásico-cuánticos que pueden sufrir de ruido o requerir circuitos profundos. Los autores proponen un método para encontrar los extremos o raíces de funciones discretas generales, $f(x)$, que pueden contener términos de orden superior más allá del límite cuadrático de QUBO.

Metodología: El Algoritmo QSERA
Los autores introducen el Algoritmo de Búsqueda Cuántica para Extremos y Raíces (QSERA), un miembro de la familia de Algoritmos de Búsqueda Cuántica (QSA) basados en el algoritmo de Grover. La metodología procede en dos pasos primarios:

1. Construcción del Oráculo ($f(x) \to u(z)$):
   El primer paso consiste en mapear la condición de encontrar un extremo (o raíz) $f(x^*) \approx f^*$ a un problema de búsqueda no estructurada para una cadena binaria $z^*$.

   • Reescalado: La función objetivo $f(x)$ se reescala a una función $g(x) \in [0, 1]$. Para la maximización, $g(x) = (f(x) - f_{min}) / (f_{max} - f_{min})$; para la minimización, $g(x) = (f_{max} - f(x)) / (f_{max} - f_{min})$; y para la búsqueda de raíces, se aplica una transformación específica. Esto requiere conocimiento a priori o estimaciones del mínimo global ($f_{min}$) y el máximo global ($f_{max}$).
   • Amplificación: Para crear un oráculo binario $u(z)$ donde $u(z^*) = 1$ y $u(z \neq z^*) = 0$, la función $g(x)$ se eleva a una potencia alta $n$ (es decir, $u_n(z) \equiv g(x)^n$). A medida que $n \to \infty$, $u_n(z)$ se aproxima al oráculo ideal.
   • Generalización: El artículo señala que $f(x)$ puede ser un polinomio general con términos hasta el orden $K$ (Ec. 10), lo que permite funciones objetivo más complejas que la forma QUBO estándar.
   • Implementación de Puertas: Los autores derivan el circuito cuántico para el oráculo. Definen operadores autoadjuntos $B_k$ correspondientes a variables binarias y construyen un operador unitario $G$ tal que $G|z\rangle = g(x)|z\rangle$. El operador del oráculo $Q^*$ se define entonces como $e^{i\pi G^n}$. Este se descompone en un producto de operadores unitarios $Q^*_j$ para cada orden de términos (ceros, primero, segundo, etc.), implementados mediante cúbits auxiliares (ancillas) y puertas de desplazamiento de fase.

2. Ejecución de la Búsqueda:
   Una vez construido el oráculo $Q^*$, el algoritmo emplea el operador de difusión de Grover ($Q_+$) y el oráculo ($Q^*$) en un bucle iterativo. El estado se inicializa en una superposición uniforme y se aplica el operador $(Q_+ Q^*)$ $m_{opt} \approx (\pi\sqrt{N} - 2)/4$ veces para amplificar la amplitud del estado objetivo $|z^*\rangle$.

Contribuciones Clave

• Generalización más allá de QUBO: A diferencia de muchos métodos de optimización cuántica restringidos a formas cuadráticas, QSERA puede manejar funciones objetivo con términos de orden superior (cúbicos, cuárticos, etc.), lo que lo hace aplicable a una clase más amplia de problemas combinatorios.
• Construcción Explícita de Circuitos: El artículo proporciona una derivación matemática detallada para la construcción de las puertas del oráculo cuántico para órdenes polinómicos arbitrarios, incluyendo el cálculo recursivo de los coeficientes necesarios para los parámetros del circuito.
• Manejo de Límites Aproximados: Los autores analizan el escenario en el que $f_{min}$ y $f_{max}$ no se conocen exactamente. Demuestran que, aunque el algoritmo aún puede funcionar con estimaciones, la probabilidad de encontrar el óptimo exacto depende de la elección del parámetro de potencia $n$. Si $n$ es demasiado grande, la señal del oráculo puede desvanecerse; si es demasiado pequeño, la señal no es lo suficientemente distinta. Existe un $n$ óptimo para equilibrar estos factores.

Resultados: Caso de Estudio de Optimización de Cartera
Los autores validan QSERA utilizando un problema de optimización de cartera con $N_a = 4$ activos, lo que resulta en $N=16$ carteras posibles.

• Configuración: El objetivo era encontrar una cartera de 2 activos que minimizara la distancia al rendimiento de referencia y la volatilidad. La función objetivo incluyó términos hasta el cuarto orden.
• Implementación: Se ensambló un circuito cuántico utilizando 4 cúbits para los estados de la cartera, 2 cúbits auxiliares para operaciones AND y 1 auxiliar para el seguimiento de fase.
• Desempeño:
  • Con el número óptimo de iteraciones de Grover ($m_{opt} = 2$) y un valor de $n \approx 24$ cuidadosamente elegido, el algoritmo identificó con éxito la cartera óptima (estado $|1001\rangle$) con la mayor probabilidad.
  • La segunda mejor cartera ($|0101\rangle$) también mostró una probabilidad relativamente alta, reflejando el hecho de que el algoritmo encontró la solución más cercana a los límites estimados.
  • El estudio confirmó que si $f_{min}$ y $f_{max}$ se estiman en lugar de conocerse exactamente, la probabilidad de medir el verdadero óptimo es menor que 1, lo que requiere múltiples "disparos" (ejecuciones repetidas) para distinguir el verdadero óptimo de las soluciones casi óptimas.
  • La relación entre la potencia $n$ y la probabilidad de éxito se visualizó, mostrando un pico de probabilidad para valores intermedios de $n$, con un desempeño que se degrada si $n$ es demasiado grande (supresión de la señal) o demasiado pequeño (discriminación insuficiente).

Significancia y Reivindicaciones
El artículo afirma que QSERA ofrece una aceleración cuadrática ($O(\sqrt{N})$) sobre la búsqueda clásica de fuerza bruta para encontrar extremos o raíces de funciones discretas. Su principal significancia radica en su capacidad para:

1. Resolver problemas de optimización con funciones objetivo de orden superior que son incompatibles con las formulaciones QUBO estándar.
2. Operar sin la necesidad de bucles de optimización de parámetros híbridos clásico-cuánticos (a diferencia de los VQAs), basándose en su lugar en una ejecución cuántica de disparo único (aunque pueden ser necesarios múltiples disparos para la confianza estadística si los límites son aproximados).
3. Abordar potencialmente funciones continuas "ruidosas" o de gradiente pronunciado (tras la discretización) donde los métodos basados en gradientes podrían fallar, aunque los autores señalan que la búsqueda estructurada es generalmente más eficiente para variables continuas.

Los autores concluyen que, si bien el algoritmo requiere el conocimiento de los límites de la función para garantizar el éxito, sigue siendo una herramienta robusta para la optimización discreta, particularmente cuando la estructura de la función objetivo excede las capacidades de los enfoques basados en QUBO actuales.