Resumen Técnico: MOSAIQC

Planteamiento del Problema

Los computadores cuánticos actuales, particularmente aquellos en la era de la Escala Intermedia con Ruido (NISQ), carecen de los recursos de cúbits y la fidelidad requeridos para ejecutar la mayoría de los algoritmos cuánticos prácticos. Para sortear estas limitaciones de hardware, el "corte de circuitos cuánticos" (o circuit knitting) ha surgido como una técnica para dividir algoritmos grandes en particiones más pequeñas ejecutables en el hardware disponible. Sin embargo, este enfoque introduce una sobrecarga de muestreo (sampling overhead) significativa que escala exponencialmente con el número de cortes requeridos para la reconstrucción exacta del estado.

Los marcos de optimización existentes para determinar la ubicación de los cortes enfrentan varias limitaciones críticas:

1. Escalabilidad: Los métodos exactos (por ejemplo, Programación Entera Mixta, resolvedores SMT) a menudo exhiben una complejidad computacional factorial o exponencial, lo que los hace inviables para circuitos que se aproximan al régimen de los mil cúbits.
2. Limitaciones del Tipo de Corte: Muchas heurísticas optimizan para cortes de cables (wire cuts) o cortes de puertas (gate cuts) de forma aislada, rara vez combinando ambos dentro de un único procedimiento de optimización.
3. Conciencia del Hardware: La mayoría de los enfoques asumen particiones de hardware homogéneas y descuidan las características de ruido específicas y las restricciones de conectividad de los backends cuánticos heterogéneos, lo que conduce a una fidelidad de ejecución subóptima.
4. Compromisos (Trade-offs): Equilibrar la minimización de la sobrecarga de muestreo con la maximización de la fidelidad del hardware (reducción de ruido) es un problema multiobjetivo complejo que las heurísticas escalables existentes a menudo no logran abordar de manera conjunta.

Metodología

El artículo presenta MosasiQC, un marco de optimización heurística diseñado para optimizar conjuntamente la sobrecarga de muestreo, la colocación consciente del hardware y los cortes mixtos de puertas/cables, manteniendo una complejidad de tiempo polinómica. El marco opera a través de un flujo de optimización jerárquico de cuatro etapas:

1. Representación de Grafos

Para reducir la sobrecarga computacional, el circuito cuántico y la topología del hardware se transforman en representaciones de grafos compactas en lugar de depender de evaluaciones repetidas de Grafos Acíclicos Dirigidos (DAG).

• Grafo de Conectividad: Representa los cúbits como nodos y las puertas de 2 cúbits como aristas, ponderadas por el conteo de puertas.
• Dependencias Temporales: Se almacenan por separado para evaluar eficientamente los cortes de cables cuando las particiones comparten cúbits.
• Topología de Hardware: Modelada como un grafo ponderado donde los pesos de las aristas incorporan métricas de ruido (por ejemplo, errores de puerta $1-q$ y $2-q$) y costos de enrutamiento (estimados mediante caminos cortos de Floyd-Warshall).

2. Particionamiento Inicial (Arranque en Caliente / Warm-Start)

El marco utiliza la biblioteca METIS para realizar un particionamiento de grafos global. Este paso genera una solución inicial que satisface las restricciones de capacidad del hardware, proporcionando un punto de partida de alta calidad para el refinamiento posterior. Esta etapa aborda principalmente los cortes de puertas o los cortes de cables de forma individual para establecer una línea base.

3. Refinamiento Local

Un algoritmo de Búsqueda Tabú (Tabu Search) refina iterativamente la partición inicial mediante movimientos locales:

• Añadir nodos a las particiones (sujeto a capacidad).
• Mover nodos entre particiones.
• Intercambiar (swap) nodos en los límites de las particiones.
• Evaluación de Cortes Mixtos: La función de costo contabiliza explícitamente tanto los cortes de puertas como los de cables. La sobrecarga se calcula como $Overhead = (GateCost)^g \cdot 16^w$, donde $g$ y $w$ son los conteos de cortes de puertas y cables, respectivamente. Para optimizar la computación, se utiliza el logaritmo de este costo durante la búsqueda.
• Estrategia de Evaluación Local: En lugar de reevaluar el grafo global, el marco utiliza una estrategia de búsqueda de cortes de cables local basada en representaciones de grafos a nivel de cúbit, reduciendo significativamente la complejidad a $O((a+1)p \log p)$ para particiones superpuestas.

4. Asignación de Partición Consciente del Hardware

Para optimizar la fidelidad de ejecución, MosaiQC emplea un resolvedor de Problemas de Asignación Cuadrática (QAP) utilizando el algoritmo de Frank-Wolfe.

