QUBO y optimización de carteras

Markowitz nos entregó una máquina preciosa. Aliméntala con rentabilidades esperadas y una matriz de covarianzas, dale a la manivela y sale la cartera con el menor riesgo para una rentabilidad objetivo. Para la versión continua de ese problema — “mantén cualquier fracción de cada activo” — la máquina está genuinamente resuelta: es un programa cuadrático convexo, y podemos descifrarlo en tiempo polinómico antes de comer.

Entonces entra un gestor de carteras y dice: “Encantador. Pero quiero mantener exactamente 8 nombres, nunca una posición menor del 2% y solo en lotes redondos de 100 acciones”. Y la preciosa máquina convexa se atasca. Esas peticiones de aspecto inocente convierten un problema de tiempo polinómico en uno combinatorio — del tipo que, en el peor caso, es NP-difícil.

Esta lección trata de ese cambio de fase, y de la apuesta que la computación cuántica hace sobre él. Reformularemos el problema discreto de cartera como un QUBO (Quadratic Unconstrained Binary Optimization, optimización binaria cuadrática sin restricciones), veremos cómo un recocedor cuántico (D-Wave) y QAOA (modelo de puertas) atacan un QUBO y — crucialmente — mantendremos la cabeza fría sobre si algo de esto bate hoy por hoy a un buen resolutor clásico. Adelanto desde el principio: las matemáticas son reales y elegantes; la ventaja es, a día de hoy, mayormente aspiracional.

Por qué las carteras continuas son fáciles y las discretas difíciles

Analogía. El problema continuo es hacer rodar una canica hasta el fondo de un cuenco liso: empieces donde empieces, la gravedad te desliza hasta el único punto más bajo. El problema discreto es encontrar el valle más bajo de una vasta cordillera pero pudiendo solo pisar un conjunto finito de cumbres. No hay pendiente que seguir — debes, en principio, comprobar combinaciones.

Definición — media–varianza continua. Con pesos $w \in \mathbb{R}^n$, rentabilidades esperadas $\mu$, covarianza $\Sigma$ y aversión al riesgo $q$, Markowitz minimiza

$\min_{w}\; q\, w^{\top}\Sigma\,w \;-\; \mu^{\top} w \quad\text{s.a.}\quad \sum_i w_i = 1.$

Como $\Sigma$ es semidefinida positiva, el objetivo es convexo y la restricción es lineal. Los programas cuadráticos convexos se resuelven en tiempo polinómico (métodos de punto interior). Este es el mundo “fácil”.

Donde se rompe. Los mandatos reales añaden restricciones que no son convexas:

• Cardinalidad: mantener exactamente (o como mucho) $k$ de los $n$ nombres.
• Tamaños mínimos de lote / posición: una posición es $0$ o al menos cierto suelo (p. ej. al menos un 2% o al menos 100 acciones) — una variable “semicontinua”.
• Umbrales de entrada / lotes redondos: los pesos deben caer en una rejilla discreta.

Cada una de estas introduce una decisión sí/no por activo. Con $n$ activos hay hasta $2^n$ combinaciones de encendido/apagado, y la región factible ya no es una única mancha convexa — es una dispersión de islas inconexas. La ramificación y poda puede podar, pero el peor caso es exponencial. Este núcleo combinatorio es exactamente lo que QAOA y el recocido cuántico afirman atacar.

Ejemplo resuelto — la explosión. Elige los 5 mejores nombres de entre 30 por fuerza bruta: $\binom{30}{5} = 142{,}506$ carteras — trivial. Ahora los 15 mejores de entre 100: $\binom{100}{15} \approx 2.5 \times 10^{17}$. A mil millones de evaluaciones por segundo eso son aproximadamente 8 años de cómputo para un único reajuste. La versión continua del mismo problema de 100 activos se resuelve en milisegundos. El enemigo es la discretitud, no el tamaño.

Cuándo usarlo

