Cross-Platform Benchmarking of Near-Term Quantum Optimisation Algorithms

Este artigo apresenta um framework de benchmarking de nível de aplicação que compara o desempenho de algoritmos de otimização quântica de curto prazo (VQE e Annealing Quântico) em dispositivos comerciais contra três algoritmos clássicos, utilizando um problema de ciência de materiais QUBO denso como caso de teste e demonstrando que a eficácia desses métodos quânticos para problemas com até 72 variáveis é limitada pela conectividade do dispositivo, ruído e sobrecarga computacional clássica.

O essencial

Imagine que você tem um quebra-cabeça gigante e complexo, onde o objetivo é encontrar a configuração perfeita de peças para que tudo se encaixe da maneira mais eficiente possível. No mundo da computação, isso é chamado de otimização.

Este artigo é como um "teste de corrida" (benchmark) para ver quem consegue resolver esse quebra-cabeça mais rápido e melhor: computadores clássicos (os que usamos hoje) ou computadores quânticos (a tecnologia do futuro, que ainda está nascendo).

Aqui está a explicação simplificada, usando analogias do dia a dia:

1. O Problema: O "Gráfico de Grafite"

Os pesquisadores escolheram um problema específico para testar: encontrar a melhor maneira de remover alguns átomos de uma folha de grafeno (um material super forte e fino, como grafite).

• A Analogia: Imagine uma rede de amigos em uma festa. Você precisa convidar algumas pessoas para sair (criar "vazios" ou buracos), mas quer que o grupo restante continue se conectando o máximo possível. Se você tirar a pessoa errada, a festa fica desorganizada e "cara" (alta energia). O objetivo é tirar as pessoas certas para manter a festa mais barata e organizada (baixa energia).
• O Desafio: Existem tantas combinações possíveis que, para um computador comum, é como tentar adivinhar a senha de um cofre testando todas as combinações do mundo. É muito difícil.

2. Os Concorrentes: Quem está na pista?

O estudo colocou três tipos de "atletas" para correr essa prova:

• O "Maratonista Clássico" (Simulated Annealing): É um algoritmo clássico muito inteligente. Ele funciona como um ferreiro esfriando metal lentamente. Ele tenta soluções, erra, aprende e melhora gradualmente. É lento, mas muito confiável e consegue resolver problemas gigantes.
• O "Mágico Quântico 1" (VQE - Computador de Portas): Usa um computador quântico de IBM (baseado em portas lógicas, como um computador normal, mas quântico). Ele tenta "adivinhar" a resposta ajustando um circuito quântico repetidamente, como um músico afinando uma guitarra até o som ficar perfeito.
• O "Mágico Quântico 2" (QA - Recozimento Quântico): Usa um computador da D-Wave. Ele funciona como uma bola rolando por uma paisagem de montanhas e vales. A ideia é que, se você deixar a bola rolar devagar o suficiente, ela vai parar no ponto mais baixo (a solução perfeita).

3. O Que Aconteceu na Corrida? (Os Resultados)

A Vitória do Clássico (por enquanto):
O "Maratonista Clássico" (Simulated Annealing) venceu de forma esmagadora. Ele foi o mais rápido e encontrou as melhores soluções, mesmo para problemas com centenas de variáveis.

• Por que? Os computadores quânticos atuais ainda são como crianças aprendendo a andar: eles são rápidos em teoria, mas tropeçam muito na prática.

Os Obstáculos dos Quânticos:
Os computadores quânticos enfrentaram dois grandes problemas:

1. O Ruído (A Estática): Imagine tentar ouvir uma música perfeita em uma sala cheia de gente gritando. O "ruído" dos computadores quânticos atuais faz com que eles cometam erros e não encontrem a resposta certa.
2. O "Embaralhamento" (Embedding): Os computadores quânticos não têm todos os "botões" (qubits) conectados entre si. Para resolver o problema, os pesquisadores tiveram que "mapear" o problema para o hardware, o que é como tentar dobrar um mapa gigante para caber em um bolso pequeno. Esse processo de dobrar o mapa (chamado embedding) consumiu muito tempo e recursos, deixando o computador quântico lento.

O Recorde de Tamanho:

• O computador clássico conseguiu resolver problemas com 388 variáveis.
• O computador quântico (recozimento) conseguiu ir até 72 variáveis.
• O computador quântico de portas (VQE) travou em problemas maiores devido ao tempo de espera e erros.

4. Lições Aprendidas (O que os pesquisadores descobriram)

