⚛️ quantum physics

Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games

Este artículo introduce y revisa las formulaciones QUDO, T-QUDO y HOBO para la optimización combinatoria, demostrando sus codificaciones explícitas y aplicaciones a problemas como la mochila y el viajante de comercio, así como a diversos juegos de lógica, para facilitar su uso en algoritmos cuánticos e inspirados en la cuántica.

Autores originales: Alejandro Mata Ali

Publicado 2026-05-04

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Alejandro Mata Ali

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 resolver un rompecabezas masivo y complicado. En el mundo de las computadoras, esto se llama optimización combinatoria. Es como intentar encontrar la única mejor manera de organizar un conjunto de elementos para obtener la puntuación más alta, mientras se siguen reglas estrictas.

Durante mucho tiempo, se ha enseñado a las computadoras a resolver estos rompecabezas utilizando un lenguaje específico llamado QUBO (Optimización Binaria Cuadrática Sin Restricciones). Piensa en QUBO como un lenguaje estricto donde cada pieza del rompecabezas solo puede estar en uno de dos estados: ENCENDIDO o APAGADO (como un interruptor de luz). Aunque esto funciona para muchas cosas, a menudo es como intentar describir una pintura compleja usando solo píxeles en blanco y negro. Tienes que usar miles de interruptores diminutos para representar solo un color, lo que hace que el rompecabezas sea enorme y difícil de resolver.

Este artículo introduce tres nuevos "lenguajes" más flexibles que permiten a las computadoras hablar en colores más ricos, facilitando la resolución de estos rompecabezas. El autor, Alejandro Mata Ali, muestra cómo funcionan estos nuevos lenguajes utilizando famosos problemas matemáticos y juegos de lógica.

Aquí tienes un desglose de los tres nuevos lenguajes y los juegos utilizados para probarlos:

1. QUDO: El "Dial" en lugar del "Interruptor"

El Concepto:
En el antiguo lenguaje QUBO, las variables son interruptores binarios (0 o 1). QUDO (Optimización Cuadrática Sin Restricciones D-aria) actualiza estos interruptores a diales. En lugar de estar simplemente ENCENDIDOS o APAGADOS, un dial puede configurarse en cualquier número desde 0 hasta un límite específico (como un botón de volumen que va de 0 a 10).

La Analogía:
Imagina que estás haciendo una maleta.

Enfoque QUBO: Tienes que decidir por cada calcetín, camisa y par de zapatos individuales si lo empacas (1) o no (0). Si quieres empacar 5 camisas, necesitas 5 interruptores separados.
Enfoque QUDO: Tienes un solo dial para "Camisas". Solo giras el dial a "5", y la computadora sabe que estás empacando cinco camisas.

Los Ejemplos del Artículo:

El Problema de la Mochila: Este es el clásico rompecabezas de "qué cabe en la bolsa". El artículo muestra que usar los diales de QUDO es mucho más eficiente que usar cientos de interruptores binarios para contar cuántos elementos de cada tipo tomas.
Hashiwokakero (Puentes): Un rompecabezas donde conectas islas con puentes. Dado que puedes construir 0, 1 o 2 puentes entre islas, un dial (0, 1 o 2) se ajusta perfectamente al problema, mientras que los interruptores binarios requerirían trucos adicionales para contar hasta 2.

2. T-QUDO: El Mapa de "Relación Inteligente"

El Concepto:
A veces, las reglas de un rompecabezas no se trata solo del valor de un dial, sino de la relación entre dos diales. T-QUDO (Tensor QUDO) es un lenguaje que entiende estas relaciones complejas directamente.

La Analogía:
Imagina una fiesta donde tienes que sentar a los invitados.

QUDO: Puedes decirle a la computadora: "El Invitado A está feliz si se sienta en la Silla 1".
T-QUDO: Puedes decirle a la computadora: "El Invitado A está feliz si se sienta en la Silla 1 Y el Invitado B se sienta en la Silla 3. Pero si el Invitado B se sienta en la Silla 4, el Invitado A se enoja".
T-QUDO permite que la computadora entienda estos emparejamientos específicos de "si-entonces" sin necesidad de descomponerlos en pasos binarios diminutos y torpes.