Quédate en el mundo continuo convexo siempre que legítimamente puedas — si la única restricción “discreta” es blanda (una preferencia, no una regla dura), codifícala como penalización en un resolutor convexo y sigue adelante. Recurre a la maquinaria combinatoria (y solo entonces considera lo cuántico) cuando la discretitud sea una restricción de negocio dura y vinculante: un recuento fijo de nombres, un tamaño de lote regulatorio, un ticket mínimo que no se puede fraccionar.

QUBO: minimizar x-transpuesta Q x sobre x binario

Analogía. Un QUBO es un conjunto de interruptores de luz (uno por activo, cada uno encendido o apagado) cableados entre sí de modo que cada par de interruptores tiene una recompensa o penalización por estar encendidos a la vez, y cada interruptor tiene su propia recompensa en solitario por estar encendido. Buscas la configuración de interruptores con la menor “energía” total. Ese es el modelo entero — pares más individuales, nada más.

Definición. Un QUBO es

$\min_{x \in \{0,1\}^n}\; x^{\top} Q\, x \;=\; \min_{x}\; \sum_{i} Q_{ii}\, x_i \;+\; \sum_{i < j} Q_{ij}\, x_i x_j,$

donde $Q$ es una matriz $n \times n$ y usamos $x_i^2 = x_i$ para fundir los términos lineales en la diagonal. “Sin restricciones” significa que no hay restricciones de igualdad/desigualdad aparte — toda preferencia y regla debe hornearse dentro de $Q$, normalmente como una penalización cuadrática.

Mapeando media–varianza + cardinalidad sobre un QUBO. Sea $x_i = 1$ si mantenemos el activo $i$ (ponderamos por igual los nombres elegidos por simplicidad). Queremos tres cosas:

1. Premiar la rentabilidad esperada — un término lineal $-\mu_i x_i$ (negativo porque minimizamos). Pliégalo en la diagonal: baja $Q_{ii}$.
2. Penalizar el riesgo — un término cuadrático $q\,\sigma_{ij} x_i x_j$ procedente de la covarianza. En la diagonal suma varianza; fuera de la diagonal suma covarianza.
3. Imponer la cardinalidad “elige exactamente $k$” con una penalización $\lambda\big(\sum_i x_i - k\big)^2$ para un peso grande $\lambda$. Esta es cero cuando hay exactamente $k$ interruptores encendidos y estrictamente positiva en caso contrario.

Expandir la penalización es el truco clave:

$\lambda\Big(\textstyle\sum_i x_i - k\Big)^2 = \lambda\Big(\sum_i x_i^2 + 2\!\!\sum_{i<j}\! x_i x_j - 2k\!\sum_i x_i + k^2\Big),$

y usando $x_i^2 = x_i$ esto aporta $\lambda(1 - 2k)$ a cada diagonal $Q_{ii}$ y $2\lambda$ a cada par fuera de la diagonal $Q_{ij}$ (el $\lambda k^2$ es un desplazamiento constante que no cambia qué $x$ es el mejor).

Ejemplo resuelto — un QUBO de 3 activos. Tres activos, elige exactamente $k = 2$. Toma aversión al riesgo $q = 1$, penalización $\lambda = 5$ y estos números (de juguete):

Covarianzas por pares: $\sigma_{AB}=0.01,\ \sigma_{AC}=0.00,\ \sigma_{BC}=0.005$.

Construye $Q$ término a término. Diagonal $Q_{ii} = -\mu_i + q\,\sigma_{ii} + \lambda(1 - 2k)$. Con $k=2$, $\lambda(1-2k) = 5(1-4) = -15$:

• $Q_{AA} = -0.10 + 0.04 - 15 = -15.06$
• $Q_{BB} = -0.08 + 0.02 - 15 = -15.06$
• $Q_{CC} = -0.06 + 0.01 - 15 = -15.05$

Fuera de la diagonal $Q_{ij} = 2q\,\sigma_{ij} + 2\lambda$. Con $2\lambda = 10$:

• $Q_{AB} = 2(0.01) + 10 = 10.02$
• $Q_{AC} = 2(0.00) + 10 = 10.00$
• $Q_{BC} = 2(0.005) + 10 = 10.01$

