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

Este artigo apresenta e revisa as formulações QUDO, T-QUDO e HOBO para otimização combinatória, demonstrando suas codificações explícitas e aplicações a problemas como o da mochila e o do caixeiro-viajante, bem como a diversos jogos de lógica, para facilitar seu uso em algoritmos quânticos e inspirados em computação quântica.

O essencial

Imagine que você está tentando resolver um quebra-cabeça massivo e complicado. No mundo dos computadores, isso é chamado de otimização combinatória. É como tentar encontrar a única melhor maneira de organizar um conjunto de itens para obter a pontuação mais alta, seguindo regras estritas.

Por muito tempo, os computadores foram ensinados a resolver esses quebra-cabeças usando uma linguagem específica chamada QUBO (Otimização Binária Quadrática Não Constrained). Pense no QUBO como uma linguagem estrita onde cada peça do quebra-cabeça pode estar apenas em um de dois estados: LIGADO ou DESLIGADO (como um interruptor de luz). Embora isso funcione para muitas coisas, muitas vezes é como tentar descrever uma pintura complexa usando apenas pixels em preto e branco. Você precisa usar milhares de interruptores minúsculos para representar apenas uma cor, o que torna o quebra-cabeça enorme e difícil de resolver.

Este artigo apresenta três novas "linguagens" mais flexíveis que permitem que os computadores falem em cores mais ricas, tornando mais fácil resolver esses quebra-cabeças. O autor, Alejandro Mata Ali, mostra como essas novas linguagens funcionam usando famosos problemas matemáticos e jogos de lógica.

Aqui está uma análise das três novas linguagens e dos jogos usados para testá-las:

1. QUDO: O "Botão Giratório" em vez do "Interruptor"

O Conceito:
Na antiga linguagem QUBO, as variáveis são interruptores binários (0 ou 1). QUDO (Otimização D-ária Quadrática Não Constrained) atualiza esses interruptores para botões giratórios. Em vez de estar apenas LIGADO ou DESLIGADO, um botão giratório pode ser definido para qualquer número de 0 até um limite específico (como um botão de volume que vai de 0 a 10).

A Analogia:
Imagine que você está arrumando uma mala.

• Abordagem QUBO: Você tem que decidir para cada meia, camisa e par de sapatos individuais se deve embalá-lo (1) ou não (0). Se você quiser embalar 5 camisas, precisa de 5 interruptores separados.
• Abordagem QUDO: Você tem um único botão giratório para "Camisas". Você apenas gira o botão para "5", e o computador sabe que você está embalando cinco camisas.

Os Exemplos do Artigo:

• O Problema da Mochila: Este é o clássico quebra-cabeça "o que cabe na bolsa". O artigo mostra que usar botões giratórios QUDO é muito mais eficiente do que usar centenas de interruptores binários para contar quantos itens de cada tipo você leva.
• Hashiwokakero (Pontes): Um quebra-cabeça onde você conecta ilhas com pontes. Como você pode construir 0, 1 ou 2 pontes entre as ilhas, um botão giratório (0, 1 ou 2) se encaixa perfeitamente no problema, enquanto interruptores binários exigiriam truques extras para contar até 2.

2. T-QUDO: O Mapa de "Relação Inteligente"

O Conceito:
Às vezes, as regras de um quebra-cabeça não são apenas sobre o valor de um botão giratório, mas sobre a relação entre dois botões giratórios. T-QUDO (QUDO Tensorial) é uma linguagem que entende essas relações complexas diretamente.

A Analogia:
Imagine uma festa onde você tem que sentar os convidados.

• QUDO: Você pode dizer ao computador: "O Convidado A fica feliz se sentar na Cadeira 1."
• T-QUDO: Você pode dizer ao computador: "O Convidado A fica feliz se sentar na Cadeira 1 E o Convidado B sentar na Cadeira 3. Mas se o Convidado B sentar na Cadeira 4, o Convidado A fica bravo."
  O T-QUDO permite que o computador entenda esses pares específicos de "se-então" sem precisar quebrá-los em pequenos e desajeitados passos binários.