Los Ejemplos del Artículo:

Problema del Viajante de Comercio: Un vendedor debe visitar cada ciudad exactamente una vez. T-QUDO facilita decir: "Si estás en la Ciudad A en el paso 1, no puedes estar en la Ciudad A en el paso 2".
N-Reinas: El objetivo es colocar reinas en un tablero de ajedrez para que ninguna se ataque entre sí. T-QUDO maneja la regla "Si la Reina A está en la Fila 1, Columna 3, entonces la Reina B no puede estar en la Fila 2, Columna 4" de manera muy natural.
Kakuro & Inshi no Heya: Estos son rompecabezas numéricos (como el Sudoku pero con sumas y productos). T-QUDO permite que la computadora verifique sumas y productos de grupos de números directamente, en lugar de forzarlos a una matemática binaria.

3. HOBO: El "Abrazo de Grupo"

El Concepto:
A veces, una regla involucra tres o más variables actuando juntas al mismo tiempo. HOBO (Optimización Binaria de Orden Superior) es un lenguaje que permite que las variables interactúen en grupos, no solo en pares.

La Analogía:
Imagina un juego de sillas musicales.

Binario/Par: Solo puedes verificar si la Persona A está sentada junto a la Persona B.
HOBO: Puedes verificar si la Persona A, la Persona B y la Persona C están todas sentadas en una formación triangular específica al mismo tiempo. Captura la "dinámica de grupo" de una sola vez.

El Ejemplo del Artículo:

Solitario de Picas: Este es el juego donde saltas fichas sobre otras para eliminarlas. Un movimiento involucra tres puntos específicos: la ficha de inicio, la ficha saltada y el punto de aterrizaje. HOBO es perfecto para describir esta interacción de tres vías en un solo paso, haciendo que la solución sea mucho más limpia.

¿Por Qué Importa Esto?

El artículo argumenta que, aunque estos nuevos lenguajes (QUDO, T-QUDO, HOBO) son más complejos de aprender que el antiguo lenguaje binario, a menudo son mucho más eficientes para tipos específicos de problemas.

Menos Desorden: Utilizan menos variables (menos "interruptores" o "diales") para describir el mismo problema.
Mejor Hardware: El artículo señala que las futuras computadoras cuánticas (que utilizan "qudits" en lugar de solo "qubits") se están construyendo para hablar estos lenguajes de forma nativa. Al formular los problemas de esta manera ahora, nos preparamos para ese hardware futuro.
La Compensación: Puedes traducir estos nuevos lenguajes de vuelta al antiguo lenguaje binario (QUBO), pero a menudo hace que el problema sea más grande y desordenado. Es como traducir un poema del inglés a un idioma con solo 26 letras, y luego intentar forzarlo de vuelta al inglés: pierde su elegancia.

Resumen

El artículo es una guía para matemáticos y científicos de la computación. Dice: "Dejen de intentar forzar cada problema complejo en una caja simple de ENCENDIDO/APAGADO. A veces, necesitan un dial (QUDO), un mapa de relaciones (T-QUDO) o un abrazo de grupo (HOBO) para resolver el rompecabezas de manera eficiente".

El autor lo demuestra tomando difíciles juegos de lógica (como Hashiwokakero, N-Reinas y Solitario de Picas) y mostrando cómo estas nuevas formulaciones los resuelven con menos recursos y reglas más claras que los métodos tradicionales.

1. Planteamiento del Problema

Los problemas de optimización combinatoria (por ejemplo, Mochila, Viajante, N-Reinas) suelen ser NP-Difíciles y carecen de soluciones clásicas eficientes. Si bien la formulación de Optimización Binaria Cuadrática sin Restricciones (QUBO) es el estándar para mapear estos problemas al hardware cuántico (específicamente a través del Hamiltoniano de Ising y QAOA), presenta limitaciones:

