Towards High Performance Quantum Computing (HPQ): Parallelisation of the Hamiltonian Auto Decomposition Optimisation Framework (HADOF)

Este artigo demonstra que a paralelização do Framework de Otimização de Auto-Decomposição Hamiltoniana (HADOF) em processadores quânticos da IBM, tanto únicos quanto múltiplos, reduz significativamente o tempo de execução para resolver problemas de otimização combinatória em grande escala, incluindo instâncias reais de montagem de genomas, mantendo a qualidade da solução e avançando em direção à computação quântica de alto desempenho.

O essencial

Imagine que você está tentando resolver um quebra-cabeça massivo e incrivelmente complexo. Este não é apenas qualquer quebra-cabeça; é um "Quebra-Cabeça Quântico" que representa um problema do mundo real, como descobrir a ordem correta de fitas de DNA para montar um genoma.

O problema é que o quebra-cabeça é grande demais para qualquer pessoa (ou um único computador quântico) segurar em suas mãos. As peças são numerosas demais, e o "ruído" na sala (erros de hardware) torna difícil ver a imagem com clareza. Se você tentar forçar todo o quebra-cabeça sobre uma mesa pequena, ele não caberá, e você provavelmente cometerá erros.

Este artigo apresenta uma nova estratégia chamada HADOF (Framework de Otimização por Auto-decomposição de Hamiltoniano) para resolver isso. Eis como funciona, usando analogias simples:

1. O Problema: O Quebra-Cabeça "Grande Demais para Segurar"

Os computadores quânticos atuais são como bancadas de trabalho minúsculas e barulhentas. Eles só podem segurar algumas peças de quebra-cabeça por vez. Se você tentar resolver um problema enorme (como um genoma com milhares de fragmentos de DNA) de uma só vez em uma dessas bancadas, o computador fica sobrecarregado, as peças se misturam devido ao "ruído" e a solução falha.

2. A Solução: Dividindo-o em "Mini-Quebra-Cabeças"

Em vez de tentar resolver o quebra-cabeça gigante de uma só vez, o HADOF age como um organizador mestre. Ele divide o quebra-cabeça massivo em centenas de "mini-quebra-cabeças" (subproblemas) minúsculos e gerenciáveis.

• O Truque de Mágica: Ele não apenas corta o quebra-cabeça aleatoriamente. Usa um sistema inteligente para olhar as peças que você já colocou e usa essa informação para ajudar a resolver o próximo mini-quebra-cabeça.
• A Iteração: Ele resolve um mini-quebra-cabeça, aprende com ele, atualiza sua compreensão da imagem completa e, em seguida, resolve o próximo. Repete isso até que a imagem inteira esteja clara.

3. A Nova Reviravolta: A "Linha de Montagem" (Paralelização)

Anteriormente, este método funcionava como um único trabalhador em uma linha de montagem: resolva o mini-quebra-cabeça nº 1, depois o nº 2, depois o nº 3. Isso leva muito tempo.

Os autores deste artigo atualizaram o sistema para funcionar como uma fábrica movimentada com múltiplas linhas de montagem.

• Trabalhador Único vs. Equipe: Em vez de uma pessoa resolvendo os mini-quebra-cabeças um por um, eles usaram uma equipe de trabalhadores (múltiplos Computadores Quânticos, ou QPUs) para resolver diferentes mini-quebra-cabeças exatamente ao mesmo tempo.
• O Resultado: Eles descobriram que, ao usar uma equipe de quatro computadores quânticos, podiam concluir o trabalho 3 a 4 vezes mais rápido do que usando apenas um. Mesmo usando apenas um computador, mas organizando o trabalho em paralelo, tornou-se 3 vezes mais rápido.

4. O Teste do Mundo Real: Reencontrando uma "História" de DNA

Para provar que isso funciona no mundo real, a equipe testou em um problema biológico específico: Montagem de Genoma.

• A Analogia: Imagine que você rasgou um livro em milhares de tiras de papel minúsculas (leituras de DNA). Sua tarefa é colá-las de volta na ordem correta para ler a história.
• O Teste: Eles pegaram um conjunto de dados biológicos reais (um vírus chamado $\phi$X174) e tentaram remontá-lo usando sua nova "equipe de computadores quânticos".
• O Resultado:
  • Velocidade: A abordagem paralela foi muito mais rápida em obter um resultado.
  • Qualidade: Embora os computadores quânticos ruidosos não tenham obtido uma pontuação perfeita de 100% (devido ao "ruído" do hardware), eles ainda encontraram soluções muito boas. Na verdade, mais de 50% das soluções que geraram estavam corretas o suficiente para serem corrigidas na resposta perfeita usando ferramentas padrão de pós-processamento.
  • Comparação: Quando tentaram resolver todo o quebra-cabeça de DNA em um único computador quântico sem dividi-lo, o computador falhou em encontrar uma boa solução. O método de "dividir para conquistar" (HADOF) teve sucesso onde o método "tudo de uma vez" falhou.