Os Exemplos do Artigo:

• Problema do Caixeiro Viajante: Um vendedor deve visitar cada cidade exatamente uma vez. O T-QUDO torna fácil dizer: "Se você está na Cidade A no passo 1, você não pode estar na Cidade A no passo 2."
• N-Rainhas: O objetivo é colocar rainhas em um tabuleiro de xadrez para que nenhuma se ataque. O T-QUDO lida com a regra "Se a Rainha A está na Linha 1, Coluna 3, então a Rainha B não pode estar na Linha 2, Coluna 4" de forma muito natural.
• Kakuro & Inshi no Heya: Estes são quebra-cabeças numéricos (como Sudoku, mas com somas e produtos). O T-QUDO permite que o computador verifique somas e produtos de grupos de números diretamente, em vez de forçá-los a uma matemática binária.

3. HOBO: O "Abraço de Grupo"

O Conceito:
Às vezes, uma regra envolve três ou mais variáveis agindo juntas ao mesmo tempo. HOBO (Otimização Binária de Ordem Superior) é uma linguagem que permite que variáveis interajam em grupos, não apenas em pares.

A Analogia:
Imagine um jogo de cadeiras musicais.

• Binário/Par: Você só pode verificar se a Pessoa A está sentada ao lado da Pessoa B.
• HOBO: Você pode verificar se a Pessoa A, a Pessoa B e a Pessoa C estão todas sentadas em uma formação triangular específica ao mesmo tempo. Captura a "dinâmica de grupo" de uma só vez.

O Exemplo do Artigo:

• Solitário de Pinos: Este é o jogo onde você pula pinos sobre outros para removê-los. Um movimento envolve três pontos específicos: o pino inicial, o pino pulado e o local de pouso. O HOBO é perfeito para descrever essa interação de três vias em um único passo, tornando a solução muito mais limpa.

Por Que Isso Importa?

O artigo argumenta que, embora essas novas linguagens (QUDO, T-QUDO, HOBO) sejam mais complexas de aprender do que a antiga linguagem binária, elas são frequentemente muito mais eficientes para tipos específicos de problemas.

• Menos Bagunça: Elas usam menos variáveis (menos "interruptores" ou "botões giratórios") para descrever o mesmo problema.
• Melhor Hardware: O artigo observa que futuros computadores quânticos (que usam "qudits" em vez de apenas "qubits") estão sendo construídos para falar essas linguagens nativamente. Ao formular problemas dessa maneira agora, estamos nos preparando para esse hardware futuro.
• A Troca: Você pode traduzir essas novas linguagens de volta para a antiga linguagem binária (QUBO), mas isso frequentemente torna o problema maior e mais confuso. É como traduzir um poema do inglês para uma linguagem com apenas 26 letras e depois tentar forçá-lo de volta ao inglês — perde-se a elegância.

Resumo

O artigo é um guia para matemáticos e cientistas da computação. Diz: "Pare de tentar forçar todo problema complexo em uma caixa simples de LIGADO/DESLIGADO. Às vezes, você precisa de um botão giratório (QUDO), um mapa de relacionamento (T-QUDO) ou um abraço de grupo (HOBO) para resolver o quebra-cabeça eficientemente."

O autor prova isso ao pegar jogos de lógica difíceis (como Hashiwokakero, N-Rainhas e Solitário de Pinos) e mostrar como essas novas formulações os resolvem com menos recursos e regras mais claras do que os métodos tradicionais.

Resumo técnico

1. Formulação do Problema

Problemas de otimização combinatória (por exemplo, Mochila, Caixeiro Viajante, N-Rainhas) são frequentemente NP-Difíceis e carecem de soluções clássicas eficientes. Embora a formulação de Otimização Binária Quadrática sem Restrições (QUBO) seja o padrão para mapear esses problemas em hardware quântico (especificamente via Hamiltoniano de Ising e QAOA), ela possui limitações:

