Quantum optimization beyond QUBO for industrial logistics and scheduling

Resumo Técnico: Otimização Quântica Além de QUBO para Logística e Agendamento Industrial

Declaração do Problema
Problemas de agendamento industrial e roteamento de transporte estão cada vez mais complexos, frequentemente possuindo estruturas matemáticas naturais que levam a formulações de Otimização Binária Não Constrained de Ordem Superior (HUBO) em vez de formulações puramente quadráticas. Embora o campo da otimização quântica tenha se concentrado predominantemente na Otimização Binária Não Constrained Quadrática (QUBO) devido ao seu mapeamento nativo para Hamiltonianos de Ising e compatibilidade com os atuais annealers quânticos, esse foco impõe limitações significativas. A redução de problemas HUBO para QUBO via variáveis auxiliares frequentemente infla o tamanho do problema (contagem de qubits), obscurece dependências-chave e falha em representar fielmente restrições operacionais intrincadas. Por outro lado, embora algoritmos quânticos digitais como o Algoritmo Quântico de Otimização Aproximada (QAOA) possam teoricamente lidar com interações de ordem superior, implementações de curto prazo em hardware ruidoso são frequentemente limitadas em profundidade à medida que as ordens de interação aumentam. Este artigo investiga o trade-off entre a compacidade representacional das formulações HUBO e seus custos de implementação em hardware quântico atual e emergente.

Metodologia
Os autores propõem e analisam formulações HUBO para três casos de uso industriais representativos:

1. QUEST (Transporte Compartilhado Aprimorado por Quântica): Um problema de pareamento de veículos onde "quebradores" são emparelhados com "surfistas" para minimizar o arrasto aerodinâmico e discrepâncias de tempo/velocidade.
2. CVRP (Problema de Roteamento de Veículos com Capacidade): Um problema de roteamento de frota com restrições de capacidade, estendendo o Problema do Caixeiro Viajante.
3. Agendamento de Montagem Automotiva: Um problema de sequenciamento de carros envolvendo restrições de lacuna, grupo e pista de armazenamento em uma linha de montagem.

Para cada caso de uso, os autores reformulam o problema como um HUBO usando codificações binárias compactas (escalonamento logarítmico em variáveis) em vez de codificações one-hot padrão (escalonamento linear). Essas formulações são validadas usando solucionadores clássicos, incluindo Recozimento Simulado (SA) e Busca Tabu Mémética (MTS), e comparadas com Programação Linear Inteira (ILP) e soluções de força bruta.

Para avaliar a viabilidade quântica, os autores empregam o algoritmo Otimização Quântica Counterdiabatic Digitizada com Campo de Viés (BF-DCQO). Este protocolo estende o DCQO padrão introduzindo um mecanismo de feedback iterativo usando campos de viés longitudinais derivados de resultados de medições anteriores para guiar o sistema em direção a configurações de menor energia. Os autores estimam requisitos de recursos (contagem de qubits, contagem de portas de dois qubits, profundidade do circuito) e fidelidade do circuito sob várias suposições de conectividade de hardware (todos-para-todos, heavy-hex, grade quadrada) e modelos de ruído.

Principais Contribuições

• Formulação de Modelos HUBO: O artigo fornece formulações HUBO explícitas para QUEST, CVRP e agendamento automotivo, demonstrando como codificações binárias compactas reduzem o número de variáveis binárias de $O(N)$ ou $O(N^2)$ para $O(N \log N)$.
• Análise de Trade-off: O trabalho destaca sistematicamente o trade-off central: formulações HUBO reduzem significativamente os requisitos de qubits (escalonamento de qubits), mas introduzem termos de interação de ordem superior que necessitam de circuitos mais profundos com mais portas de dois qubits.
• Análise de Recursos e Escalabilidade: Os autores fornecem estimativas detalhadas de fidelidade do circuito e tempo de execução para BF-DCQO. Eles demonstram que, embora o HUBO reduza a pegada de qubits, o decaimento exponencial da fidelidade do circuito com o aumento das contagens de portas de dois qubits representa um gargalo crítico para dispositivos quânticos intermediários de escala ruidosa (NISQ) atuais.
• Proposta de Fluxo de Trabalho Híbrido: Para instâncias de grande escala (por exemplo, agendamento automotivo) onde a execução quântica completa é inviável, o artigo propõe e avalia um fluxo de trabalho híbrido de horizonte rolante. Esta abordagem decompõe o problema global em subproblemas localizados solucionáveis por solucionadores clássicos ou quânticos de curto prazo, preservando a estrutura de ordem superior do objetivo completo.