Ahora evalúa la energía $E(x) = x^{\top} Q x$ para dos selecciones candidatas (la constante $\lambda k^2 = 20$ es la misma para todo $x$, así que la descartamos y comparamos energías relativas). Energía = suma de las entradas diagonales de los activos elegidos + el término fuera de la diagonal de cada par elegido.

Candidata 1 — elige A y B ($x = (1,1,0)$), que cumple la restricción (2 nombres):

$E_{AB} = Q_{AA} + Q_{BB} + Q_{AB} = -15.06 - 15.06 + 10.02 = -20.10.$

Candidata 2 — elige solo A ($x = (1,0,0)$), que viola la restricción (1 nombre):

$E_{A} = Q_{AA} = -15.06.$

La cartera válida de dos nombres tiene la energía más baja (mejor), $-20.10 \le -15.06$ — la penalización hizo su trabajo: quedarse corto deja sin reclamar un buen trozo de las recompensas diagonales de $-15$. Para completar, los tres pares válidos:

El óptimo aquí es A + C con $-20.11$ — agarra las dos mejores diagonales de rentabilidad/riesgo pagando la penalización por pares más baja (su covarianza es cero). Fíjate en lo cerca que están las energías válidas: los QUBO reales tienen un paisaje escarpado donde el mejor y el segundo mejor difieren en un pelo, que es exactamente lo que hace difícil la búsqueda.

Cuándo usarlo

Recurre a una formulación QUBO cuando tu problema trate nativamente de decisiones de encendido/apagado con interacciones por pares — activo dentro o fuera, arista dentro o fuera, bit puesto o no — y cuando tus restricciones puedan escribirse como penalizaciones cuadráticas. Si tus variables son genuinamente continuas (pesos fraccionarios), forzarlas a QUBO mediante expansión binaria (un bit por cada 0.1% de peso) infla el número de variables y suele ser un paso atrás.

La equivalencia de Ising

Un QUBO sobre $x_i \in \{0,1\}$ y un modelo de Ising sobre espines $s_i \in \{-1,+1\}$ son la misma optimización con ropajes distintos. Sustituye $x_i = (1 + s_i)/2$ y cualquier QUBO se convierte en un hamiltoniano de Ising

$H(s) = \sum_{i<j} J_{ij}\, s_i s_j \;+\; \sum_i h_i\, s_i \;+\; \text{const},$

donde $J_{ij}$ son las intensidades de acoplamiento y $h_i$ son los campos locales, ambos funciones lineales del $Q$ original. Esta única línea importa porque los recocedores cuánticos minimizan energías de Ising nativamente — el hardware es un vidrio de espín programable. Así que “resuelve mi QUBO de cartera” se convierte en “fija estos acopladores y campos, y deja que la física se relaje hasta el estado fundamental”. Guárdate la equivalencia en el bolsillo; el resto de la lección usa QUBO e Ising indistintamente.

Recocido cuántico: el descenso adiabático

Analogía. El recocido (annealing) toma su nombre de la metalurgia por una razón. Calienta un metal hasta que sus átomos vibran libremente, luego enfríalo despacio: los átomos se asientan en un cristal ordenado de baja energía. Enfríalo rápido (témplalo) y se congelan en un vidrio desordenado de alta energía. El recocido cuántico hace el mismo truco sobre el paisaje de energía de un problema — “enfría” un sistema cuántico con la lentitud suficiente para que se deslice hasta el valle más bajo (el óptimo) en vez de quedarse atascado en una abolladura local.

Definición — recocido adiabático / cuántico. La máquina prepara el estado fundamental de un hamiltoniano impulsor $H_0$ sencillo (uno cuyo estado de menor energía es fácil y conocido — una superposición uniforme de todas las configuraciones). Luego interpola lentamente hasta el hamiltoniano del problema $H_P$ que codifica tu modelo de Ising:

