Quantum circuit evolutionary framework applied on set partitioning problem

Este artículo propone un marco evolutivo de circuitos cuánticos que utiliza topología variable y un término evolutivo pseudo-contradiabático para resolver eficazmente problemas de partición de conjuntos superando el estancamiento de la convergencia y eliminando la necesidad de optimizadores clásicos.

Lo esencial

Imagina que estás intentando resolver un rompecabezas masivo y complejo. El objetivo es dividir un grupo de personas (como las tripulaciones de una aerolínea) en equipos para que cada vuelo sea cubierto exactamente una vez, sin solapamientos ni turnos faltantes, manteniendo al mismo tiempo los costos lo más bajos posible. En el mundo de las matemáticas, esto se llama Problema de Partición de Conjuntos. Es un desafío notoriamente difícil que se vuelve exponencialmente más complejo a medida que añades más personas y vuelos.

Este artículo introduce una nueva forma en que las computadoras cuánticas pueden abordar este rompecabezas. En lugar de utilizar la "receta" estándar que siguen la mayoría de los algoritmos cuánticos, los autores construyeron un marco que permite a la computadora evolucionar su propia receta mientras trabaja.

Aquí tienes un desglose de su enfoque utilizando analogías simples:

1. La Vieja Forma: El "Plano Fijo" (VQE)

La mayoría de los algoritmos cuánticos actuales, como el Eigensolver Cuántico Variacional (VQE), funcionan como un chef que sigue un libro de recetas estricto e inmutable.

• La Configuración: La estructura del "circuito" (los pasos que da la computadora) es fija. No puedes añadir ni quitar ingredientes; solo puedes ajustar las cantidades (los parámetros).
• El Problema: A medida que el rompecabezas se hace más grande, el chef a menudo se queda atascado en un "valle plano". Imagina caminar en un campo neblinoso donde el suelo es perfectamente plano. No importa hacia dónde pases, no subes ni bajas. No puedes decir si te estás acercando a la solución o no. En física cuántica, esto se llama una Meseta Árida. La computadora deja de aprender porque no puede encontrar una dirección para mejorar.

2. La Nueva Forma: El "Escultor Evolutivo" (QCE)

Los autores proponen un marco llamado Evolución de Circuitos Cuánticos (QCE). En lugar de una receta fija, imagina a un escultor que comienza con un pequeño montón de arcilla y tiene permitido añadir, quitar o remodelar la arcilla en cada paso.

• Cómo funciona: La computadora comienza con un circuito muy simple (quizás solo una puerta). Luego crea una "familia" de versiones ligeramente diferentes de sí misma mutando aleatoriamente la estructura (añadiendo un nuevo paso, eliminando uno antiguo o cambiando una conexión).
• La Selección: Prueba todas estas versiones. La que resuelve el rompecabezas mejor sobrevive para ser la "progenitora" de la siguiente ronda. Las demás se descartan.
• El Beneficio: Dado que la estructura misma está cambiando, la computadora no queda atrapada en un valle plano. Puede remodelar todo su enfoque para encontrar un camino fuera de la niebla.

3. Las Dos Estrategias Probadas

El artículo probó dos sabores específicos de este enfoque de "Escultor Evolutivo":

• Estrategia A: El Evolucionista Puro (Sin Ansatz)
  Esta versión comienza con casi nada y deja que la computadora determine la estructura completamente mediante prueba y error, muy parecido a la selección natural. No adivina cómo debería verse la solución; simplemente evoluciona hasta que funciona.

• Estrategia B: El Evolucionista Inspirado en la Física (Pseudo-Contradiabático)
  Esta es la "estrella" del artículo. Los autores dieron a la computadora una pista basada en la física del problema. Añadieron un "empujón" especial (llamado término pseudo-contradiabático) al circuito.

  • La Analogía: Imagina que estás intentando empujar una caja pesada cuesta arriba. El "Evolucionista Puro" simplemente empuja aleatoriamente hasta encontrar una forma de subir. La versión "Inspirada en la Física" conoce la forma de la colina y añade una fuerza contraria específica para mantener la caja moviéndose suavemente, evitando que se quede atascada en los puntos planos.
  • El Resultado: Esta estrategia tuvo el mejor rendimiento. Evitó la sensación de "atascarse" (estancamiento de la convergencia) mucho mejor que los otros métodos, incluso cuando el rompecabezas era muy grande.