Ineficiencia de Variables: Los problemas con estados naturales multivaluados (por ejemplo, seleccionar $k$ elementos de $n$ ) requieren codificación binaria, lo que aumenta el número de variables e introduce estados inválidos que requieren términos de penalización.
Limitaciones de Restricciones: Ciertas restricciones lógicas (por ejemplo, implicaciones de valores específicos o la no coincidencia de valores específicos) son difíciles o imposibles de implementar eficientemente en QUBO estándar debido a la naturaleza binaria de las variables ( $x_i^2 = x_i$ ).
Desajuste de Hardware: Las tecnologías cuánticas emergentes, como los qudits (sistemas cuánticos de nivel $d$ ), ofrecen una forma natural de representar variables no binarias, pero requieren formulaciones de optimización más allá de QUBO.

El artículo aborda la necesidad de formulaciones más generales que aprovechen los qudits y las interacciones de orden superior para reducir la sobrecarga de recursos y simplificar la implementación de restricciones.

2. Metodología

El autor introduce y analiza tres marcos de optimización generalizados, proporcionando formulaciones matemáticas explícitas y demostrando su aplicación a problemas clásicos y juegos combinatorios.

A. Optimización Cuadrática sin Restricciones D-aria (QUDO)

Definición: Una generalización de QUBO donde las variables $x_i$ son enteros no negativos acotados ( $x_i \in \{0, 1, \dots, d_i-1\}$ ) en lugar de binarios.
Función de Costo: $C(\vec{x}) = \sum_{i \le j} Q_{ij}x_i x_j + \sum D_i x_i$ .
Características Clave:
- Requiere qudits para su implementación directa.
- Permite términos lineales (a diferencia del QUBO puro donde $x_i^2=x_i$ ).
- Limitaciones: Ciertas restricciones (por ejemplo, "si $x_i=a$ entonces $x_j \neq b$ ") son difíciles de implementar porque el signo de los términos de interacción depende de los valores específicos de las variables no binarias.
- Implementación: Puede mapearse a QAOA utilizando puertas de fase de qudit $P(\theta)$ y puertas de fase controladas.

B. Optimización Cuadrática sin Restricciones D-aria Tensorial (T-QUDO)

Definición: Una generalización categórica por pares de QUDO. Trata las variables como etiquetas categóricas en lugar de valores numéricos.
Función de Costo: $C(\vec{x}) = \sum U_i(x_i) + \sum_{i<j} V_{ij}(x_i, x_j)$ .
Características Clave:
- Utiliza un tensor de costos $Q_{i,j, a, b}$ para definir el costo de asignar el valor $a$ a la variable $i$ y el valor $b$ a la variable $j$ .
- Ventaja: Supera las limitaciones de QUDO implementando fácilmente restricciones lógicas complejas (por ejemplo, implicaciones de valores específicos, no coincidencia de valores específicos) sin depender de propiedades aritméticas.
- Codificación: Puede codificarse en HOBO o QUBO (mediante codificación one-hot o binaria), aunque esto puede aumentar la cantidad de variables.

C. Optimización Binaria de Orden Superior (HOBO)

Definición: Una formulación que utiliza funciones pseudo-booleanas multilineales de orden $m$ (donde $m > 2$ ).
Función de Costo: $C(\vec{y}) = \sum_{S} q_S \prod_{i \in S} y_i$ , donde $y_i \in \{0, 1\}$ .
Características Clave:
- Permite interacciones entre más de dos variables.
- Relación con T-QUDO: Las interacciones de T-QUDO pueden codificarse en HOBO binarizando las etiquetas de qudit.
- Implementación: Aplicable directamente a dispositivos cuánticos basados en qubits que soportan interacciones de orden superior o mediante técnicas de reducción.

3. Contribuciones Clave y Estudios de Caso

El artículo valida estas formulaciones aplicándolas al Problema de la Mochila, al Problema del Viajante (TSP) y a cinco juegos combinatorios.

