⚛️ quantum physics

A competitive NISQ and qubit-efficient solver for the LABS problem

Este artículo demuestra que el marco de codificación de correlación de Pauli (PCE), un enfoque variacional eficiente en cúbits, resuelve eficazmente el problema de las secuencias binarias de baja autocorrelación (LABS) con un escalado y una resiliencia al ruido mejorados, superando a las heurísticas clásicas de vanguardia mientras requiere significativamente menos recursos cuánticos.

Autores originales: Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

Publicado 2026-01-27

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Marco Sciorilli, Giancarlo Camilo, Thiago O. Maciel, Askery Canabarro, Lucas Borges, Leandro Aolita

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando organizar una larga fila de personas, donde cada una sostiene una bandera roja (+1) o una bandera azul (-1). Tu objetivo es organizar las banderas de modo que, si miras la línea desde diferentes ángulos, los patrones de banderas rojas y azules no se alineen accidentalmente de una forma confusa. En el mundo científico, esto se llama el problema de las Secuencias Binarias de Baja Autocorrelación (LABS), un rompecabezas notoriamente difícil utilizado para poner a prueba qué tan buenos son los ordenadores para resolver problemas de optimización complejos.

Este artículo presenta una nueva y astuta forma para que las computadoras cuánticas (específicamente las actuales, ruidosas, conocidas como NISQ) resuelvan este rompecabezas mejor que muchos métodos tradicionales. Aquí está el desglose de su enfoque:

1. El Problema: Un "Campo de Golf" de Errores

Imagina que la búsqueda de la disposición perfecta de las banderas es como intentar encontrar el punto más bajo en un vasto paisaje neblinoso.

El Paisaje: La mayor parte del tiempo, estás caminando sobre una llanura con muchos pequeños hundimientos (mínimos locales). Estos parecen ser el fondo de un valle, pero no son el fondo real.
El Objetivo: La verdadera solución es un único agujero, diminuto y profundo, en medio de la llanura (el mínimo global).
La Dificultad: Debido a que hay tantos "fondos" falsos, los programas informáticos estándar a menudo se quedan atrapados en uno de ellos y se rinden, pensando que han encontrado la mejor respuesta cuando no es así.

2. La Solución: Un Mapa "Comprimido" (Codificación de Correlación de Pauli)

Normalmente, para resolver un problema con $N$ variables (como 45 banderas), una computadora cuántica necesita 45 bits cuánticos (qubits). Pero las computadoras cuánticas actuales son pequeñas y frágiles; no pueden manejar esa cantidad de bits todavía.

Los autores utilizan un truco llamado Codificación de Correlación de Pauli (PCE).

La Analogía: Imagina que tienes una enorme biblioteca de libros (las 45 banderas), pero solo tienes un pequeño cuaderno (4 qubits). En lugar de escribir cada uno de los libros, usas un código especial. Escribes las relaciones entre los libros.
Cómo funciona: Mapean las 45 banderas en solo 4 qubits. Es como comprimir una película de alta definición en un archivo muy pequeño sin perder la trama. Esto les permite abordar problemas enormes (hasta 45 banderas en su simulación, e incluso 120 en un experimento real) utilizando muy pocos recursos cuánticos.

3. La Estrategia: Elegir las "Preguntas" Adecuadas

Para obtener la mayor cantidad de información de esos 4 qubits, el equipo tuvo que decidir cómo hacerle preguntas a la computadora cuántica.

El Conjunto Conmutativo: Hacer preguntas que no interfieren entre sí (como preguntar por el clima y la hora del día).
El Conjunto No Conmutativo: Hacer preguntas que sí interfieren entre sí (como intentar medir la posición y la velocidad de una moneda giratoria al mismo tiempo).
El Resultado: Descubrieron que las preguntas "interferentes" (no conmutativas) eran mucho mejores. Es como agitar un frasco de canicas para ver la imagen completa en lugar de mirar solo un lado. Este método les dio los mejores resultados.

4. El Rendimiento: Más Rápido y Más Inteligente

Probaron su nuevo método contra los mejores programas de computadora clásicos (regulares) y otros métodos cuánticos.

