⚛️ física cuántica

Designing Quantum Solutions to the Closest String Problem with the Non-Variational QWOA

Este artículo presenta una implementación cuántica de extremo a extremo y no variacional del problema de la Cadena más Cercana utilizando el algoritmo NV-QWOA, la cual presenta una nueva prescripción de parámetros que evita la optimización específica de cada instancia mientras amplifica consistentemente las soluciones óptimas con requisitos de recursos estimados analíticamente.

Autores originales: Benjamin Rossdeutscher, Jingbo Wang

Publicado 2026-10-27

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Benjamin Rossdeutscher, Jingbo Wang

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

En el vasto panorama de la informática moderna, existe una clase de acertijos tan complejos que incluso las supercomputadoras más potentes luchan por resolverlos con exactitud. Estos son los problemas de optimización combinatoria, donde el objetivo es encontrar la mejor disposición única entre un número asombroso de posibilidades. Imagine intentar encontrar la llave perfecta en una habitación llena de miles de millones de cerraduras; a medida que el número de cerraduras crece, el tiempo requerido para comprobar cada una de ellas crece tan rápido que rápidamente se vuelve imposible. Uno de estos acertijos es el problema de la "Cadena más Cercana" (Closest String). Este plantea una pregunta sencilla: dadas una colección de diferentes cadenas de caracteres, ¿es posible encontrar una nueva cadena que sea lo más similar posible a todas ellas a la vez? Esto no es solo un juego teórico. Los científicos utilizan esta lógica para reconstruir mensajes dañados en las comunicaciones, identificar estructuras comunes en moléculas de proteínas para el descubrimiento de fármacos y rastrear virus mutados durante brotes de enfermedades. Debido a que el número de posibles respuestas explota a medida que el problema se agranda, encontrar la verdadera mejor respuesta se considera una de las tareas más difíciles en la informática.

Recientemente, investigadores de la Universidad de Australia Occidental han dado un paso significativo hacia la resolución de este problema utilizando el poder único de las computadoras cuánticas. En lugar de comprobar las respuestas una por una como lo hace una computadora clásica, su nuevo método utiliza las extrañas reglas de la mecánica cuántica para explorar muchas posibilidades a la vez. Aplicaron una técnica específica llamada Algoritmo de Optimización de Caminata Cuántica No Variacional, o NV-QWOA, al problema de la Cadena más Cercana. Este enfoque es distinto porque no depende de un proceso lento de prueba y error para ajustar sus configuraciones. En su lugar, los investigadores diseñaron un conjunto fijo de instrucciones que guían automáticamente a la computadora cuántica hacia la mejor solución. Al simular este proceso en una computadora clásica, demostraron que su método puede aumentar con éxito la probabilidad de encontrar la respuesta correcta, convirtiendo una búsqueda casi imposible en una manejable para problemas de pequeño a mediano tamaño.

El núcleo de su trabajo consiste en la construcción de un plano digital, o circuito, que una computadora cuántica pueda seguir. Este circuito actúa como una fábrica para el procesamiento de información. Primero, crea una superposición, un estado en el que la computadora contiene todas las posibles respuestas simultáneamente. Luego, comienza un riguroso proceso de evaluación. El sistema compara esta nube de posibles respuestas contra la colección original de cadenas de referencia. Calcula la "distancia" entre cada posible respuesta y las referencias, midiendo cuántos caracteres tendrían que cambiarse para que coincidan. El objetivo es encontrar la respuesta que requiera el menor número de cambios en general. Los investigadores tuvieron que diseñar una forma ingeniosa de realizar este cálculo dentro del reino cuántico, utilizando puertas especiales para contar las diferencias y determinar la distancia máxima sin perder la delicada información cuántica.

