Symmetry-based quantum algorithms for open-shop scheduling with hard constraints

Este artigo apresenta uma abordagem baseada em simetria para codificar restrições rígidas em problemas de agendamento de loja aberta para computação quântica, propondo um novo algoritmo variacional que aproveita grupos de permutação que preservam a viabilidade para garantir a obtenção de soluções ótimas com certeza, otimizando apenas um número quadrático de parâmetros.

O essencial

O Panorama Geral: A Caixa de Quebra-Cabeça Quântica

Imagine que você é um gerente de logística tentando agendar uma frota de caminhões de entrega. Você tem uma lista de trabalhos (entregas), um conjunto de máquinas (caminhões) e uma linha do tempo (intervalos de tempo). As regras são estritas:

1. Cada trabalho deve ser feito exatamente uma vez.
2. Nenhum caminhão pode estar em dois lugares ao mesmo tempo.
3. Nenhum intervalo de tempo pode ter dois trabalhos.

Isso é chamado de Problema de Agendamento de Loja Aberta (OSSP). É um quebra-cabeça clássico "difícil". Se você tentar resolvê-lo com um computador normal, pode levar uma eternidade porque há muitas combinações erradas para verificar.

Os autores deste artigo perguntaram: Podemos usar um computador quântico para resolver isso mais rápido?

O problema é que os computadores quânticos atuais são como crianças pequenas desajeitadas; eles cometem erros facilmente. Se você apenas pedir a eles para "encontrar o melhor cronograma", eles frequentemente se perdem em "zonas proibidas" (cronogramas que quebram as regras, como atribuir dois trabalhos a um único caminhão ao mesmo tempo).

A solução da equipe é construir um robô quântico que só sabe andar no "caminho seguro". Eles projetaram um novo algoritmo que impede fisicamente o computador de considerar jamais um cronograma ilegal.

---

A Ideia Central: A Chave da "Simetria"

Para entender o truque deles, imagine uma sala cheia de pessoas (os cronogramas possíveis).

• Os Maus Cronogramas: Pessoas paradas nos lugares errados (quebrando regras).
• Os Bons Cronogramas: Pessoas paradas nos lugares certos.

A maioria dos algoritmos quânticos tenta empurrar as "pessoas ruins" para fora da sala dando a elas uma penalidade pesada (como uma multa). Mas isso é bagunçado. As pessoas ruins podem ainda ficar retidas, ou a penalidade pode não ser forte o suficiente.

A Abordagem dos Autores:
Em vez de punir as pessoas ruins, eles perceberam que os "Bons Cronogramas" têm uma simetria oculta.
Pense nos trabalhos como dançarinos e nos intervalos de tempo como parceiros de dança. Se você tiver uma rotina de dança perfeita (um cronograma válido), você pode trocar os parceiros de lugar de maneiras específicas e você ainda terá uma rotina perfeita.

Os autores descobriram um "grupo" matemático (um conjunto de regras) que descreve exatamente como você pode embaralhar esses trabalhos sem quebrar as regras. Eles chamam isso de Grupo de Preservação de Viabilidade.

A Analogia:
Imagine um Cubo Mágico.

• Abordagem Padrão: Você tenta resolvê-lo torcendo faces aleatoriamente e torcendo para não estragar as cores que já consertou.
• Abordagem deste Artigo: Você percebe que, se você torcer o cubo apenas de maneiras específicas e pré-aprovadas (simetrias), você está garantido de permanecer em um estado onde as cores ainda estão alinhadas. Você nunca precisa se preocupar em "quebrar" o cubo porque seus movimentos são matematicamente projetados para mantê-lo resolvido.

O Novo Algoritmo: A Máquina de "Embaralhar"

O artigo propõe um novo tipo de algoritmo quântico (um Algoritmo Quântico Variacional) que usa essa simetria.

1. Comece Seguro: Você inicia o computador com um cronograma válido (uma solução "semente").
2. O Misturador: Em vez de ruído aleatório, o computador aplica uma porta "misturadora" especial. Essa porta é como um botão de embaralhar que só troca trabalhos de lugar de maneiras matematicamente garantidas para manter o cronograma válido.
3. A Garantia: Os autores provaram um fato matemático muito forte: Se você tem $J$ trabalhos, você só precisa ajustar um número específico e gerenciável de "botões" (parâmetros) para alcançar qualquer cronograma válido possível, incluindo o absolutamente melhor.

A Analogia do "Botão":
Imagine que você tem um cofre gigante com uma fechadura de combinação.