$H(t) = \Big(1 - \tfrac{t}{T}\Big) H_0 \;+\; \tfrac{t}{T}\, H_P, \qquad 0 \le t \le T.$

Por el teorema adiabático, si el tiempo total $T$ es largo comparado con $1/g_{\min}^2$ — donde $g_{\min}$ es el menor hueco de energía entre el estado fundamental y el primer estado excitado a lo largo del camino — el sistema se mantiene en el estado fundamental, y en $t = T$ una medición devuelve el óptimo de $H_P$. Ese hueco es la trampa: para problemas difíciles puede encogerse exponencialmente, exigiendo un recocido exponencialmente largo.

Juega con la isla de arriba antes de seguir leyendo. Fíjate en tres cosas que te compra la física: la búsqueda acepta movimientos cuesta arriba ocasionales mientras está caliente (para no quedar atrapada en el primer hoyo), esos saltos cuesta arriba se encogen según cae la temperatura (de modo que al final se compromete), y el indicador de restricción puede parpadear en rojo a mitad de búsqueda — un QUBO no prohíbe los estados inválidos, simplemente los hace caros, así que el recocedor deambula por ellos camino abajo.

Ejemplo resuelto — por qué “con suficiente lentitud” puede ser ruinoso. Supón que el hueco mínimo en un problema concreto es $g_{\min} = 0.01$ (unidades de energía). La condición adiabática exige aproximadamente $T \gtrsim 1/g_{\min}^2 = 1/(0.01)^2 = 10{,}000$ unidades de tiempo. Reduce a la mitad el hueco a $0.005$ y el tiempo requerido se cuadruplica a $40{,}000$. Para instancias genuinamente difíciles el hueco se cierra exponencialmente con el tamaño del problema, así que el tiempo de recocido “garantizado” se dispara exponencialmente — que es precisamente por qué los recocidos reales de D-Wave son cortos y repetidos y se tratan como una heurística, no como una garantía.

Cuándo usarlo

El recocido cuántico merece un piloto cuando tu problema tiene forma de Ising nativamente, es disperso (para que la sobrecarga de embebido siga siendo manejable) y te conformas con una buena respuesta heurística en vez de un óptimo certificado. Trátalo como tratarías el recocido simulado o la búsqueda tabú: ejecútalo muchas veces, quédate con la mejor muestra y siempre compáralo con un resolutor clásico fuerte sobre la misma instancia antes de reclamar beneficio alguno.

QAOA: el primo variacional del modelo de puertas

Analogía. Si el recocido es una canica enfriándose hasta un valle, QAOA es una carrera de relevos entre dos entrenadores. Un entrenador (el hamiltoniano del problema) empuja al equipo hacia configuraciones de bajo coste; el otro (el mezclador) sacude las cosas para que el equipo explore. Se alternan durante $p$ rondas, y un optimizador clásico fuera de la carrera ajusta cuánto tiempo tiene cada entrenador el testigo (los ángulos) para hacer la alineación final lo más barata posible.

Definición — QAOA. El Algoritmo de Optimización Aproximada Cuántica (Quantum Approximate Optimization Algorithm) prepara un estado alternando $p$ capas de un unitario del problema $e^{-i\gamma_\ell H_P}$ (que codifica tu coste de Ising) y un unitario mezclador $e^{-i\beta_\ell H_M}$ (típicamente volteos de espín de campo transversal):

$|\boldsymbol{\gamma},\boldsymbol{\beta}\rangle = \prod_{\ell=1}^{p} e^{-i\beta_\ell H_M}\, e^{-i\gamma_\ell H_P}\, |+\rangle^{\otimes n}.$

Un optimizador clásico ajusta los $2p$ ángulos $(\boldsymbol{\gamma},\boldsymbol{\beta})$ para minimizar la energía esperada medida $\langle H_P \rangle$. Es un bucle cuántico-clásico: el chip cuántico evalúa el coste de una configuración de parámetros, el optimizador clásico propone la siguiente configuración. Cuando $p \to \infty$ las capas pueden imitar el barrido adiabático lento, así que QAOA puede en principio alcanzar el óptimo.