Un obstáculo importante en estos tipos de algoritmos cuánticos es decidir cómo ajustar los ajustes internos para obtener el mejor resultado. Muchos métodos existentes requieren que una computadora clásica ajuste constantemente estos parámetros basándose en los resultados de ejecuciones previas, un proceso que puede ser lento e ineficiente. Los investigadores en este estudio introdujeron una nueva regla fija para uno de estos ajustes críticos. Descubrieron que, al establecer este valor basándose simplemente en el tamaño del problema, podían evitar la necesidad de cualquier ajuste de prueba y error. Este cambio evitó un error común donde las fases cuánticas, que guían la búsqueda, se envolverían y se cancelarían entre sí. Al mantener estas fases distintas y debidamente escaladas, el algoritmo podía empujar de manera más efectiva la probabilidad de encontrar la respuesta correcta hacia arriba.

Para probar su idea, el equipo ejecutó simulaciones en una computadora clásica que imitaba el comportamiento de una máquina cuántica. Crearon docenas de diferentes escenarios de problemas, que iban desde cadenas simples de tres caracteres hasta otras más complejas con seis caracteres. En cada caso, comenzaron con un estado donde todas las posibles respuestas eran igualmente probables. A medida que el algoritmo avanzaba en sus pasos, comenzaba a favorecer las mejores soluciones. Después de treinta rondas de procesamiento, las simulaciones mostraron que la probabilidad de medir la respuesta perfecta aumentó a más del ochenta por ciento. En muchos casos, la probabilidad de encontrar la mejor respuesta fue incluso mayor, alcanzando el noventa por ciento. El sistema consistentemente impulsó las soluciones correctas hacia la cima mientras suprimía las incorrectas, demostrando que el método funciona según lo previsto para los tamaños que probaron.

Los investigadores también contaron cuidadosamente los recursos que su método requeriría si se ejecutara en hardware cuántico real. Descubrieron que el número de bits cuánticos, o qubits, necesarios crece de una manera manejable a medida que el problema se agranda. Específicamente, el número de qubits escala linealmente con el número de cadenas de referencia y la longitud de las cadenas, pero solo logarítmicamente con el tamaño del conjunto de caracteres utilizado. Esto significa que, incluso cuando el problema se vuelve más complejo, los requisitos de hardware no explotan de forma incontrolada. La profundidad del circuito, que representa el tiempo que toma ejecutar el cálculo, también sigue un patrón predecible. Estos hallazgos proporcionan un mapa claro para futuros experimentos, mostrando exactamente qué tipo de máquina se necesitaría para abordar estos problemas en el mundo real.

Aunque los resultados actuales se basan en simulaciones, las implicaciones para el futuro son claras. El estudio confirma que el problema de la Cadena más Cercana, que es notoriamente difícil para las computadoras clásicas, puede abordarse eficazmente con métodos cuánticos. El trabajo del equipo proporciona una guía completa, paso a paso, sobre cómo construir los circuitos cuánticos necesarios y cómo configurar sus parámetros sin necesidad de una intervención humana constante. Aunque las simulaciones se limitaron a tamaños de problemas pequeños, el éxito del algoritmo en estas pruebas sugiere que podría escalar para manejar los complejos conjuntos de datos que se encuentran en la genética y las comunicaciones. Los investigadores señalan que su método podría extenderse potencialmente para resolver problemas relacionados, como encontrar subcadenas comunes dentro de secuencias más largas, abriendo la puerta a aplicaciones más amplias en la ciencia y la tecnología.

Esta investigación representa un movimiento concreto de la teoría a la práctica en el campo de la optimización cuántica. Al demostrar un diseño de circuito funcional y un método fiable para establecer sus parámetros, los autores han proporcionado una base para futuros experimentos de hardware. Su trabajo muestra que, con el enfoque adecuado, las computadoras cuánticas pueden navegar por los vastos espacios de búsqueda de los problemas combinatorios, concentrando su poder en las respuestas más prometedoras. A medida que el hardware cuántico continúe mejorando, las técnicas desarrolladas en este estudio probablemente servirán como un plano para resolver algunos de los acertijos de optimización más desafiantes que actualmente limitan nuestra capacidad para analizar sistemas biológicos y digitales complejos.

Resumen Técnico: Soluciones Cuánticas al Problema de la Cadena más Cercana mediante NV-QWOA

1. Definición del Problema