Problema	Formulación Utilizada	Idea Clave/Resultado
Mochila	QUDO	Demuestra una reducción significativa de recursos. En lugar de variables binarias para las cantidades de elementos, un solo qudit por clase de elemento representa la cantidad directamente. Reduce el número de variables y variables de holgura necesarias en comparación con QUBO.
Hashiwokakero	QUDO	Modela las conexiones de puentes (0, 1 o 2) de forma natural. Utiliza variables de flujo auxiliares (codificadas como qudits) para imponer conectividad global, demostrando que QUDO puede manejar restricciones topológicas complejas de manera exacta.
Viajante (TSP)	T-QUDO	Utiliza variables $x_t$ que representan el nodo en el paso de tiempo $t$ . La restricción "sin repetir" se maneja naturalmente mediante un término de penalización por pares $\delta_{x_t, x_{t'}}$ , evitando la necesidad de codificaciones complejas con números primos o matrices binarias masivas.
N-Reinas	T-QUDO	Reduce las variables de $N^2$ (cuadrícula binaria) a $N$ (índice de columna por fila). El tensor T-QUDO codifica naturalmente las restricciones de fila, columna y diagonal como entradas específicas del tensor, simplificando la estructura de la función de costo.
Kakuro	T-QUDO	Combina QUDO (para restricciones de suma) y T-QUDO (para restricciones de no repetición). La naturaleza categórica de T-QUDO maneja perfectamente la regla de "número único en una fila/columna".
Inshi no Heya	T-QUDO	Maneja restricciones de región multiplicativas convirtiendo productos en sumas de exponentes primos (funciones unarias), lo que encaja naturalmente en el marco de T-QUDO.
Solitario de Fichas	HOBO	Modela el juego como una secuencia de estados. La lógica de movimiento (saltar sobre una ficha) requiere interacciones de 4 variables (origen, medio, destino, tiempo), lo cual se expresa naturalmente en HOBO sin necesidad de reducir a términos cuadráticos.

4. Resultados

Eficiencia de Recursos: Las formulaciones QUDO y T-QUDO a menudo requieren menos variables que sus contrapartes QUBO. Por ejemplo, N-Reinas pasa de $N^2$ variables binarias a $N$ qudits.
Flexibilidad de Restricciones: T-QUDO permite la implementación directa de restricciones lógicas (implicación, no coincidencia) que son engorrosas o imposibles en QUDO/QUBO sin variables auxiliares.
Viabilidad: El artículo proporciona funciones de costo y términos de penalización explícitos para todos los ejemplos, demostrando que estas formulaciones son matemáticamente sólidas y "exactas" (es decir, las soluciones válidas tienen costo cero).
Implementación Cuántica: El autor describe cómo implementar estas funciones de costo en QAOA:
- QUDO: Utiliza puertas de fase de qudit individual y puertas de dos qudits.
- T-QUDO: Utiliza puertas de fase de enfoque controlado.
- HOBO: Utiliza puertas de fase multicontroladas (o reducciones basadas en ancillas).

5. Significado

Puente entre Teoría y Hardware: El artículo sirve como una guía práctica para utilizar el emergente hardware cuántico basado en qudits, superando la limitación binaria de la investigación actual centrada en qubits.
Optimización Algorítmica: Demuestra que elegir la formulación correcta (QUDO/T-QUDO/HOBO) basada en la estructura natural del problema puede reducir drásticamente la complejidad del paisaje de optimización, mejorando potencialmente el rendimiento de algoritmos cuánticos como QAOA.
Marco Educativo: Al utilizar juegos y acertijos conocidos, el artículo reduce la barrera de entrada para comprender formalismos de optimización de orden superior y multivaluados complejos.
Direcciones Futuras: El trabajo sugiere que las futuras arquitecturas de hardware cuántico deberían soportar interacciones de orden superior y qudits de forma nativa para resolver problemas combinatorios de manera más eficiente que los métodos actuales de reducción binaria.

En conclusión, el artículo argumenta que, aunque QUBO es una herramienta poderosa, QUDO, T-QUDO y HOBO ofrecen una eficiencia y expresividad superiores para clases específicas de problemas combinatorios, particularmente aquellos que involucran variables multivaluadas o restricciones lógicas complejas, y son directamente implementables en dispositivos cuánticos de próxima generación.