La Carrera: Midieron el "Tiempo hacia la Solución" (cuánto tiempo toma encontrar la respuesta perfecta).
El Resultado: Su método cuántico fue más rápido que los mejores programas clásicos de "heurística" (un algoritmo de adivinación inteligente llamado Búsqueda Tabú) para los tamaños que probaron.
La Escala: Mientras que otros métodos cuánticos necesitaban computadoras masivas y perfectas que aún no existen, este método funciona en dispositivos pequeños y actuales. Escala mejor, lo que significa que, a medida que el problema se hace más grande, su método sigue siendo competitivo durante más tiempo que los demás.

5. La Prueba del Mundo Real: El Patio de Juegos "Ruidoso"

Los autores no solo realizaron simulaciones; realmente ejecutaron su algoritmo en una computadora cuántica real fabricada por IonQ (llamada el procesador Forte).

El Desafío: Las computadoras cuánticas reales son "ruidosas". Es como intentar escuchar un susurro en medio de un huracán. El hardware comete errores.
El Resultado: Resolvieron con éxito un problema de 120 banderas (el mayor jamás mostrado en hardware cuántico para este problema específico).
Resiliencia: Incluso con el "huracán" de ruido, la respuesta final fue buena. Descubrieron que no necesitaban millones de intentos (shots) para obtener una respuesta decente; unos pocos miles fueron suficientes. Sin embargo, el ruido hizo que la respuesta final fuera ligeramente menos perfecta de lo que sería en una simulación perfecta.

Resumen

El artículo afirma que, mediante el uso de una ingeniosa técnica de "compresión" (PCE) y haciendo el tipo de preguntas adecuadas (operadores no conmutativos), pueden resolver un rompecabezas matemático muy difícil (LABS) en computadoras cuánticas pequeñas e imperfectas. Su método es más rápido que los mejores métodos de adivinación clásicos actuales para los tamaños probados y es lo suficientemente robusto como para funcionar en hardware real y ruidoso hoy mismo. Sugieren que esto podría ser una herramienta poderosa para resolver problemas difíciles ahora, incluso antes de que tengamos computadoras cuánticas perfectas y libres de errores.

Resumen Técnico: Un Solucionador Competitivo para el Problema LABS con Eficiencia de Qubits y para la Era NISQ

Definición del Problema
El problema de las Secuencias Binarias de Baja Autocorrelación (LABS, por sus siglas en inglés) es un desafío de optimización combinatoria bien conocido, de clase NP-duro, con aplicaciones en ingeniería, comunicaciones y física estadística. Dado un entero $N$ , el objetivo es encontrar una secuencia binaria $x \in \{-1, +1\}^N$ que minimice la energía de los lóbulos laterales $E(x)$ , definida como la suma de las autocorrelaciones al cuadrado $C_\ell(x)$ para $\ell > 0$ . Equivalentemente, el objetivo es maximizar el factor de mérito $F(x) = N^2 / 2E(x)$ . El problema se caracteriza por un paisaje de optimización de tipo "campo de golf" con numerosos mínimos locales y mínimos globales aislados. Aunque existen soluciones exactas para $N \le 66$ , encontrar soluciones óptimas o de alta calidad para $N$ más grandes se vuelve intratable para los métodos clásicos de fuerza bruta, e incluso los heurísticos de vanguardia como el Búsqueda Tabú Memética enfrentan desafíos significantes de escalabilidad.

Metodología: Codificación de Correlación de Pauli (PCE)
Los autores proponen un solucionador cuántico variacional eficiente en qubits basado en el marco de trabajo de Codificación de Correlación de Pauli (PCE). A diferencia de las codificaciones estándar que requieren un qubit por cada variable binaria, PCE comprime $N$ variables binarias en $n$ qubits donde $N = \text{poly}(n)$ , específicamente $n \ll N$ .