El Problema de la Cadena más Cercana (CSP, por sus siglas en inglés) es un problema de optimización combinatoria clasificado como NP-Duro. Dada un conjunto de $m$ cadenas de referencia, cada una de longitud $n$ sobre un alfabeto de tamaño $k$ , el objetivo es encontrar una cadena solución $s$ de longitud $n$ que minimice la distancia de Hamming máxima respecto a cualquier cadena del conjunto de referencia. La función de costo se define como:
$f(s) = \max_{i=1,2,...,m} d_H(s, s_i)$
donde $d_H$ es la distancia de Hamming.

Clásicamente, resolver este problema de forma exacta es computacionalmente prohibitivo para $n$ grandes. Una búsqueda exhaustiva escala como $O(k^n)$ , y calcular la matriz de costos para un solo candidato requiere $O(mn)$ comparaciones, lo que conduce a una complejidad clásica total de $O(k^n mn)$ . Aunque existen algoritmos clásicos parametrizados, estos siguen exhibiendo un escalamiento exponencial con respecto a la distancia de Hamming máxima $d$ . El CSP tiene aplicaciones significativas en bioinformática (por ejemplo, identificar estructuras comunes en moléculas proteicas o cepas virales mutadas), reconstrucción de señales en comunicaciones y corrección de códigos.

2. Metodología: NV-QWOA (No Variacional)

Los autores proponen una implementación cuántica de extremo a extremo del CSP utilizando el Algoritmo de Optimización de Caminata Cuántica No Variacional (NV-QWOA). A diferencia de los Algoritmos Cuánticos Variacionales (VQA) como el QAOA, que dependen de bucles de optimización clásicos para ajustar parámetros, el NV-QWOA utiliza un conjunto fijo de hiperparámetros determinados por la estructura del problema, evitando los problemas de mesetas áridas (barren plateaus) y la sobrecarga clásica asociados con los métodos variacionales.

Pasos del Algoritmo

El algoritmo opera sobre un circuito cuántico a través de $p$ iteraciones, cada una de las cuales consta de tres componentes principales:

Evaluación de Costo (Separación de Fase):
- El algoritmo calcula la distancia de Hamming entre una superposición de cadenas de solución candidatas y todas las $m$ cadenas de referencia.
- Determina la distancia de Hamming máxima para cada candidato (el costo) utilizando una arquitectura de circuito cuántico determinista que involucra la Suma de Fourier Cuántica (QFA) y un comparador de estado cuántico.
- Se aplica un desplazamiento de fase proporcional al costo al registro de la solución. Los autores introducen una prescripción revisada para el parámetro de separación de fase $\gamma$ , definido determinísticamente como $\gamma = \frac{\pi}{2(n+1)}$ . Esto evita la necesidad de optimización específica para cada instancia y mitiga el empaquetamiento de fase módulo $2\pi$ que puede debilitar la correlación entre el costo y la fase.
Mezcla (Caminata Cuántica):
- Se realiza una Caminata Cuántica de Tiempo Continuo (CTQW) sobre un grafo de mezcla. Para el CSP, este grafo es un grafo de Hamming, donde los nodos representan cadenas de solución y las aristas conectan cadenas que difieren en una distancia de Hamming de 1.
- Esta unidad de mezcla redistribuye la amplitud entre estados vecinos, amplificando aquellos con fases favorables (bajas).
Iteración:
- Los pasos 1 y 2 se repiten $p$ veces. El algoritmo amplifica la probabilidad de medir soluciones óptimas o casi óptimas mientras suprime los estados no óptimos.

Detalles de Implementación del Circuito

Codificación a Nivel de Puerta: La implementación utiliza Qiskit para traducir el problema en puertas de uno y dos qubits.
Registros: El circuito utiliza siete registros cuánticos: un registro de solución, un registro de referencia, un registro de caracteres (para $k>2$ ), un registro QFT, un registro de ganador, un registro de ranura de ganador y un registro de objetivo de fase.
Descomputación: Los registros auxiliares (ancillas) utilizados para el cálculo del costo se descomputan (desentrelazan) mediante operaciones de conjugado hermítico para evitar la interferencia con el paso de mezcla.
Optimización: Los autores optimizaron el cálculo de la distancia de Hamming integrando una implementación eficiente de la puerta OR con QFA, reduciendo la necesidad de qubits adicionales.