• A Regra do "Punição Leve": Eles descobriram que, ao invés de punir muito severamente as soluções erradas (o que cria um "abismo" difícil de atravessar), é melhor punir levemente e depois filtrar as respostas ruins manualmente. Isso ajudou os computadores quânticos a encontrarem melhores respostas.
• O Tempo é Dinheiro: Para os computadores quânticos, o tempo que eles passam "pensando" (no chip) é rápido, mas o tempo que eles passam "esperando na fila" e sendo configurados (no computador clássico) é enorme. A maior parte do tempo gasto não é no quantum, é no clássico!
• O Futuro: Embora os computadores quânticos ainda não tenham vencido, eles mostram potencial. O estudo serve como um "mapa" para mostrar onde estão os buracos na estrada (ruído, conectividade) para que os engenheiros possam consertá-los.

Resumo Final

Pense neste artigo como um relatório de um teste de carro. Os pesquisadores colocaram um carro de Fórmula 1 (o computador quântico) contra um carro de passeio confiável (o computador clássico) em uma pista cheia de buracos (ruído e limitações de hardware).

O carro de passeio chegou primeiro e foi mais estável. O carro de Fórmula 1 tem um motor incrível e potencial para ser o mais rápido do mundo, mas, por enquanto, ele ainda precisa de mais ajustes na suspensão e no motor para superar o carro comum em pistas reais.

A mensagem principal: A computação quântica é promissora, mas ainda precisa amadurecer antes de superar os computadores clássicos em problemas do mundo real. Este estudo nos dá as ferramentas para medir esse progresso de forma justa.

Resumo técnico

Resumo Técnico: Benchmarking Cross-Platform de Algoritmos de Otimização Quântica de Curto Prazo

1. Problema Abordado

O artigo foca na resolução de problemas de Otimização Combinatória utilizando computadores quânticos de curto prazo (NISQ - Noisy Intermediate-Scale Quantum). O caso de teste específico escolhido é a análise configuracional de estruturas de grafeno defeituosas.

• Definição do Problema: Dada uma folha de grafeno com $N$ sítios, o objetivo é remover um número fixo de átomos (neste estudo, 3 vacâncias) de modo a minimizar a energia do sistema. A energia é determinada pelo número de ligações carbono-carbono remanescentes; maximizar essas ligações equivale a minimizar a energia.
• Formulação: O problema é mapeado para um QUBO (Quadratic Unconstrained Binary Optimization), que é NP-difícil. A formulação envolve uma matriz de custo densa (grafo totalmente conectado) devido à inclusão de termos de penalidade para impor a restrição do número fixo de vacâncias.
• Desafio: O problema serve como um representante de alta densidade, desafiando a conectividade limitada dos dispositivos quânticos atuais e exigindo técnicas de embedding (mapeamento de variáveis lógicas para qubits físicos).

2. Metodologia

Os autores desenvolveram um framework de benchmarking cross-platform para comparar algoritmos quânticos e clássicos de forma justa e transparente, utilizando métricas agnósticas ao hardware.

• Algoritmos Testados:

  • Quânticos:
    • VQE (Variational Quantum Eigensolver): Executado tanto em um simulador de vetor de estado (sem ruído) quanto em um QPU real baseado em portas lógicas (IBM ibm_fez, 156 qubits).
    • QA (Quantum Annealing): Executado em um annealer quântico comercial (D-Wave Advantage 6.4, 5612 qubits físicos).
  • Clássicos:
    • Força Bruta (Brute Force): Solução exata (limitada a pequenos tamanhos).
    • Simulated Annealing (Recozimento Simulado): Método heurístico clássico.
    • Amostragem Aleatória: Linha de base probabilística.

• Métricas de Desempenho:

  • Probabilidade da Solução Ótima ($P_s$): Frequência com que o estado fundamental é encontrado.
  • Razão de Aproximação (AR): Medida da qualidade da solução em relação à energia mínima e máxima teórica.
  • Tempo de Execução do Usuário (User Runtime): Inclui codificação, latência e tempo no dispositivo.
  • Tempo no QPU (QPU Time): Tempo exclusivo de uso do hardware quântico.
  • Pós-seleção: Um passo crítico onde soluções que violam a restrição (número incorreto de vacâncias) são removidas. Os autores utilizam coeficientes de penalidade ($\lambda$) pequenos para manter a faixa de energia do QUBO reduzida, dependendo da pós-seleção para filtrar soluções inválidas.