5. A Visão Geral: "Computação Quântica de Alto Desempenho" (HPQ)

Os autores chamam essa abordagem de computação Quântica de Alto Desempenho (HPQ).

• Pense na diferença entre uma única pessoa tentando mover uma montanha de areia com uma colher versus uma frota de caminhões trabalhando juntos.
• O artigo argumenta que, para tornar os computadores quânticos verdadeiramente úteis para grandes problemas, não podemos apenas esperar que eles fiquem maiores e mais silenciosos. Precisamos mudar como os usamos: dividindo problemas em pequenas peças e resolvendo-os em paralelo em muitas máquinas.

Resumo das Afirmações

• Velocidade: Usar múltiplos computadores quânticos em paralelo torna a resolução desses problemas 3–4 vezes mais rápida.
• Escalabilidade: Este método permite resolver problemas (como 500 variáveis) que atualmente são grandes demais para um único computador quântico lidar.
• Precisão: Mesmo com hardware ruidoso e imperfeito, este método encontra soluções melhores do que tentar resolver o problema inteiro de uma só vez.
• Aplicação Real: Demonstrou com sucesso isso em uma tarefa real de montagem de genoma, mostrando que não é apenas uma teoria, mas uma ferramenta funcional.

Em resumo, o artigo diz: "Não tente comer o elefante inteiro de uma só mordida. Divida-o em pedaços pequenos e tenha uma equipe de computadores quânticos comê-los todos ao mesmo tempo. É mais rápido e funciona melhor."

Resumo técnico

1. Declaração do Problema

A aplicação prática da otimização quântica para problemas combinatórios (formulados como Otimização Binária Quadrática sem Restrições, ou QUBO) está atualmente limitada pelas restrições de dispositivos Quânticos de Escala Intermediária Ruidosa (NISQ). As principais restrições incluem:

• Contagem Limitada de Qubits: O hardware atual não pode hospedar grandes problemas QUBO que exigem centenas de variáveis.
• Ruído de Hardware: O acúmulo de ruído em circuitos profundos degrada a qualidade da solução.
• Escalabilidade: Os métodos de decomposição existentes (como o HADOF) são predominantemente sequenciais, falhando em explorar o paralelismo disponível em arquiteturas quânticas distribuídas ou recursos de Computação de Alto Desempenho (HPC).
• Limites de Simulação: Simular grandes circuitos quânticos classicamente é computacionalmente caro e intensivo em memória.

O artigo aborda essas questões estendendo o Framework de Otimização de Auto-Decomposição Hamiltoniana (HADOF) para suportar execução paralela em uma ou múltiplas Unidades de Processamento Quântico (QPUs), visando alcançar a Computação Quântica de Alto Desempenho (HPQ).

2. Metodologia

Framework Central: HADOF

O HADOF decompõe um Hamiltoniano QUBO global em sub-Hamiltonianos menores e gerenciáveis que podem ser resolvidos iterativamente.

1. Decomposição: O problema global é dividido em subproblemas (subconjuntos de variáveis).
2. Resolução Iterativa: Cada subproblema é resolvido usando um otimizador quântico (QAOA).
3. Integração de Contexto: Os valores esperados ($E[x_i]$) das variáveis dos subproblemas resolvidos são usados para aproximar o contexto para os subproblemas subsequentes.
4. Agregação: As soluções são recombinadas para formar uma solução global.

A Extensão Paralela

Os autores introduzem uma versão paralelizada do HADOF que difere da base sequencial em dois aspectos principais:

• Geração Independente: Em cada iteração, todos os sub-Hamiltonianos são gerados simultaneamente usando valores esperados da iteração anterior (em vez de atualizar valores sequencialmente dentro da iteração atual).
• Execução Assíncrona: Os subcircuitos são resolvidos concorrentemente. Isso permite:
  • Paralelismo Intra-QPU: Executar múltiplos trabalhos em uma única QPU (aproveitando o agendador).
  • Paralelismo Inter-QPU: Distribuir trabalhos entre múltiplas QPUs distintas (por exemplo, IBM Kingston, Pittsburgh, Fez, Marrakesh).

Detalhes de Implementação