• Métodos Quânticos Antigos: Você tem que adivinhar a combinação tentando bilhões de números aleatórios. Você pode ter sorte, mas também pode ficar preso em um beco sem saída.
• Este Método: Os autores encontraram o mapa. Eles provaram que você só precisa girar $J^3$ (aproximadamente o cubo do número de trabalhos) botões específicos para alcançar cada porta única no cofre. É como ter uma chave mestra que pode abrir cada porta se você apenas girar os mostradores certos na ordem certa.

O Que Eles Realmente Fizeram (A Prova)

O artigo não fala apenas de teoria; eles testaram isso.

1. A Simulação: Eles simularam uma versão pequena do problema (4 trabalhos, 2 máquinas) em um computador clássico.

   • Resultado: O método antigo (que usa "multas" para cronogramas ruins) falhou em encontrar boas soluções. Ele ficou preso nas "zonas proibidas".
   • Resultado: Seu novo método, que permanece estritamente no "caminho seguro", encontrou a solução perfeita rapidamente.

2. O Teste de Hardware Real: Eles pegaram uma versão minúscula do problema (3 trabalhos, 1 máquina — basicamente um problema do Caixeiro Viajante) e executaram em um computador quântico real (IBM Q System One).

   • Resultado: Mesmo que o computador real fosse ruidoso (como um rádio com estática), seu algoritmo ainda conseguiu encontrar a melhor solução com mais frequência do que o acaso aleatório. Isso mostrou que a lógica do "caminho seguro" funciona mesmo em hardware imperfeito.

A Conclusão

Este artigo trata de construir guardrails para computadores quânticos.

Em vez de esperar que o computador permaneça na estrada, eles redesenharam o carro para que ele não possa sair da estrada. Ao usar as simetrias matemáticas do problema de agendamento, eles criaram um algoritmo que:

• Nunca considera um cronograma impossível.
• Pode alcançar a solução perfeita girando um número específico e limitado de botões.
• Funciona melhor do que os métodos atuais, mesmo nas máquinas quânticas ruidosas e imperfeitas de hoje.

Eles ainda não resolveram o problema para todas as indústrias do mundo, mas construíram um novo motor, mais confiável, para resolver esse tipo específico de quebra-cabeça de agendamento.

Resumo técnico

Resumo Técnico: Algoritmos Quânticos Baseados em Simetria para Programação de Oficinas Abertas com Restrições Rígidas

Declaração do Problema
O artigo aborda o Problema de Programação de Oficinas Abertas (OSSP), um problema de otimização combinatória onde $J$ trabalhos devem ser distribuídos entre $M$ máquinas com $T$ intervalos de tempo cada. As restrições exigem que cada trabalho seja executado exatamente uma vez e que nenhum intervalo de tempo de máquina seja atribuído a mais de um trabalho. Este problema é uma generalização do Problema do Caixeiro Viajante (TSP), onde $TSP = OSSP(1, T, T)$.

O desafio central reside em codificar essas "restrições rígidas" em Algoritmos Quânticos Variacionais (VQAs). Diferentemente de problemas sem restrições (por exemplo, MAX-CUT) ou daqueles com restrições "codificadas de forma suave" (onde a inviabilidade é penalizada na função objetivo), o OSSP exige que a otimização permaneça estritamente dentro do subespaço viável. A codificação suave frequentemente leva a paisagens de otimização subótimas ou a problemas de viabilidade. Embora o Ansatz de Operador Alternante Quântico (QAOA) ofereça uma estrutura para restrições rígidas por meio de misturadores que preservam a viabilidade, construções existentes para problemas de programação têm sido frequentemente heurísticas, falhando em explorar plenamente as estruturas de simetria subjacentes do problema.

Metodologia
Os autores empregam uma abordagem rigorosa baseada na teoria dos grupos combinada com a teoria dos grafos para analisar a estrutura de viabilidade do OSSP:

1. Modelo de Grafo de Restrições: O problema é mapeado para um grafo de restrições $G=(V, E)$, onde os vértices representam atribuições potenciais de trabalho (bits) e as arestas representam restrições que proíbem atribuições simultâneas. As soluções correspondem a conjuntos independentes (cocliques) de tamanho $J$.
2. Grupo de Preservação de Viabilidade ($F$): Os autores identificam o grupo $F$ de permutações de valores de bits que mapeiam soluções viáveis para outras soluções viáveis. Eles provam que, para o OSSP, este grupo é isomorfo ao grupo de automorfismos do grafo de restrições, $\text{Aut}(G)$.
   • Para o caso "ocupado" ($MT = J$), a estrutura do grupo é um produto enlaçado envolvendo grupos simétricos.
   • Crucialmente, eles demonstram que $F$ age transitivamente sobre o conjunto de todas as soluções viáveis. Isso significa que qualquer solução viável pode ser transformada em qualquer outra por meio de uma sequência de permutações em $F$.
