Resource-Efficient Quantum Optimization via Higher-Order Encoding

Resumo Técnico: Otimização Quântica Eficiente em Recursos via Codificação de Ordem Superior

Definição do Problema
Problemas de otimização combinatória (COPs) são centrais para campos que variam de logística a biologia computacional, mas são frequentemente NP-difíceis, tornando-os computacionalmente intratáveis para solvers clássicos à medida que os tamanhos dos problemas crescem. Algoritmos quânticos, particularmente o Algoritmo de Otimização Aproximada Quântica (QAOA), oferecem um caminho potencial para abordar esses desafios. No entanto, as abordagens quânticas atuais são frequentemente limitadas pelas demandas de recursos das formulações de Otimização Binária Não Restrita Quadrática (QUBO). Codificações QUBO padrão, como a codificação One-Hot, exigem um número de qubits linear tanto no número de variáveis ($n$) quanto no número de valores possíveis por variável ($m$), resultando em $n \times m$ qubits. Além disso, impor restrições em QUBO tipicamente exige termos de penalidade grandes, o que aumenta a profundidade do circuito e a contagem de portas CNOT de dois qubits, tornando muitos problemas práticos inviáveis em hardware quântico de curto prazo.

Metodologia
Os autores propõem um framework sistemático utilizando a Otimização Binária Não Restrita de Ordem Superior (HUBO) para mitigar essas restrições de recursos. A metodologia envolve três componentes principais:

1. Codificação Binária vs. Codificação One-Hot: Em vez de usar a codificação One-Hot (onde cada par variável-valor é um qubit distinto), os autores empregam uma codificação Binária. Aqui, cada variável $i$ é representada por um registro binário compacto de $d = \lceil \log_2(m) \rceil$ bits. Isso reduz o requisito de qubits de $n \times m$ para $n \times \lceil \log_2(m) \rceil$.
2. Construção do Hamiltoniano HUBO: Os autores demonstram que esta codificação binária naturalmente leva a Hamiltonianos HUBO contendo termos de interação de ordem superior (até ordem $2 \times d$). Diferente de QUBO, que requer termos de penalidade para impor a restrição "one-hot" (que uma variável assuma apenas um valor), a codificação binária respeita inerentemente a atribuição de valor único. As restrições (ex: $s_i \neq s_j$) são incorporadas diretamente no Hamiltoniano ou via termos de penalidade que não requerem a expansão do espaço de variáveis.
3. Compilação de Circuito: Embora os termos de ordem superior impliquem formalmente interações de múltiplos qubits, os autores mostram que estes podem ser compilados inteiramente em portas padrão de um e dois qubits. Eles utilizam uma síntese de circuito baseada em Gray-code (seguindo Welch et al.) para implementar a unitária de custo $e^{-i\gamma \hat{H}_C}$. Esta abordagem minimiza operações redundantes ao aproveitar estados de paridade gerados para um termo para auxiliar na construção de outros, garantindo que a contagem assintótica de portas CNOT escale como $O(n^2 m^2)$, comparável a QUBO, mas com fatores constantes significativamente menores na prática.

Os autores também introduzem o PyHUBO, uma biblioteca Python de código aberto que automatiza a construção de Hamiltonianos HUBO e o cálculo de seus coeficientes usando transformadas de Walsh-Hadamard, garantindo que a complexidade numérica escale polinomialmente com o tamanho do problema.

Principais Contribuições

• Framework Sistemático: Um método geral para mapear COPs para Hamiltonianos HUBO usando codificações binárias, aplicável a problemas com restrições one-hot ou relacionadas.
• Redução de Recursos: Uma demonstração de que formulações HUBO reduzem significativamente a contagem de qubits e, crucialmente, o número total de portas CNOT necessárias para a execução do QAOA em comparação ao QUBO.
• Ferramenta de Software: O lançamento do PyHUBO para facilitar a adoção de modelos HUBO na comunidade quântica.
• Benchmarking: Avaliação abrangente através de três classes distintas de COP: Problema de Atribuição de Portas (GAP), Subgrafo Máximo k-Colorível (MkCS) e Programação Inteira (IP).

Resultos
Os autores testaram o QAOA usando codificações QUBO e HUBO nas três classes de problemas selecionadas. Os resultados indicam economias substanciais de recursos para o HUBO:

• Eficiência de Qubits: O HUBO reduz os requisitos de qubits de $O(nm)$ para $O(n \log m)$.
• Redução da Contagem de Portas: Para todas as instâncias testadas, o HUBO reduziu a contagem total de portas CNOT em pelo menos 89,6%. Em casos específicos, como nos benchmarks de Programação Inteira, as reduções atingiram até 97,1%.
• Qualidade da Solução: Para um número fixo de camadas de QAOA, o HUBO-QAOA consistentemente alcançou razões de aproximação melhores (mais próximas da solução ótima) do que o QUBO-QAOA. Por exemplo, no benchmark GAP, o HUBO alcançou um valor objetivo médio de 12,1 minutos versus 15,8 minutos para o QUBO.
• Convergência: O HUBO-QAOA atingiu razões de aproximação alvo com significativamente menos portas totais. No benchmark IP, o HUBO alcançou uma razão alvo de 0,60 com 1 camada, enquanto o QUBO exigiu 10 camadas, resultando no QUBO consumindo 31,6 vezes mais portas CNOT e 24,5 vezes mais portas RZ.
• Escalabilidade: A vantagem de recursos do HUBO persistiu e frequentemente aumentou conforme os tamanhos dos problemas cresciam, com o HUBO permanecendo tratável para tamanhos de problemas onde o QUBO-QAOA se tornou computacionalmente inviável devido aos excessivos requisitos de recursos.

Significância
O artigo argumenta que as formulações HUBO oferecem uma alternativa prática para a otimização quântica em dispositivos de curto prazo. Contrariando a intuição de que interações de ordem superior aumentariam as demandas de hardware, os autores mostram que a eliminação de termos de penalidade e a compressão da representação de variáveis levam a uma redução líquida na complexidade do circuito. Ao reduzir significativamente os requisitos de qubits e CNOT, a codificação HUBO ajuda a mitigar os gargalos de recursos que atualmente limitam a aplicação de algoritmos quânticos a problemas industriais do mundo real. Os autores concluem que esses métodos eficientes em recursos são cada vez mais vitais à medida que a tecnologia quântica avança e os tamanhos dos problemas escalam, permitindo aplicações mais viáveis na indústria e na pesquisa.