Ejemplo resuelto — el coste de la profundidad. A profundidad $p$ debes optimizar $2p$ ángulos. Para un modesto $p = 5$ eso son 10 parámetros — y cada evaluación significa ejecutar el circuito y muestrearlo miles de veces para estimar $\langle H_P \rangle$ con precisión aceptable. Digamos 5.000 disparos por evaluación y 200 pasos del optimizador: eso son $10 \times 200 \times 5{,}000 = 10{,}000{,}000$ ejecuciones de circuito para un problema, en hardware donde cada puerta multicúbit inyecta ruido. Una $p$ más profunda significa circuitos más profundos, más acumulación de ruido y un paisaje de ángulos de mayor dimensión que buscar.

Cuándo usarlo

Hoy, QAOA es principalmente una herramienta de investigación y aprendizaje, no un optimizador de carteras de producción. Úsalo para entender los algoritmos cuánticos variacionales, para comparar instancias pequeñas y para seguir el campo — pero no apuestes un reajuste a él esperando que bata a la ramificación y poda o al recocido simulado. Si estás ejecutando QAOA en serio, mantén $p$ baja, arranca en caliente los ángulos desde valores buenos conocidos o el calendario adiabático y (de nuevo) compara siempre clásicamente sobre la instancia idéntica.

El veredicto sobrio

Hora de la verdad poco glamurosa. La optimización combinatoria clásica es muy buena. Los resolutores comerciales de programación entera mixta (MIP) que usan ramificación y poda y planos de corte descifran rutinariamente carteras con restricción de cardinalidad de cientos de activos hasta la optimalidad certificada, y las metaheurísticas como el recocido simulado y la búsqueda tabú entregan excelentes soluciones casi óptimas rápido cuando no se requiere exactitud. El recocido cuántico y QAOA son científicamente fascinantes y pueden algún día ayudar en instancias con estructura discreta especialmente desagradable — pero a día de hoy no se ha demostrado ninguna ventaja clara y reproducible sobre estos métodos clásicos en problemas realistas de cartera.

La postura disciplinada es la misma que toda esta asignatura predica sobre el aprendizaje automático: compara honestamente, desconfía del bombo y deja que la base clásica tenga la primera y la última palabra. Si un proveedor demuestra una victoria cuántica de cartera, pregunta si pasó la misma instancia por un resolutor clásico afinado — la respuesta suele ser que no lo hizo, o que el resolutor clásico también ganó.

Cuándo usarlo

Por defecto, ve a lo clásico: un resolutor MIP cuando necesites un óptimo certificado y la instancia sea tratable, recocido simulado o tabú cuando necesites respuestas rápidas y suficientemente buenas en QUBO grandes. Considera el recocido cuántico solo para instancias discretas dispersas y genuinamente difíciles y solo como un piloto comparado. Trata QAOA como un instrumento de investigación. En todos los casos, la regla es idéntica: ejecuta la base clásica sobre la misma instancia y cree a los números por encima de la narrativa.

Resumen

Viste una preciosa máquina convexa atascarse en el momento en que un gestor de carteras pidió un recuento fijo de nombres, un lote mínimo o una rejilla de acciones redondas — el precipicio de la convexidad que convierte la media–varianza de tiempo polinómico en una búsqueda combinatoria y NP-difícil. Reformulaste esa búsqueda como un QUBO (minimizar $x^\top Q x$ sobre $x$ binario), plegando la rentabilidad en la diagonal, el riesgo en el término cuadrático y la regla de cardinalidad en una penalización $\lambda(\sum x_i - k)^2$. Viste la equivalencia de Ising de una línea que permite al hardware de recocido minimizarlo nativamente, el descenso adiabático del recocido cuántico (y sus salvedades de hueco y embebido) y el bucle variacional de QAOA (y sus mesetas yermas). Y terminaste donde un experto debería: los resolutores clásicos son fuertes, la ventaja cuántica en carteras reales no está aún demostrada, y la jugada honesta es siempre comparar.