• Ineficiência de Variáveis: Problemas com estados multivariáveis naturais (por exemplo, selecionar $k$ itens de $n$) exigem codificação binária, o que aumenta o número de variáveis e introduz estados inválidos que requerem termos de penalidade.
• Limitações de Restrições: Certas restrições lógicas (por exemplo, implicações de valores específicos ou não-coincidência de valores específicos) são difíceis ou impossíveis de implementar eficientemente no QUBO padrão devido à natureza binária das variáveis ($x_i^2 = x_i$).
• Incompatibilidade com Hardware: Tecnologias quânticas emergentes, como qudits (sistemas quânticos de $d$ níveis), oferecem uma maneira natural de representar variáveis não binárias, mas exigem formulações de otimização além do QUBO.

O artigo aborda a necessidade de formulações mais gerais que aproveitem qudits e interações de ordem superior para reduzir a sobrecarga de recursos e simplificar a implementação de restrições.

2. Metodologia

O autor introduz e analisa três frameworks de otimização generalizados, fornecendo formulações matemáticas explícitas e demonstrando sua aplicação em problemas clássicos e jogos combinatórios.

A. Otimização D-ária Quadrática sem Restrições (QUDO)

• Definição: Uma generalização do QUBO onde as variáveis $x_i$ são inteiros não negativos limitados ($x_i \in \{0, 1, \dots, d_i-1\}$) em vez de binárias.
• Função de Custo: $C(\vec{x}) = \sum_{i \le j} Q_{ij}x_i x_j + \sum D_i x_i$.
• Características Principais:
  • Requer qudits para implementação direta.
  • Permite termos lineares (diferente do QUBO puro onde $x_i^2=x_i$).
  • Limitações: Certas restrições (por exemplo, "se $x_i=a$ então $x_j \neq b$") são difíceis de implementar porque o sinal dos termos de interação depende dos valores específicos de variáveis não binárias.
  • Implementação: Pode ser mapeado para QAOA usando portas de fase de qudit $P(\theta)$ e portas de fase controladas.

B. Otimização D-ária Quadrática Tensorial sem Restrições (T-QUDO)

• Definição: Uma generalização categórica pairwise do QUDO. Trata variáveis como rótulos categóricos em vez de valores numéricos.
• Função de Custo: $C(\vec{x}) = \sum U_i(x_i) + \sum_{i<j} V_{ij}(x_i, x_j)$.
• Características Principais:
  • Usa um tensor de custo $Q_{i,j, a, b}$ para definir o custo de atribuir o valor $a$ à variável $i$ e o valor $b$ à variável $j$.
  • Vantagem: Supera as limitações do QUDO ao implementar facilmente restrições lógicas complexas (por exemplo, implicações de valores específicos, não-coincidência de valores específicos) sem depender de propriedades aritméticas.
  • Codificação: Pode ser codificado em HOBO ou QUBO (via codificação one-hot ou binária), embora isso possa aumentar a contagem de variáveis.

C. Otimização Binária de Ordem Superior (HOBO)

• Definição: Uma formulação usando funções pseudo-booleanas multilineares de ordem $m$ (onde $m > 2$).
• Função de Custo: $C(\vec{y}) = \sum_{S} q_S \prod_{i \in S} y_i$, onde $y_i \in \{0, 1\}$.
• Características Principais:
  • Permite interações entre mais de duas variáveis.
  • Relação com T-QUDO: As interações do T-QUDO podem ser codificadas em HOBO binarizando rótulos de qudit.
  • Implementação: Aplicável diretamente a dispositivos quânticos baseados em qubits que suportam interações de ordem superior ou via técnicas de redução.

3. Contribuições Principais e Estudos de Caso

O artigo valida essas formulações aplicando-as ao Problema da Mochila, Problema do Caixeiro Viajante (TSP) e cinco jogos combinatórios.