Codificación: Las variables binarias $x_i$ se codifican como los signos de los valores esperados de un conjunto de cadenas de Pauli de $n$ qubits $\Pi = \{\Pi_i\}_{i \in [N]}$ :
$x_i := \text{sgn}(\langle \Pi_i \rangle)$
donde $\langle \Pi_i \rangle = \langle \Psi | \Pi_i | \Psi \rangle$ .
Optimización: El estado cuántico $|\Psi\rangle$ es generado por un circuito de ladrillos (brickwork) parametrizado. Los parámetros se optimizan clásicamente para minimizar una función de pérdida no lineal $L$ . Para facilitar la optimización basada en gradientes, las variables binarias se relajan utilizando una función tangente hiperbólica: $\tilde{x}_i = \tanh(\alpha \langle \Pi_i \rangle)$ . La función de pérdida incluye un término de regularización para evitar que los correladores se desvanezcan.
Selección del Conjunto de Pauli: El estudio evalúa dos conjuntos distintos para $\Pi$ $Π$ :
1. $\Pi(C)$ : Un conjunto de operadores de Pauli seleccionados aleatoriamente y mutuamente conmutantes.
2. $\Pi(NC)$ : Un conjunto diseñado para maximizar el número de operadores de Pauli mutuamente no conmutantes. Los autores hipotetizan que la no conmutatividad conduce a mediciones mutuamente sesgadas, aumentando así la expresividad e independencia de las variables codificadas.

Contribuciones Clave y Resultados

Simulaciones Numéricas ( $N \le 45$ ):
- Los autores simularon el solucionador PCE utilizando $n=4$ qubits y una profundidad de circuito de 15 capas (30 puertas de dos qubits, 150 parámetros).
- La variante $\Pi(NC)$ superó consistentemente a la variante conmutante.
- Análisis de Escalamiento: El Tiempo para la Solución (TTS), definido como el número de evaluaciones de la función de costo requeridas para encontrar la solución exacta, se comparó con QAOA y la Búsqueda Tabú Memética.
  - Escalamiento de PCE: $O(1.330^N)$ para instancias pares y $O(1.326^N)$ para instancias impares.
  - Comparación: Este escalamiento mejora el escalamiento de QAOA de $O(1.46^N)$ y es marginalmente mejor que el escalamiento de la Búsqueda Tabú de vanguardia de $O(1.34^N)$ (para instancias pares) y $O(1.409^N)$ (para instancias impares).
- Los resultados indican una ventaja de ley de potencia de PCE sobre las líneas base clásicas dentro del rango probado.
Demostración Experimental (IonQ Forte):
- Los autores realizaron una demostración de prueba de concepto en el procesador cuántico IonQ Forte para un tamaño de instancia de $N=120$ , el más grande demostrado hasta la fecha en hardware cuántico.
- Para el experimento, se utilizó un conjunto específico de correladores de $k$ -cuerpos ( $k=2$ ) amigable para el hardware, lo que requirió solo tres configuraciones de medición.
- Resiliencia al Ruido: El estudio encontró que, si bien el ruido de disparo (shot noise) tuvo un impacto menor (requiriendo solo unos pocos miles de disparos), el ruido del hardware degradó significativamente la calidad de la solución final. Sin embargo, el proceso de entrenamiento en sí mismo se mantuvo robusto, lo que sugiere que la mitigación de errores o tasas de compresión más altas son críticas para el despliegue en la era cercana.

Significancia y Reivindicaciones
El artículo sostiene que los solucionadores basados en PCE representan un enfoque prometedor para dos vías distintas:

Heurísticos Clásicos de Inspiración Cuántica: Incluso cuando se simulan clásicamente, el marco de PCE ofrece un escalamiento competitivo o superior frente a los principales heurísticos clásicos para problemas difíciles como LABS, actuando como un poderoso algoritmo de inspiración cuántica.
Reducción de Recursos NISQ: Al codificar $N$ variables en un número de qubits polinómicamente menor ( $n$ ), PCE reduce drásticamente los requisitos de qubits para los dispositivos de corto plazo. Los autores señalan que $n=8$ qubits podría teóricamente abordar instancias de hasta $N=66$ (donde se conocen las soluciones exactas), y $n \le 20$ podría desafiar las instancias más grandes resolubles mediante heurísticos clásicos.

Los autores mantienen una postura modesta respecto a la "ventaja cuántica". Reconocen que la sobrecarga de simular vectores de estado cuánticos completos en comparaciones clásicas retrasa el punto de cruce donde una verdadera ventaja de tiempo de ejecución cuántica se hace evidente. Además, señalan que aunque el método muestra un fuerte desempeño, actualmente carece de garantías de rendimiento. No obstante, la capacidad de resolver instancias de $N=120$ en el hardware actual con presupuestos de disparos modestos y la observación de la resiliencia al ruido resaltan el potencial de PCE como una herramienta para reducir los requisitos de recursos en algoritmos cuánticos reales.