• Objetivo: Encontrar una matriz de permutación que mapee las particiones del circuito a los backends de hardware para maximizar la fidelidad esperada (minimizar el ruido).
• Puntuación: El algoritmo minimiza la traza del producto de la matriz de la partición del circuito y la matriz de topología de ruido del hardware. Los pesos de ruido se transforman logarítmicamente ($w = \ln(1 - \epsilon_{noise})$) para manejar diferentes escalas de manera efectiva.
• Función de Costo Adaptativa: Para equilibrar el costo computacional de las evaluaciones de QAP con la calidad de la optimización, el marco utiliza una función de costo adaptativa ($S_{adapt}$) que normaliza la sobrecarga de corte frente a la puntuación de colocación de QAP. Las evaluaciones de QAP se realizan en intervalos establecidos en lugar de en cada iteración.

Contribuciones Clave

El artículo reclama las siguientes contribuciones específicas:

1. Marco de Optimización Conjunta: Un marco heurístico que optimiza los cortes mixtos de cables y puertas dentro de un solo procedimiento, una capacidad raramente demostrada en las herramientas escalables existentes.
2. Evaluación de Corte de Cables Local: Una estrategia basada en representaciones de grafos a nivel de cúbit que reduce la complejidad computacional de la optimización repetida basada en DAG.
3. Soporte para Hardware Heterogéneo: Una capa de abstracción que soporta backends cuánticos con capacidades de cúbits y características de ruido variables, permitiendo particiones de hardware de tamaño mixto.
4. Colocación Consciente del Hardware: Un método que utiliza el emparejamiento de grafos doblemente ponderado (resuelto mediante Frank-Wolfe) para colocar las particiones en el hardware, optimizando explícitamente para la reducción de ruido.
5. Estrategia Híbrida Escalable: Una combinación de particionamiento global con METIS para el arranque en caliente y refinamiento mediante Búsqueda Tabú, logrando una complejidad de tiempo polinómica $O(k \cdot n_q + m \cdot n_q^3)$.

Resultados

El marco fue evaluado contra el complemento de corte de circuitos de Qiskit (usando el algoritmo de Dijkstra) y métodos de búsqueda exhaustiva a través de varios bancos de pruebas (ej. Adder, BV, AQFT, QAOA, VQE) y tamaños de circuito (de 6 a 1000 cúbits).

• Rendimiento de Tiempo de Ejecución: MosaiQC logró una aceleración de la media geométrica de 2.88× en el tiempo de ejecución en comparación con la línea base. Crucialmente, optimizó con éxito circuitos de hasta 1000 cúbits, mientras que la línea base frecuentemente sufría de tiempos de espera agotados (timeouts) o desbordamientos de memoria.
• Sobrecarga de Muestreo: El marco demostró una reducción promedio del 16.84% en el número de cortes en comparación con la línea base. Esto resultó en una mejora de la media geométrica en la sobrecarga de muestreo de aproximadamente $5.38 \cdot 10^{11}\times$ (debido a la naturaleza exponencial de la sobrecarga).
• Mejora de la Fidelidad: La estrategia de colocación consciente del hardware mostró una fuerte correlación de Pearson ($r \approx 0.83 - 0.87$) entre la puntuación de QAP y la fidelidad medida. En las pruebas de fidelidad, MosaiQC logró una mejora de la fidelidad local media de +19.56% ± 6.17% sobre la línea base cuando se priorizó el peso del ruido.
• Convergencia: El enfoque híbrido de arranque en caliente redujo significamente el número de iteraciones requeridas para la convergencia en comparación con los enfoques de solo refinamiento, evitando que el optimizador quedara atrapado en mínimos locales temprano en su búsqueda.

Significado y Reclamaciones

Los autores posicionan a MosaiQC como una evolución necesaria en las herramientas de compilación cuántica. Afirman que, a medida que los circuitos cuánticos escalan hacia el régimen de los mil cúbits, la optimización de la ubicación de los cortes en sí misma no debe convertirse en un cuello de botella computacional.

El artículo sostiene que MosaiQC demuestra un compromiso superior entre la velocidad de ejecución y la calidad de la solución, añadiendo características fundamentales (cortes mixtos, soporte de hardware heterogéneo y colocación consciente del ruido) que están excluidas por la mayoría de sus competidores. Aunque reconocen que el corte de circuitos práctico sigue estando fundamentalmente limitado por la sobrecarga de muestreo exponencial requerida para la reconstrucción, los autores argumentan que MosaiQC establece una base práctica para el corte de circuitos escalable en futuros sistemas de computación cuántica heterogéneos. El trabajo sugiere que la optimización heurística escalable puede reducir sustancialmente la sobrecarga computacional de la colocación de cortes de circuitos, permitiendo la ejecución de algoritmos que de otro modo serían inviables en el hardware actual.