• Técnicas de Mapeamento (Embedding):

  • Para o D-Wave, foram comparadas duas técnicas: Minor Embedding (padrão, heurístico) e Clique Embedding (otimizado para grafos totalmente conectados).

3. Contribuições Principais

1. Framework de Benchmarking Unificado: Introdução de um método padronizado para comparar algoritmos variacionais baseados em portas, annealing quântico e métodos clássicos no mesmo conjunto de instâncias QUBO.
2. Escala e Densidade: Aplicação do framework para resolver QUBOs totalmente conectados com até 72 variáveis, superando muitas limitações de estudos anteriores que focavam em grafos esparsos.
3. Análise de Escalabilidade:
   • Demonstração de que o Simulated Annealing clássico escala polinomialmente para este problema específico, resolvendo instâncias de até 388 variáveis.
   • Evidência preliminar de escalabilidade polinomial para o Quantum Annealing com clique embedding em tamanhos viáveis de hardware.
4. Insights Técnicos Detalhados:
   • Identificação de que coeficientes de penalidade pequenos ($\lambda$) combinados com pós-seleção aumentam a probabilidade de encontrar a solução ótima, evitando o alargamento excessivo do espectro de energia.
   • Revelação de que o overhead de embedding é o principal gargalo de tempo para o Quantum Annealing em problemas densos.
   • Demonstração de que o ruído e a falta de conectividade no VQE levam a grandes desvios padrão na probabilidade de sucesso e dificultam a convergência dos parâmetros variacionais.
   • Análise de como o tempo de computação clássica (compilação, otimização de parâmetros) domina o tempo total de execução no VQE, limitando o número de repetições experimentais.

4. Resultados Chave

• Desempenho no Problema de 18 Variáveis:
  • O Simulated Annealing foi o melhor método geral, oferecendo alta probabilidade de solução ótima ($P_s \approx 0.99$) e o menor tempo de execução.
  • O VQE no QPU (IBM) apresentou $P_s \approx 0.18$ (antes da pós-seleção) e $\approx 0.59$ (após pós-seleção), mas com um tempo de execução de usuário mais de 2 ordens de magnitude maior que o Simulated Annealing, devido ao tempo de compilação e iterações clássicas.
  • O Quantum Annealing (D-Wave) obteve $P_s \approx 0.19$ (antes) e $\approx 0.40$ (após pós-seleção). O tempo no QPU foi rápido, mas o tempo total foi dominado pelo processo de embedding.
• Escalabilidade:
  • O Simulated Annealing manteve-se eficiente até 338 variáveis.
  • O VQE falhou em retornar soluções não nulas para problemas acima de 50 variáveis no QPU real, devido à acumulação de erros, falta de convergência e restrições de tempo de acesso ao dispositivo.
  • O Quantum Annealing conseguiu resolver até 72 variáveis (com minor embedding) e 50 variáveis (com clique embedding), mostrando sinais de escalabilidade polinomial, embora a qualidade da solução degrade com o aumento do tamanho.
• Impacto do Ruído e Conectividade: A conectividade limitada dos dispositivos (necessidade de cadeias de qubits no D-Wave e portas SWAP no IBM) impõe um limite prático severo ao tamanho dos problemas que podem ser resolvidos com qualidade.

5. Significado e Conclusão

O estudo conclui que, embora os algoritmos quânticos de curto prazo ainda não superem os métodos clássicos heurísticos (como o Simulated Annealing) em termos de tempo de solução ou qualidade para este tipo de problema denso, o framework de benchmarking proposto é vital para:

1. Avaliar o Progresso do Hardware: Permitir o rastreamento de melhorias em dispositivos futuros (como o processador Heron da IBM ou o Advantage2 da D-Wave).
2. Identificar Gargalos: Mostrar que os obstáculos atuais não são apenas de hardware, mas também de overhead clássico (compilação, embedding) e limitações algorítmicas (como barren plateaus e ruído).
3. Guiar o Desenvolvimento Futuro: Sugerir que técnicas como warm-start, transferência de parâmetros, CVaR (Conditional Value at Risk) e error mitigation são necessárias para que a vantagem quântica se torne viável em problemas de otimização prática.

O trabalho enfatiza que a comparação justa ("end-to-end") entre abordagens completas (algoritmo + hardware + pré/pós-processamento) é essencial para entender o estado real da arte da computação quântica, indo além de comparações puramente teóricas ou focadas apenas no hardware.