3. Contribuciones Clave

Implementación Explícita a Nivel de Puerta: El artículo proporciona un flujo de trabajo completo y automatizado para convertir instancias arbitrarias de CSP en circuitos cuánticos, incluyendo la codificación de las cadenas de referencia, la evaluación de costos y el ansatz de NV-QWOA.
Escalamiento de Fase Determinista: Se introduce una nueva prescripción de $\gamma$ dependiente del tamaño del problema. Esto elimina la necesidad de estimación heurística u optimización clásica de $\gamma$ , asegurando que el algoritmo sea verdaderamente no variacional.
Análisis de Complejidad de Recursos:
- Complejidad de Qubits: $O(nm \log k)$ .
- Profundidad del Circuito: $O(pm \log^2 n + pn \log n)$ para tamaños de alfabeto fijos.
- Estas estimaciones representan una trayectoria de escalamiento favorable en comparación con el espacio de búsqueda clásico exponencial.
Circuito Eficiente de Función Máximo: Los autores diseñaron arquitecturas de circuito específicas (usando puertas CCNOT y CSwap) para encontrar determinísticamente la distancia de Hamming máxima a través del conjunto de referencia, una tarea no trivial en circuitos cuánticos debido a la naturaleza no cuadrática de la función máximo.

4. Resultados

Los autores validaron el enfoque utilizando simulaciones de estado vectorial clásicas mediante Qiskit-Aer.

Parámetros de Simulación: Los experimentos se realizaron para longitudes de cadena $n \in \{3, 4, 5, 6\}$ , con $m=2$ cadenas de referencia y un alfabeto binario ( $k=2$ ). Esto corresponde a circuitos de entre 15 y 26 qubits.
Rendimiento:
- Tras $p=30$ iteraciones, el algoritmo amplificó consistentemente el conjunto de soluciones óptimas (subcapa 0).
- La probabilidad de medir una solución óptima alcanzó el 80–90% en todas las instancias probadas.
- La subcapa 1 (soluciones casi óptimas) retuvo un 10–20% de probabilidad, mientras que todas las demás subcapas convergieron a una probabilidad cercana a cero.
- La prescripción determinista de $\gamma$ resultó efectiva sin requerir el escalamiento de la desviación estándar del costo, lo cual se consideró ligeramente perjudicial en escalas menores.
Observación: Los resultados demuestran que el NV-QWOA puede concentrar eficazmente la probabilidad de medición en candidatos de alta calidad partiendo de una superposición uniforme, incluso sin ajuste de parámetros clásicos.

5. Significado y Reivindicaciones

El artículo afirma proporcionar un marco fundamental para resolver el Problema de la Cadena más Cercana en hardware cuántico. Su importancia radica en:

Demostración de Aplicabilidad: Verifica que el NV-QWOA, previamente probado en problemas como MaxCut y k-means, es aplicable al CSP (NP-Duro).
Preparación para el Hardware: Al proporcionar una implementación explícita a nivel de puerta y estimaciones de recursos, el trabajo sienta las bases para futuros experimentos en computadoras cuánticas tolerantes a fallos.
Potencial de Benchmarking: Los autores posicionan este trabajo como una base para comparar algoritmos cuánticos frente a solucionadores clásicos. Establecen explícitamente que alcanzar una "aceleración cuántica de extremo a extremo" completa requiere un análisis adicional de la escala de iteraciones ( $p$ ), las repeticiones de medición y las sobrecargas clásicas, aspectos que no se resuelven totalmente en este estudio.
Extensiones Futuras: Los autores señalan que el marco podría extenderse potencialmente al Problema de la Subcadena más Cercana (donde la solución es una subcadena de longitud $n$ dentro de cadenas de referencia más largas de longitud $L$ ), aunque esto no fue investigado en el presente trabajo.

El artículo mantiene un tono modesto, reconociendo que, si bien el algoritmo muestra una fuerte amplificación en la simulación, la transición hacia una ventaja cuántica práctica requiere una mayor investigación sobre las leyes de escalamiento y las restricciones del hardware.