Resultados

• Validação de QUEST e CVRP: Para pequenas instâncias (até 6 quebradores/surfistas para QUEST e pequenas instâncias de CVRP), as simulações de BF-DCQO recuperam soluções ótimas, validando a codificação HUBO. No entanto, à medida que o tamanho do problema aumenta, a razão de aproximação para BF-DCQO degrada-se mais rapidamente do que o Recozimento Simulado clássico em HUBO quadratizado, consistente com o rápido aumento na complexidade do circuito.
• Restrições de Hardware: A análise revela que, para hardware atual (por exemplo, heavy-hex ou grade quadrada da IBM), codificações QUBO frequentemente permanecem mais viáveis devido a contagens mais baixas de portas de dois qubits, apesar de exigirem mais qubits. Formulações HUBO tornam-se competitivas apenas em termos de contagem de portas em arquiteturas com conectividade todos-para-todos (por exemplo, íons aprisionados) e, mesmo assim, são limitadas a instâncias muito pequenas (por exemplo, 4 clientes no CVRP) devido ao tempo de coerência e acúmulo de erros.
• Limites de Escalabilidade: Para uma instância representativa de grande escala de CVRP (100 clientes), os autores estimam que uma implementação fiel de circuitos DCQO exigiria taxas de erro médio de portas de dois qubits abaixo de $10^{-10}$, um nível alcançável apenas no regime de qubits lógicos habilitado pela correção de erros quânticos.
• Desempenho de Agendamento: No caso de agendamento automotivo, solucionadores clássicos (MTS e ILP) foram usados para comparar a formulação HUBO. O MTS reduziu efetivamente violações FIFO (Primeiro a Entrar, Primeiro a Sair), mas lutou com restrições de grupo de ordem superior à medida que o tamanho do problema crescia. A abordagem híbrida de horizonte rolante usando SA forneceu uma redução equilibrada tanto em violações locais quanto globais.

Significado e Alegações
O artigo alega modestamente que sua contribuição primária não é a demonstração de vantagem quântica em instâncias de escala industrial, mas sim uma clarificação de quando formulações de ordem superior oferecem uma vantagem representacional significativa e como essa vantagem é restringida pelos requisitos de recursos quânticos.

Os autores concluem que:

1. HUBO vs. QUBO: Formulações HUBO oferecem escalonamento superior de qubits, tornando-as potencialmente mais atraentes do que QUBO em configurações de tolerância a falhas iniciais onde as contagens de qubits são limitadas, mas as fidelidades de portas são altas.
2. Limitações Atuais: A implementação prática em hardware NISQ atual é restringida pela fidelidade de portas, tempos de coerência e profundidade do circuito. Os requisitos aumentados de portas de dois qubits do HUBO frequentemente superam os benefícios de contagens reduzidas de qubits em dispositivos atuais.
3. Caminhos Futuros: O cenário mais plausível para o uso prático dessas formulações é um fluxo de trabalho híbrido quântico-clássico sequencial. Neste paradigma, rotinas quânticas atuam como etapas de refinamento para subproblemas localizados dentro de um pipeline de otimização predominantemente clássico. Esta abordagem aproveita o escalonamento favorável de qubits do HUBO enquanto mitiga os tempos de execução proibitivos e o acúmulo de erros associados à otimização quântica ponta a ponta, mesmo em regimes de tolerância a falhas iniciais.

O trabalho sublinha que a viabilidade da otimização quântica na indústria depende de alinhar a estrutura do problema com as capacidades do hardware, sugerindo que estratégias híbridas são essenciais para fechar a lacuna entre as vantagens teóricas do HUBO e a implementação prática.