Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly

Título: Enfoques de optimización cuántica no variacional para el ensamblaje de secuencias guiado por pangenomas

1. El Problema: Ensamblaje de Genomas y Sesgo de Referencia

El ensamblaje de genomas a partir de datos de secuenciación de lecturas cortas sigue siendo un desafío significativo, especialmente en regiones repetitivas donde la complejidad combinatoria y el sesgo de referencia limitan los métodos existentes.

• Solución propuesta (PGSA): El Ensamblaje de Secuencias Guiado por Pangenomas (PGSA, por sus siglas en inglés) mitiga el sesgo de referencia reconstruyendo el genoma individual como un recorrido (walk) a través de un grafo de nivel poblacional.
• El Cuello de Botella Computacional: El problema central, denominado Resolución de Enredos Orientados (Oriented Tangle Resolution), consiste en identificar un camino en el grafo donde las visitas a los nodos coincidan con las frecuencias de copia estimadas a partir de las lecturas. Este problema es NP-duro y desafía a los solucionadores clásicos incluso a escalas moderadas.
• Objetivo del trabajo: Desarrollar enfoques de optimización cuántica a corto plazo (near-term) para resolver este cuello de botella, evaluando dos codificaciones: una formulación QUBO (Optimización Binaria Cuadrática Sin Restricciones) establecida y una nueva formulación HUBO (Optimización Binaria de Orden Superior Sin Restricciones).

2. Metodología

Los autores proponen un marco de trabajo que combina codificaciones de problemas específicas con un algoritmo cuántico heurístico no variacional.

• Codificaciones del Problema:

  • QUBO: Utiliza variables binarias para pares "nodo-tiempo". Requiere $O(N^2)$ variables (donde $N$ es el número de nodos), lo que implica un alto costo en qubits pero circuitos más superficiales.
  • HUBO (Novedad): Codifica los índices de los nodos en binario en lugar de enumerar pares nodo-tiempo. Esto reduce drásticamente el número de variables a $O(N \log N)$, permitiendo resolver instancias más grandes con menos qubits, pero introduce términos de interacción de orden superior que requieren circuitos más profundos.

• Algoritmo Cuántico: Iterative-QAOA
  En lugar de utilizar un bucle de optimización variacional completo (que es costoso y propenso a "mesetas estériles"), el estudio emplea Iterative-QAOA:

  1. Programa Fijo (Linear-Ramp): Utiliza un programa de parámetros fijo (LR-QAOA) donde los ángulos de rotación siguen una rampa lineal, evitando la optimización clásica de parámetros.
  2. Actualización de Sesgos Iterativa: El estado inicial se "calienta" (warm-start) basándose en los resultados de iteraciones anteriores. Se calculan nuevos sesgos para cada qubit utilizando las cadenas de bits medidas y sus energías, guiando progresivamente la búsqueda hacia regiones de baja energía.
  3. Post-selección (CVaR): Se utiliza una función de pérdida de Valor en Riesgo Condicional (CVaR), manteniendo solo una fracción ($\alpha$) de las mejores muestras para actualizar los sesgos, lo que mejora la robustez frente al ruido.

• Compilación de Circuitos Personalizada:
  Se desarrolló una estrategia de compilación personalizada para reducir la sobrecarga de puertas en hardware. Para HUBO, se optimiza la implementación de rotaciones Z de múltiples qubits mediante la cancelación de puertas CX y el uso de un solucionador MAX-SAT para encontrar disposiciones de qubits eficientes.

3. Contribuciones Clave

• Formulación HUBO para PGSA: Introducción de una nueva codificación HUBO que reduce la complejidad de qubits de $O(N^2)$ a $O(N \log N)$, haciendo factible el uso de dispositivos cuánticos actuales para instancias de tamaño moderado.
• Marco Iterative-QAOA No Variacional: Demostración de que combinar un programa de rampa lineal fijo con actualizaciones de sesgos iterativos es eficaz para problemas de ensamblaje, evitando la complejidad de la optimización variacional completa.
• Reducción de Sobrecarga de Hardware: La estrategia de compilación personalizada logró reducir la sobrecarga de puertas de dos qubits en hasta un 67% en comparación con las herramientas estándar (Qiskit).
• Validación en Hardware Real: Ejecución exitosa de experimentos en el dispositivo cuántico IBM Boston, demostrando la viabilidad de estos enfoques en hardware ruidoso de escala intermedia (NISQ).

4. Resultados

• Simulaciones sin Ruido (QUBO):

  • En instancias de 24 qubits, Iterative-QAOA identificó soluciones óptimas tras una sola iteración, incluso con profundidades de circuito bajas ($p=1$).
  • En instancias de 80 qubits, las profundidades intermedias ($p=3, 5$) alcanzaron soluciones óptimas en pocas iteraciones, mientras que $p=1$ mostró limitaciones de expresividad.
  • La eficiencia es notable: se encontraron soluciones óptimas explorando solo una fracción minúscula ($10^{-17}\%$) del espacio de búsqueda total.

• Resultados en Hardware (IBM Boston):

  • QUBO (24 y 48 qubits): Los resultados mitigados por errores coincidieron cualitativamente con las simulaciones sin ruido. Con una selección post-CVaR adecuada, se observaron soluciones óptimas, demostrando que el método funciona en hardware real.
  • HUBO (12 y 15 qubits): Aunque la reducción de qubits es ventajosa, los circuitos más profundos necesarios para las interacciones de alto orden mostraron mayor sensibilidad al ruido. En instancias más grandes, las soluciones óptimas aparecieron en iteraciones posteriores y con mayor desviación respecto a la simulación, evidenciando el compromiso (trade-off) entre la reducción de qubits y la profundidad del circuito.

• Comparativa QUBO vs. HUBO:

  • QUBO: Preferible cuando la fidelidad de las puertas (especialmente de dos qubits) es la limitación principal, ya que genera circuitos más superficiales.
  • HUBO: Preferible cuando el número de qubits es el recurso limitante, a pesar de requerir circuitos más profundos y una mejor mitigación de errores.

5. Significado e Impacto

Este trabajo establece el ensamblaje de pangenomas como una clase de problema concreta y motivada biológicamente donde la optimización cuántica podría proporcionar valor práctico en un futuro cercano.

• Viabilidad Práctica: Demuestra que los dispositivos cuánticos actuales pueden abordar problemas de ensamblaje que son desafiantes para los solucionadores clásicos, especialmente a escalas donde la complejidad combinatoria crece exponencialmente.
• Ruta hacia la Utilidad Cuántica: Identifica que, a medida que mejore la fidelidad del hardware y las técnicas de compilación, los enfoques HUBO podrían volverse más atractivos al superar las limitaciones de memoria (número de qubits), marcando una transición de un régimen limitado por la profundidad del circuito a uno limitado por la memoria cuántica.
• Método Heurístico Robusto: La validación de Iterative-QAOA sin bucles de optimización variacional ofrece una ruta prometedora para ejecutar algoritmos cuánticos complejos en hardware ruidoso sin la sobrecarga computacional clásica asociada.

En resumen, el artículo proporciona una prueba de concepto sólida de que la computación cuántica puede resolver subproblemas críticos en la genómica, ofreciendo un marco metodológico que equilibra la eficiencia de los qubits con las restricciones actuales del hardware.