Optimized QUBO formulation methods for quantum computing

Título: Métodos Otimizados de Formulação QUBO para Computação Quântica

Autores: Dario De Santis, Salvatore Tirone, Stefano Marmi e Vittorio Giovannetti.

1. O Problema

Os dispositivos quânticos de escala intermediária ruidosa (NISQ), especialmente os quantum annealers (como os da D-Wave), possuem limitações severas de recursos, principalmente no número de qubits disponíveis e na conectividade entre eles. Muitos problemas de otimização combinatória, incluindo problemas NP-difíceis, podem ser resolvidos nesses dispositivos se forem reformulados como Otimização Binária Quadrática sem Restrições (QUBO).

No entanto, a conversão de problemas com restrições para a forma QUBO geralmente exige a introdução de variáveis de folga (slack variables) para transformar desigualdades em igualdades quadráticas. O método padrão para essa conversão frequentemente resulta em um número excessivo de variáveis de folga (comparável ou superior ao número de variáveis lógicas originais). Isso aumenta drasticamente o número de qubits necessários e a complexidade da conectividade do problema, tornando a execução em hardware quântico atual inviável para instâncias de tamanho realista.

2. Metodologia

Os autores propõem um novo conjunto de ferramentas para reformular problemas de otimização com restrições em QUBO, visando minimizar o uso de variáveis de folga. A abordagem é dividida em duas técnicas principais, que podem ser usadas de forma independente ou combinada:

A. Método do Polinômio Quadrático Iterativo (IQP - Iterative Quadratic Polynomial)

• Conceito: Em vez de usar a abordagem padrão de adicionar variáveis de folga para cobrir todo o intervalo de violação de uma restrição, o IQP constrói um polinômio quadrático genérico $P(x, s)$ que penaliza especificamente as combinações de variáveis binárias que violam a restrição.
• Processo Iterativo: O método começa tentando encontrar um polinômio sem variáveis de folga. Se não for possível satisfazer as condições de penalidade (valor $\le -1$ para violações e $0$ para satisfações), o método adiciona iterativamente variáveis de folga até que uma solução seja encontrada.
• Vantagem: É particularmente eficaz para restrições definidas sobre um pequeno número de variáveis lógicas. Permite lidar com restrições não-lineares e com parâmetros não-inteiros sem necessidade de aproximação.

B. Método Mestre-Satélite (MS - Master-Satellite)

• Conceito: Explora a sinergia entre múltiplas restrições que compartilham o mesmo conjunto de variáveis binárias. As restrições são divididas em "Mestres" e "Satélites".
  • Restrição Mestre: É imposta para todas as combinações possíveis de variáveis.
  • Restrição Satélite: É imposta apenas para as combinações que já satisfazem a restrição mestre.
• Mecanismo: Como a restrição satélite não precisa penalizar combinações que já violam a mestre (que já são penalizadas), o número de condições a serem satisfeitas pelo polinômio da satélite diminui, reduzindo a necessidade de variáveis de folga.
• Ajuste de Multiplicadores: Para evitar que a restrição satélite forneça "incentivos acidentais" (valores positivos) para combinações que violam a mestre, os autores introduzem multiplicadores relativos ($\lambda_{MC}$) que amplificam o peso da restrição mestre, garantindo que a penalidade líquida seja negativa mesmo com os incentivos acidentais.

C. Problemas Localmente Confinados

Os autores definem uma classe de problemas onde as restrições são definidas nó a nó em um grafo (dependendo apenas das arestas incidentes a cada nó). Para esses problemas, a combinação dos métodos IQP e MS (chamada de IQPMS) é altamente eficiente, permitindo a construção de formulações QUBO esparsas.

3. Estudo de Caso: MPBS (Max-Profit Balance Settlement)

Para validar as técnicas, os autores aplicaram o método IQPMS ao problema Max-Profit Balance Settlement (MPBS), um problema NP-difícil inspirado em cenários financeiros reais (liquidação de recebíveis).

• Objetivo: Maximizar o valor total de transações pagas, sujeito a duas restrições por nó:
  1. CAP/FLOOR: O saldo líquido do nó deve permanecer dentro de um intervalo pré-definido.
  2. IN/OUT: Se um nó participa de uma transação, ele deve ter pelo menos uma entrada e uma saída (evitar nós que apenas recebem ou apenas pagam).
• Aplicação: O problema foi modelado em grafos multirreais com dados de cenários financeiros (UniCredit). As restrições IN/OUT foram tratadas como "Mestres" e CAP/FLOOR como "Satélites".

4. Resultados Principais

Os autores testaram suas formulações em dois annealers quânticos da D-Wave: o Advantage_system4.1 (Adv1) e o protótipo Advantage2_prototype1.1 (Adv2).

• Redução de Variáveis de Folga:

  • A metodologia IQPMS reduziu o número de variáveis de folga necessárias em aproximadamente 90% em comparação com o método padrão.
  • Para nós com até 4 arestas, o método IQPMS não exigiu nenhuma variável de folga para as restrições IN/OUT e CAP/FLOOR, enquanto o método padrão exigia várias.
  • A dependência do número de variáveis de folga deixou de depender dos valores dos parâmetros do problema (como a amplitude do CAP/FLOOR), passando a depender apenas da topologia do grafo.

• Desempenho em Annealers Quânticos:

  • Taxa de Sucesso: A taxa de sucesso na obtenção da solução ótima (ou soluções dentro de 95% do ótimo) foi significativamente maior com o método IQPMS.
  • Fator de Ganho: O ganho multiplicativo de sucesso variou de 7x (para instâncias menores no Adv1) até 184x (para instâncias maiores no Adv2) em comparação com o método padrão.
  • Escalabilidade: Enquanto a qualidade da solução do método padrão degradava rapidamente com o aumento do tamanho da entrada, o método IQPMS manteve taxas de sucesso altas e estáveis, permitindo resolver instâncias maiores que seriam impossíveis com a formulação padrão devido à falta de qubits.
  • Eficiência de Embedding: O método IQPMS exigiu cerca de 2 qubits por aresta para mapear o problema no chip quântico, contra cerca de 10,5 qubits por aresta para o método padrão.

5. Significado e Conclusão

Este trabalho demonstra que a otimização da formulação QUBO é tão crítica quanto o hardware em si para o sucesso da computação quântica no cenário NISQ.

• Viabilidade Prática: As técnicas propostas desbloqueiam a possibilidade de resolver problemas de otimização financeira e logística complexos em hardware quântico atual, que anteriormente seriam limitados pelo número de qubits.
• Eficiência de Recursos: Ao reduzir drasticamente o número de variáveis de folga e a conectividade necessária, os métodos IQPMS tornam os problemas mais "amigáveis" aos annealers quânticos, melhorando a qualidade da saída e a taxa de sucesso.
• Generalidade: Embora testado no MPBS, as técnicas são aplicáveis a uma vasta gama de problemas de otimização combinatória localmente confinados, como problemas de mochila múltipla e subconjunto de soma.

Em resumo, os autores oferecem uma nova paradigma para a imposição de restrições em QUBO, substituindo a abordagem de "força bruta" com variáveis de folga por uma abordagem inteligente e iterativa que maximiza o potencial dos dispositivos quânticos atuais.