Constrained Quantum Optimization at Utility Scale: Application to the Knapsack Problem

Resumo Técnico: Otimização Quântica Restrita em Escala de Utilidade

1. Problema e Contexto

O artigo aborda o desafio de resolver problemas de otimização combinatória com restrições em hardware quântico de curto prazo (NISQ), especificamente em escalas relevantes para aplicações industriais ("utility-scale").

• Contexto Industrial: O foco é o Problema de Comprometimento de Unidades (Unit Commitment - UC) em sistemas de energia, que envolve decidir quais geradores devem estar ligados para atender à demanda com custos mínimos, respeitando restrições operacionais complexas.
• Desafios Quânticos:
  1. Variáveis Contínuas: O UC original envolve variáveis contínuas e binárias, o que é difícil de mapear diretamente em hardware quântico devido à sobrecarga de recursos.
  2. Restrições: O espaço de soluções viáveis ocupa apenas uma fração do espaço de Hilbert total. Algoritmos padrão como o QAOA (Quantum Approximate Optimization Algorithm) tendem a explorar estados inviáveis, exigindo circuitos profundos para impor restrições estritamente, o que é proibitivo no hardware atual.
• Objetivo: Demonstrar a viabilidade de resolver uma versão simplificada (monoperíodo) do UC, reduzida a um Problema da Mochila 1D, utilizando até 150 qubits em hardware real da IBM, superando ou competindo com solvers clássicos de ponta como o Gurobi.

2. Metodologia

A abordagem proposta combina redução matemática do problema com um algoritmo quântico híbrido e eficiente em termos de hardware.

A. Redução do Problema de UC para Mochila (1D-Knapsack)

• Os autores simplificam o problema de UC removendo restrições de acoplamento temporal (como limites de rampa).
• Utilizam condições de otimalidade de primeira ordem (derivadas) para eliminar analiticamente a maioria das variáveis contínuas de produção de energia ($p_i$).
• O problema é transformado em uma otimização sobre um único parâmetro contínuo ($D$, custo marginal) e uma variável binária que decide quais unidades ligar.
• Para um $D$ fixo, o problema reduz-se puramente a um Problema da Mochila 1D: selecionar um subconjunto de itens (unidades) para maximizar o valor (minimizar o custo) sem exceder a capacidade (demanda de energia).

B. Algoritmo Copula-QAOA (cop-QAOA)
Para resolver a mochila em hardware quântico, utilizam uma variante do QAOA chamada cop-QAOA, que evita a necessidade de circuitos profundos para manter a viabilidade estrita:

• Estado Inicial Viesado (Warm-start): Em vez de uma superposição uniforme, o estado inicial é preparado com probabilidades de cada qubit estarem no estado $|1\rangle$ baseadas em uma heurística clássica ("Lazy Greedy" suavizada). Isso direciona o estado quântico para a região de soluções viáveis desde o início.
• Mixer de Copula: Utilizam um Hamiltoniano de mistura de profundidade constante (copula mixer) que introduz correlações entre os qubits. Diferente dos mixers tradicionais que exploram todo o espaço, este mixer é projetado para manter o estado próximo ao subespaço viável, permitindo a exploração de configurações próximas à viabilidade sem circuitos complexos de projeção.
• Treinamento: Os parâmetros variacionais ($\beta, \gamma$) são otimizados classicamente em simuladores e depois fixados para execução no hardware.

C. Seleção de Instâncias e Benchmarks

• Foram geradas instâncias de mochila projetadas para serem difíceis para solvers clássicos (distribuições de correlação inversa forte).
• Comparadores:
  • Gurobi: Solver comercial de otimização mista inteira.
  • Lazy Greedy: Heurística clássica usada como base para o "warm-start".
  • Amostrador Aleatório: Para demonstrar a dificuldade de encontrar soluções viáveis sem viés.

3. Principais Contribuições

1. Escala Recorde: Esta é a maior demonstração bem-sucedida do problema da mochila em hardware quântico da IBM, escalando até 150 qubits.
2. Validação em Escala de Utilidade: É a primeira investigação em escala industrial de estratégias de otimização restrita usando mixers rasos e estados iniciais viesados em hardware real.
3. Redução Eficiente: Demonstração prática de como reduzir um problema de otimização de energia complexo (UC) para um problema de mochila usando apenas um parâmetro contínuo adicional, viabilizando a execução quântica.
4. Desempenho Competitivo: O cop-QAOA conseguiu encontrar soluções que superam a heurística "Lazy Greedy" e, em casos específicos onde o Gurobi não atingiu o gap de otimalidade zero, encontrou soluções ligeiramente melhores que o Gurobi.

4. Resultados Experimentais

Os experimentos foram realizados no processador IBM Kingston (arquitetura Heron r2) com mitigação de erros via Q-CTRL Performance Management.

• Instância de 100 Itens:
  • O cop-QAOA encontrou soluções com valores melhores que o Lazy Greedy.
  • Em comparação com o Gurobi (que encontrou uma solução com gap de otimalidade de $4 \times 10^{-2}$), o cop-QAOA conseguiu igualar ou superar ligeiramente o melhor valor encontrado pelo Gurobi em algumas execuções.
  • A razão de soluções válidas (feasible) diminuiu no hardware à medida que a profundidade ($p$) aumentava, mas as melhores soluções encontradas ainda eram competitivas.
• Instância de 150 Itens:
  • O Gurobi encontrou a solução ótima.
  • O cop-QAOA no simulador superou o Lazy Greedy (razão de aproximação de 0.57 para 0.61).
  • No hardware, a fração de amostras válidas caiu drasticamente (de 0.89 para 0.13) devido ao ruído, e o melhor valor encontrado foi inferior ao do simulador, mas ainda superior ao de um amostrador aleatório (que falhou em encontrar qualquer solução válida).
• Eficiência Temporal: O tempo de execução no hardware (excluindo o treinamento clássico) foi inferior a 3 minutos para todas as 5 rodadas do QAOA, enquanto o Gurobi levou mais de 70 minutos para tentar melhorar a solução na instância de 100 itens.
• Paisagem de Treinamento: Os autores observaram que a paisagem de custo em função dos parâmetros $\gamma$ e $\beta$ é similar entre diferentes instâncias, sugerindo que parâmetros otimizados podem ser transferidos entre problemas, mitigando o problema de "barren plateaus".

5. Significado e Conclusão

O trabalho demonstra que a otimização quântica restrita é viável em escalas relevantes para a indústria, mesmo com hardware ruidoso.

• Viabilidade Prática: A estratégia de usar estados iniciais viesados e mixers rasos (cop-QAOA) é uma via promissora para problemas do mundo real, onde a imposição estrita de restrições via circuitos profundos não é possível.
• Competitividade: Embora o ganho quântico absoluto (superar o Gurobi em todos os casos) ainda seja limitado pela qualidade das soluções iniciais (warm-start) e pelo ruído, o algoritmo consegue refinar soluções clássicas e encontrar melhores resultados em cenários onde solvers clássicos têm dificuldade em fechar o gap de otimalidade.
• Futuro: O estudo abre caminho para extensões a problemas de UC de múltiplos períodos (com restrições temporais) e para o desenvolvimento de estratégias de treinamento e transferência de parâmetros mais robustas para otimização restrita.

Em suma, o artigo valida que, com a redução adequada do problema e técnicas de viés de estado, computadores quânticos atuais podem contribuir para a resolução de problemas de otimização energética complexos, oferecendo soluções competitivas em tempo de execução.