4. Los Resultados

Los autores probaron estos métodos en un simulador (un programa informático que actúa como una computadora cuántica) utilizando 35 versiones diferentes del rompecabezas de programación de aerolíneas.

• El Ganador: El método de Evolución Inspirada en la Física (APCD-QCE) encontró consistentemente mejores soluciones que el método estándar de "Plano Fijo" (VQE).
• El Punto Crítico: Aunque los nuevos métodos fueron mucho mejores, aún tuvieron dificultades cuando el rompecabezas se volvió extremadamente grande (alrededor de 20 qubits). Incluso el escultor evolutivo a veces se quedaba sin tiempo o complejidad para encontrar la solución perfecta.
• Ruido: También probaron qué sucede cuando la computadora comete errores (simulando el "ruido" del mundo real). Los nuevos métodos se sostuvieron razonablemente bien, aunque el rendimiento disminuyó, lo cual es esperado.

La Conclusión

El artículo afirma que, al permitir que un circuito cuántico cambie su propia forma en lugar de simplemente ajustar sus configuraciones, podemos evitar los "caminos sin salida" que atrapan a los algoritmos actuales. Específicamente, añadir un "empujón" basado en la física a este proceso evolutivo ayuda a la computadora a encontrar mejores soluciones más rápido.

Aunque esto no resuelve todos los problemas aún (especialmente los más grandes), ofrece un nuevo camino prometedor para utilizar computadoras cuánticas en la resolución de problemas complejos de optimización como la programación y la gestión de recursos, potencialmente evitando la necesidad de que las computadoras clásicas realicen el trabajo pesado de la optimización.

Resumen técnico

Resumen Técnico: Marco Evolutivo de Circuitos Cuánticos Aplicado al Problema de Partición de Conjuntos

Definición del Problema
El artículo aborda el Problema de Partición de Conjuntos (SPP), un desafío conocido de optimización combinatoria NP-difícil. El SPP implica dividir un conjunto de elementos en subconjuntos mutuamente excluyentes y exhaustivos para minimizar el peso total, asegurando que cada elemento pertenezca exactamente a un subconjunto. Las aplicaciones prácticas incluyen la programación de tripulaciones de aerolíneas. Para resolver esto en hardware cuántico, los autores formulan el SPP como un problema de Optimización Binaria Cuadrática sin Restricciones (QUBO), que posteriormente se mapea a un Hamiltoniano de Ising. El estudio se dirige específicamente a las limitaciones de los actuales Algoritmos Cuánticos Variacionales (VQA), como el Eigensolver Cuántico Variacional (VQE), que a menudo sufren de "mesetas estériles", un fenómeno donde los gradientes desaparecen exponencialmente a medida que aumenta el número de qubits, lo que lleva a un estancamiento en la convergencia.

Metodología
Los autores proponen un marco Evolutivo de Circuitos Cuánticos (QCE) que se aparta del enfoque estándar de VQE. A diferencia de VQE, que utiliza una topología de circuito fija (ansatz) con parámetros variables optimizados por un optimizador clásico, el marco QCE evoluciona la propia topología del circuito. El estudio evalúa dos estrategias distintas dentro de este marco:

1. Evolución de Circuitos Cuánticos sin Ansatz (AF-QCE):

   • Inspirado en literatura previa [13], este enfoque comienza con un circuito mínimo (una sola puerta aleatoria) y evoluciona iterativamente sin un ansatz predefinido.
   • La evolución se basa en operaciones de mutación: INSERTAR (añadir una puerta), ELIMINAR (quitar una puerta), INTERCAMBIAR (reemplazar una puerta) y MODIFICAR (ajustar los parámetros de la puerta).
   • Se genera una población de circuitos, se miden y se selecciona el circuito de mejor rendimiento como el progenitor para la siguiente generación, asegurando una reducción monótona de la función de costo.