Problema	Formulação Utilizada	Insight/Resultado Chave
Mochila	QUDO	Demonstra redução significativa de recursos. Em vez de variáveis binárias para contagens de itens, um único qudit por classe de item representa a contagem diretamente. Reduz o número de variáveis e variáveis de folga necessárias comparado ao QUBO.
Hashiwokakero	QUDO	Modela conexões de pontes (0, 1 ou 2) naturalmente. Usa variáveis de fluxo auxiliares (codificadas como qudits) para impor conectividade global, provando que o QUDO pode lidar com restrições topológicas complexas exatamente.
Caixeiro Viajante (TSP)	T-QUDO	Usa variáveis $x_t$ representando o nó no instante de tempo $t$. A restrição "sem repetição" é naturalmente tratada via um termo de penalidade pairwise $\delta_{x_t, x_{t'}}$, evitando a necessidade de codificações complexas de números primos ou matrizes binárias massivas.
N-Rainhas	T-QUDO	Reduz variáveis de $N^2$ (grade binária) para $N$ (índice de coluna por linha). O tensor T-QUDO codifica naturalmente restrições de linha, coluna e diagonal como entradas específicas do tensor, simplificando a estrutura da função de custo.
Kakuro	T-QUDO	Combina QUDO (para restrições de soma) e T-QUDO (para restrições de não-repetição). A natureza categórica do T-QUDO lida perfeitamente com a regra "número único em uma linha/coluna".
Inshi no Heya	T-QUDO	Lida com restrições regionais multiplicativas convertendo produtos em somas de expoentes primos (funções unárias), que se encaixam naturalmente no framework T-QUDO.
Solitário de Pinos	HOBO	Modela o jogo como uma sequência de estados. A lógica de movimento (pular sobre um pino) requer interações de 4 variáveis (origem, meio, destino, tempo), o que é expresso naturalmente em HOBO sem necessidade de redução para termos quadráticos.

4. Resultados

• Eficiência de Recursos: Formulações QUDO e T-QUDO frequentemente exigem menos variáveis que suas contrapartes QUBO. Por exemplo, N-Rainhas cai de $N^2$ variáveis binárias para $N$ qudits.
• Flexibilidade de Restrições: O T-QUDO permite a implementação direta de restrições lógicas (implicação, não-coincidência) que são trabalhosas ou impossíveis em QUDO/QUBO sem variáveis auxiliares.
• Viabilidade: O artigo fornece funções de custo e termos de penalidade explícitos para todos os exemplos, demonstrando que essas formulações são matematicamente sólidas e "exatas" (ou seja, soluções válidas têm custo zero).
• Implementação Quântica: O autor descreve como implementar essas funções de custo em QAOA:
  • QUDO: Usa portas de fase de qudit único e portas de dois qudits.
  • T-QUDO: Usa portas de fase de foco controlado.
  • HOBO: Usa portas de fase multi-controladas (ou reduções baseadas em ancilla).

5. Significado

• Ponte entre Teoria e Hardware: O artigo serve como um guia prático para utilizar hardware quântico baseado em qudits emergente, indo além da limitação binária da pesquisa atual centrada em qubits.
• Otimização Algorítmica: Demonstra que escolher a formulação correta (QUDO/T-QUDO/HOBO) com base na estrutura natural do problema pode reduzir drasticamente a complexidade da paisagem de otimização, potencialmente melhorando o desempenho de algoritmos quânticos como o QAOA.
• Framework Educacional: Ao usar jogos e quebra-cabeças bem conhecidos, o artigo reduz a barreira de entrada para entender formalismos complexos de otimização de ordem superior e multivalorados.
• Direções Futuras: O trabalho sugere que futuras arquiteturas de hardware quântico devem suportar interações de ordem superior e qudits nativamente para resolver problemas combinatórios com mais eficiência do que os métodos atuais de redução binária permitem.

Em conclusão, o artigo argumenta que, embora o QUBO seja uma ferramenta poderosa, QUDO, T-QUDO e HOBO oferecem eficiência e expressividade superiores para classes específicas de problemas combinatórios, particularmente aqueles envolvendo variáveis multivaloradas ou restrições lógicas complexas, e são diretamente implementáveis em dispositivos quânticos de próxima geração.