• Otimizador: Utiliza uma abordagem QAOA digitalizada com Parametrização de Annealing Trotterizada para evitar loops de otimização clássica para os parâmetros $\beta$ e $\gamma$.
• Profundidade do Circuito: Os circuitos são construídos camada por camada (até 5 camadas). Em cada iteração, uma camada é adicionada a todos os subcircuitos.
• Tamanho do Subproblema: Fixado em 5 qubits ($k=5$) para manter alta fidelidade no hardware atual.
• Aplicação Alvo: Montagem de Genoma, modelada como um Problema do Caixeiro Viajante (TSP) em um grafo de sobreposição. O problema é codificado em um QUBO onde o objetivo é encontrar o caminho Hamiltoniano.

3. Principais Contribuições

1. Primeira Implementação HADOF em Dispositivo Real: O estudo move o HADOF de simulação teórica para execução em QPUs reais da IBM (Kingston, Pittsburgh, Fez, Marrakesh).
2. Estratégia de Paralelização: Demonstra um framework para execução concorrente de subproblemas decompostos, alcançando acelerações significativas no tempo de relógio sem comprometer a qualidade da solução.
3. Validação do Paradigma HPQ: Posiciona o HADOF como um caminho viável para a Computação Quântica de Alto Desempenho, integrando decomposição algorítmica com paralelismo em nível de sistema.
4. Aplicação do Mundo Real: Aplica com sucesso o framework a um problema de montagem de genoma (bacteriófago ϕX174), demonstrando sua utilidade em biologia computacional.
5. Benchmarking: Fornece uma comparação abrangente entre HADOF Sequencial, HADOF Paralelo (Única e Multi-QPU), QAOA de Circuito Completo Padrão e Annealing Simulado Clássico.

4. Principais Resultados

Velocidade e Eficiência

• Tempo de Relógio (Wall Clock Time):
  • Paralelo Multi-QPU: Alcançou uma redução de 3–4× no tempo de relógio em comparação com a execução sequencial em hardware real.
  • Paralelo Single-QPU: Alcançou até 3× de aceleração mesmo em um único dispositivo devido à orquestração eficiente de trabalhos.
  • Simulação: Prevê >5× de aceleração em modos de simulação paralela.
• Uso de QPU: Embora o tempo total de uso da QPU permaneça proporcional ao número de circuitos, o makespan (tempo total até a solução) é drasticamente reduzido, tornando a abordagem prática para aplicações sensíveis ao tempo.

Precisão e Robustez

• vs. QAOA Padrão: O HADOF supera significativamente o QAOA de circuito completo em hardware real.
  • A precisão do QAOA padrão caiu para quase zero (por exemplo, 0,02) para problemas de 50 variáveis em hardware ruidoso devido ao acúmulo de ruído.
  • O HADOF manteve >0,80 de precisão em hardware real para tamanhos similares.
• Resiliência ao Ruído: A decomposição limita a profundidade do circuito, prevenindo a degradação exponencial da precisão observada em circuitos monolíticos.
• Estudo de Caso de Montagem de Genoma:
  • Simulação Ideal: Tanto o HADOF sequencial quanto o paralelo alcançaram 100% de melhor precisão (correspondendo ao Annealing Simulado).
  • Hardware Real: A melhor precisão permaneceu competitiva (0,88–0,91), embora a frequência de encontrar o estado fundamental exato tenha caído para zero devido ao ruído. No entanto, >52% das soluções amostradas puderam ser pós-processadas para recuperar a sequência correta usando ferramentas padrão de bioinformática (GFAtools).

Escalabilidade

• O HADOF resolveu com sucesso problemas QUBO com até 500 variáveis em simulação e 300 variáveis em hardware real usando apenas circuitos de 5 qubits.
• O QAOA padrão de circuito completo é limitado a ~50 variáveis no mesmo hardware devido a restrições de conectividade e incorporação.

5. Significado e Conclusão

Esta pesquisa demonstra que decomposição e paralelismo não são meros paliativos para as limitações atuais de hardware, mas são habilitadores fundamentais de vantagem quântica prática.

• Escalabilidade: O HADOF contorna os limites físicos de qubits dos dispositivos atuais, permitindo a solução de problemas muito maiores do que o hardware pode suportar nativamente.
• Alinhamento com HPQ: O framework alinha-se com o paradigma emergente de Computação Quântica de Alto Desempenho, mostrando que arquiteturas quânticas distribuídas podem entregar ganhos de desempenho substanciais.
• Viabilidade Prática: Ao aplicar com sucesso o método à montagem de genomas, o artigo prova que a otimização quântica pode ser integrada em pipelines científicos do mundo real, desde que o ruído seja gerenciado através de estratégias de decomposição e execução paralela.

Os autores concluem que trabalhos futuros devem focar em estratégias de decomposição adaptativa, técnicas de mitigação de erros e na integração do HADOF em pipelines padrão de montagem de genomas com dados de sequenciamento real.