2. Ansatz con Término Evolutivo Pseudo-Contradiabático (APCD-QCE):

   • Este enfoque incorpora una estructura inspirada en la física en el ansatz para mejorar la convergencia. Utiliza un Hamiltoniano $H_T(\lambda) = H_{ad}(\lambda) + H_{pcd}(\lambda)$, donde $H_{ad}$ representa un Hamiltoniano de evolución temporal adiabática y $H_{pcd}$ es un término evolutivo pseudo-contradiabático.
   • El operador unitario se define como $U = U_{ad}U_{pcd}$. El componente $U_{ad}$ es fijo (un paso de Trotter), mientras que $U_{pcd}$ se evoluciona utilizando la misma estrategia de mutación evolutiva que AF-QCE.
   • La preparación del estado inicial utiliza $|+\rangle^{\otimes n}$, y se aplican configuraciones de parámetros específicas ($\beta=0, \delta=0.5$) para facilitar la exploración del espacio de Hilbert.

Configuración Experimental
Los experimentos se realizaron utilizando la biblioteca Qiskit en un simulador de alto rendimiento (KUATOMU) bajo dos escenarios:

• Sin Ruido: Se probaron 35 instancias del SPP (que van de 6 a 20 qubits).
• Con Ruido: Las simulaciones incluyeron canales de error de despolarización ($\epsilon = 0.01$) en qubits específicos para imitar las limitaciones de los dispositivos NISQ.
• Comparación: Las estrategias QCE se compararon con el VQE estándar (utilizando un ansatz de entrelazamiento lineal de dos locales y el optimizador COBYLA).
• Métrica: El rendimiento se midió utilizando la Relación de Aproximación ($R$), definida como la relación entre un valor de referencia clásico (solucionador Gurobi) y el valor de expectativa mínimo encontrado por el algoritmo cuántico.

Resultados Clave

• Superioridad sobre VQE: En escenarios sin ruido, tanto AF-QCE como APCD-QCE superaron significativamente a VQE. El rendimiento de VQE se degradó rápidamente a medida que aumentaba el número de qubits (a menudo fallando en converger para instancias $\ge 10$ qubits), mientras que los enfoques evolutivos mantuvieron un mejor rendimiento.
• Rendimiento de APCD-QCE: La estrategia APCD-QCE demostró los resultados más robustos, logrando una relación de aproximación de 1.00 (óptima) en 25 de las 35 instancias. Evitó eficazmente el estancamiento de la convergencia en la mayoría de los casos donde VQE y AF-QCE tuvieron dificultades.
• Límites de Escalabilidad: A pesar de las mejoras, persistieron desafíos de escalabilidad. Para las instancias de 20 qubits (específicamente 20.1, 20.6 y 20.7), todos los métodos, incluido APCD-QCE, mostraron signos de estancamiento de la convergencia, con una caída significativa en las relaciones de aproximación.
• Impacto del Ruido: En las simulaciones con ruido, el rendimiento se degradó para todos los algoritmos, particularmente en instancias más pequeñas. Sin embargo, los marcos QCE mantuvieron generalmente un rendimiento comparable o mejor en relación con VQE.

Significado y Afirmaciones
El artículo afirma que el marco QCE propuesto ofrece una alternativa prometedora a los algoritmos variacionales de ansatz fijo para problemas de optimización entera. Las contribuciones clave incluyen:

• Mitigación del Estancamiento: El marco, particularmente la variante APCD-QCE, demuestra una capacidad notable para evitar el estancamiento de la convergencia asociado con las mesetas estériles en los VQA estándar.
• Eliminación de Optimizadores Clásicos: Al evolucionar la topología del circuito directamente, el procedimiento evita la necesidad de optimizadores clásicos (como COBYLA) para ajustar parámetros, abordando un cuello de botella en los flujos de trabajo actuales de VQA.
• Camino hacia la Escalabilidad: Aunque no es una solución completa al estancamiento de 20 qubits, los resultados sugieren que los circuitos de topología variable proporcionan un "camino interesante" para resolver problemas de optimización a mayor escala. Los autores señalan que la estrategia APCD-QCE es "casi inmune" a los efectos de estancamiento de la convergencia dado un número suficientemente grande de generaciones, aunque escapar de los mínimos locales en el paisaje de mutación sigue siendo un desafío.

Los autores concluyen que, aunque el método enfrenta obstáculos de escalabilidad con el aumento del número de qubits, la integración de términos inspirados en la física (pseudo-contradiabáticos) en la búsqueda evolutiva de circuitos produce resultados alentadores para resolver problemas combinatorios en dispositivos NISQ.