Un algoritmo heurístico variacional y ahorrador de qubits para MaxCut

Por qué los chips cuánticos diminutos importan para puzzles grandes

Muchas tareas del mundo real —desde el diseño de circuitos hasta la modelización de materiales— se reducen a separar una red en dos grupos cortando tantas conexiones entre ellos como sea posible. Este desafío, conocido como MaxCut, es notoriamente difícil para los ordenadores convencionales. El artículo presenta un nuevo método inspirado en la cuántica que puede manejar redes sorprendentemente grandes usando solo un puñado de bits cuánticos (qubits), ofreciendo una vía novedosa para probar y mejorar herramientas de optimización tanto cuánticas como clásicas.

Dividir una red en dos mitades útiles

MaxCut plantea una pregunta de apariencia simple: si tienes un conjunto de puntos (nodos) conectados por líneas (aristas), ¿cómo deberías colorear cada nodo, por ejemplo azul o blanco, para que el mayor número posible de líneas conecte nodos de distinto color? Esa partición óptima es valiosa en áreas como el diseño de circuitos y la física estadística, pero es muy difícil de encontrar exactamente cuando la red es grande. Un enfoque clásico ampliamente usado, el algoritmo de Goemans–Williamson (GW), realiza una relajación ingeniosa del problema y garantiza encontrar un corte que sea al menos aproximadamente el 88% tan bueno como el óptimo. La computación cuántica promete nuevas formas de abordar estos problemas, pero los dispositivos actuales son ruidosos y de tamaño limitado, lo que dificulta ejecutar circuitos grandes y profundos.

Resolver grafos grandes con solo unos pocos qubits

Los enfoques cuánticos estándar, como el Quantum Approximate Optimization Algorithm (QAOA), requieren un qubit por nodo de la red, por lo que un grafo de 1.000 nodos necesitaría 1.000 qubits, muy por encima de las máquinas actuales. El nuevo método, llamado Qubit-Efficient MaxCut (QEMC), invierte esta escala: usa solo aproximadamente el logaritmo del número de nodos, lo que significa que 11 qubits pueden codificar información sobre más de 2.000 nodos. En lugar de vincular cada qubit a un único nodo, QEMC usa el estado cuántico completo como un espacio de direcciones compacto y permite que distintos nodos correspondan a diferentes estados base de este pequeño registro. Esta economía de qubits mantiene los circuitos poco profundos y más fáciles de ejecutar en hardware ruidoso, al tiempo que sigue representando grafos muy grandes.

Colorear nodos por probabilidad en lugar de estados fijos

La innovación clave es cómo QEMC codifica el “color” de cada nodo. En lugar de forzar que cada nodo sea exactamente azul o blanco en un único estado cuántico, el método permite que el color de cada nodo se infiera a partir de la probabilidad con la que se observa en la medición. Un nodo cuya estado base aparece con baja probabilidad se trata como un color; un nodo con mayor probabilidad se trata como el otro. Un valor umbral separa los dos regímenes. Esto significa que muchos estados cuánticos diferentes corresponden esencialmente a la misma partición del grafo. La función de coste que QEMC minimiza está construida de modo que los nodos conectados sean incentivados a caer en lados opuestos de este umbral de probabilidad, lo que tiende a aumentar el número de aristas que cruzan entre los dos grupos de color y, por tanto, mejora el corte.

Probar el rendimiento en máquinas reales y simuladas

Los autores prueban QEMC en dos frentes: procesadores cuánticos reales y simulaciones clásicas de los circuitos cuánticos. En grafos regulares pequeños de hasta 32 nodos (usando solo de 2 a 5 qubits), QEMC ejecutado en hardware superconductivo de IBM encuentra cortes que igualan o casi igualan las mejores respuestas posibles halladas por búsqueda exhaustiva, superando con claridad el azar y estudios cuánticos anteriores basados en QAOA. En simulaciones sin ruido, QEMC alcanza de forma consistente más del 97% del corte óptimo para estos grafos pequeños. El poder de la codificación resulta aún más patente para grafos mayores: para grafos 9-regulares de hasta 2.048 nodos, las simulaciones clásicas de QEMC siguen superando a GW tanto en cortes medios como en los mejores cortes por unos pocos puntos porcentuales, y se observan ventajas similares en grafos aleatorios de 128 nodos con diferentes densidades.

Velocidad, límites y promesa inspirada en la cuántica

A pesar de su éxito, QEMC no ofrece aún una aceleración cuántica formal. Dado que usa solo aproximadamente log N qubits, la simulación clásica de sus circuitos también escala aproximadamente de forma lineal con el número de nodos, y el tiempo necesario para evaluar la función de coste crece con el número de aristas. Estudios empíricos sugieren que el tiempo total para alcanzar un rendimiento al nivel de GW crece aproximadamente de forma cuadrática con el tamaño del grafo, lo cual sigue siendo alcanzable en la práctica para muchos problemas. Esto significa que QEMC, en su forma actual, funciona más como una heurística poderosa inspirada en la cuántica que como una demostración de ventaja cuántica.

Qué significa este trabajo para el futuro

Para un no especialista, el mensaje principal es que dispositivos cuánticos pequeños y ruidosos pueden seguir siendo científicamente útiles si diseñamos algoritmos que se ajusten a sus fortalezas. Al codificar los colores de los nodos en rangos de probabilidad flexibles en lugar de valores de bits rígidos, QEMC utiliza muy pocos qubits para abordar problemas de redes muy grandes y tolera de forma natural el ruido del hardware. El método establece un nuevo punto de referencia para probar algoritmos de optimización cuántica y también produce un algoritmo clásico práctico basado en las mismas ideas. Más ampliamente, muestra cómo repensar la forma en que se codifica la información —en lugar de limitarse a construir máquinas más grandes— puede abrir vías prometedoras para resolver problemas computacionales difíciles.

Cita: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

Palabras clave: MaxCut, optimización cuántica, algoritmos variacionales, partición de grafos, cálculo inspirado en la cuántica