3. Design do Algoritmo:
   • Extensão do QAOA: Eles refinam a estrutura do QAOA construindo misturadores diretamente a partir dos geradores de $F$. Como $F$ age transitivamente, os misturadores derivados de seus elementos garantem que todo o subespaço viável seja acessível.
   • Novo VQA (Otimização de Grupo Quântico): Para instâncias ocupadas de OSSP, os autores propõem um algoritmo inovador que contorna o separador de fase padrão. Ao decompor permutações no grupo simétrico $S_J$ (que representa o espaço de soluções para OSSP ocupado) em produtos de transposições, eles constroem um circuito parametrizado usando portas SWAP.
   • Parametrização: O algoritmo utiliza uma decomposição específica de permutações em $J(J-1)/2$ transposições. Cada transposição é implementada como um produto de portas SWAP disjuntas através de blocos de trabalho.

Principais Contribuições

• Caracterização Teórica: O artigo fornece uma caracterização completa do grupo de preservação de viabilidade para o OSSP, provando seu isomorfismo ao grupo de automorfismos do grafo de restrições e estabelecendo sua ação transitiva sobre o conjunto de soluções.
• Alcançabilidade Garantida: Diferentemente do QAOA genérico, onde a alcançabilidade do ótimo é garantida apenas no limite de profundidade infinita do circuito ($p \to \infty$), o VQA proposto oferece um limite superior estrito para os parâmetros. Os autores provam que $O(J^3)$ (especificamente $J(J-1)/2$) parâmetros são suficientes para alcançar qualquer solução viável, incluindo o ótimo global, com certeza.
• Implementação de Restrições Rígidas: O trabalho demonstra um método sistemático para construir misturadores que preservam estritamente o subespaço viável, evitando as armadilhas da codificação suave de restrições.
• Implementação em Hardware: Os autores implementam o algoritmo em um dispositivo quântico real (IBM Q System One) para uma instância $OSSP(1, 3, 3)$ (equivalente a um TSP de 3 cidades) e realizam simulações sem ruído para uma instância $OSSP(2, 2, 4)$.

Resultados

• Simulação Sem Ruído ($OSSP(2, 2, 4)$): O VQA proposto com restrições codificadas rigidamente alcançou com sucesso o mínimo global (razão de aproximação de 100%) dentro de seis iterações (otimizando 12 parâmetros). Em contraste, um QAOA padrão com restrições codificadas de forma suave falhou em exceder uma razão de aproximação de 30%, mesmo com acesso a todos os 18 parâmetros, devido à dificuldade de concentrar amplitude no pequeno subespaço viável.
• Hardware Real ($OSSP(1, 3, 3)$): No IBM Q System One, o algoritmo demonstrou a capacidade de deixar o estado inicial e aumentar a sobreposição com o ótimo local. No entanto, os autores observam que o ruído do hardware obscureceu significativamente a convergência para o ótimo global, com o fundo ruidoso dominando o sinal. A simulação clássica ruidosa mostrou melhor convergência, sugerindo que as limitações atuais de hardware (tempo de coerência, fidelidade de portas) são os principais gargalos, e não o design algorítmico.

Significância e Afirmações
O artigo afirma que sua principal significância reside em fornecer uma estrutura sistemática baseada em simetria para codificar restrições rigidamente em VQAs, indo além do design heurístico de misturadores. Ao vincular a estrutura de viabilidade do problema aos automorfismos de grafos, os autores derivam um algoritmo com uma garantia teórica de que um número polinomial de parâmetros ($O(J^3)$) é suficiente para explorar todo o espaço de soluções.

Os autores são modestos quanto à escalabilidade prática. Eles reconhecem que, embora o limite teórico de parâmetros seja forte, a otimização prática desses parâmetros é prejudicada por "platôs estéreis" e pelo número exponencial de mínimos locais em espaços de alta dimensão. Além disso, eles afirmam explicitamente que sua abordagem depende de restrições de igualdade (simetrias) e pode não se aplicar diretamente a problemas com restrições de desigualdade (como o problema da mochila), onde tais simetrias estão ausentes. O trabalho serve como uma prova de conceito de que estruturas de grupos que preservam a viabilidade podem ser exploradas para projetar algoritmos quânticos mais eficientes e teoricamente fundamentados para problemas de programação, desde que melhorias futuras de hardware abordem questões de ruído e conectividade.