⚛️ quantum physics

Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem

Este artigo introduz o Quantum WalkScore (QWS), um benchmark escalável e orientado à aplicação que avalia o desempenho de computadores quânticos NISQ e futuros computadores tolerantes a falhas ao medir sua capacidade de resolver o problema de busca de nós em grafos usando caminhadas quânticas de tempo discreto e amplificação de amplitude, validado por meio de simulações e experimentos em processadores quânticos da IBM.

Autores originais: Noé Olivier, Michel Nowak

Publicado 2026-09-18

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Noé Olivier, Michel Nowak

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Na busca para construir máquinas que possam resolver problemas além do alcance dos supercomputadores atuais, cientistas correm para desenvolver computadores quânticos. Esses dispositivos não dependem dos simples interruptores de liga-desliga dos bits clássicos, mas utilizam, em vez disso, bits quânticos, ou qubits, que podem existir em múltiplos estados simultaneamente. Essa propriedade única permite que eles explorem vastas possibilidades ao mesmo tempo. No entanto, construir uma máquina que possa manter de forma confiável esses estados quânticos frágeis é incrivelmente difícil. Os dispositivos atuais são frequentemente assolados por ruído e erros, levando os pesquisadores a fazer uma pergunta crítica: como sabemos se um computador quântico está realmente funcionando e quão bom ele é para resolver tarefas do mundo real? Para responder a isso, a comunidade científica precisa de mais do que apenas uma lista de taxas de erro; eles precisam de um teste prático que meça se uma máquina consegue navegar com sucesso em um problema complexo.

Uma equipe de pesquisadores da CortAIx Labs, na França, propôs uma nova maneira de medir essa capacidade, chamada Quantum WalkScore. Em vez de testar propriedades matemáticas abstratas, seu benchmark pede que o computador realize uma tarefa específica e útil: encontrar um alvo oculto dentro de uma rede. Imagine um viajante tentando encontrar uma cidade específica em um vasto mapa de estradas conectadas. Um computador clássico verificaria as estradas uma por uma, mas um computador quântico pode explorar muitos caminhos ao mesmo tempo. Os pesquisadores focaram em duas ferramentas poderosas que os computadores quânticos usam para esse tipo de busca: um método chamado caminhada quântica de tempo discreto, que atua como uma forma sofisticada de se mover através da rede, e uma técnica chamada amplificação de amplitude, que aumenta as chances de encontrar a resposta correta. Ao combinar essas ferramentas, a equipe criou um teste que mede o quão grande uma rede um computador quântico consegue pesquisar antes que o ruído na máquina cause sua falha.

O benchmark é projetado para ser escalável, o que significa que pode começar com uma rede muito pequena e crescer para algo maior e mais complexo à medida que o hardware melhora. Os pesquisadores testaram este protocolo em dois tipos de formas de rede: um anel simples, onde cada ponto se conecta a dois vizinhos, e uma grade mais complexa que se envolve sobre si mesma, como a superfície de uma rosquinha. Eles definiram um objetivo claro: o computador deve encontrar o alvo oculto com uma taxa de sucesso superior ao que seria esperado pelo puro acaso. Se o computador tiver sucesso, o teste avança para uma versão ligeiramente maior ou mais difícil do problema. A pontuação final é simplesmente o tamanho da maior rede que o computador conseguiu resolver antes de não conseguir mais encontrar o alvo de forma confiável. Essa abordagem oferece um número concreto que qualquer pessoa pode entender, representando o limite prático da capacidade atual da máquina.

Para ver como isso funciona na prática, os pesquisadores executaram seus testes em várias gerações de processadores quânticos reais fornecidos pela IBM, incluindo modelos chamados Heron e Nighthawk. Eles também realizaram simulações em um computador perfeito e sem ruídos para ver como os resultados deveriam ser em um mundo ideal. As simulações mostraram que, com as configurações corretas, os algoritmos quânticos poderiam teoricamente resolver problemas muito grandes, encontrando o alvo com alta confiança. No entanto, quando a equipe executou os mesmos testes nas máquinas físicas reais, os resultados foram muito mais modestos. O ruído e os erros inerentes ao hardware atual significaram que os computadores só consegiam resolver redes muito pequenas com sucesso. Para as redes em formato de anel, as máquinas de melhor desempenho conseguiram encontrar o alvo em redes de um tamanho pequeno específico, mas conforme a rede crescia, a taxa de sucesso caía ao nível de um palpite aleatório.

O estudo destaca uma lacuna significativa entre o que os algoritmos quânticos podem fazer na teoria e o que o hardware atual pode realmente alcançar. Os pesquisadores descobriram que a complexidade do circuito necessário para executar a busca cresce rapidamente à medida que o problema se torna maior. Nas máquinas que testaram, circuitos que eram muito profundos ou complexos tornaram-se sobrecarregados por erros, fazendo com que a informação quântica se degradasse antes que a resposta pudesse ser encontrada. Mesmo com os processadores mais avançados disponíveis na época do estudo, a equipe só conseguiu demonstrar uma pontuação de prova de conceito, provando que o método funciona, mas também revelando o quanto o hardware precisa melhorar. Os resultados sugerem que, embora as ferramentas matemáticas estejam prontas, as máquinas físicas ainda estão nos estágios iniciais de serem capazes de lidar com as tarefas exigentes exigidas para aplicações do mundo real, como logística ou busca em bancos de dados.

Este novo benchmark, Quantum WalkScore, oferece uma maneira clara e honesta de acompanhar o progresso. Ele não depende de potencial teórico ou simulações idealizadas, mas mede o desempenho real da máquina de uma forma controlada e repetível. Ao estabelecer um padrão que exige que o computador vença o acaso aleatório em um problema de grafo específico, os pesquisadores fornecem um parâmetro para todo o campo. À medida que o hardware quântico evolui, tornando-se mais estável e menos propenso a erros, esta pontuação aumentará naturalmente. O trabalho serve como um lembrete de que o caminho para a computação quântica poderosa é uma subida gradual, onde cada passo em desempenho deve ser verificado pela resolução bem-sucedida de um problema que estava anteriormente fora de alcance. Os pesquisadores traçaram um mapa para essa jornada, mostrando exatamente onde as máquinas estão hoje e o que elas devem superar para alcançar o futuro.

Resumo Técnico: Quantum WalkScore (QWS)

Definição do Problema
O artigo aborda a necessidade de benchmarks orientados a aplicações para avaliar a maturidade de computadores quânticos de Escala Intermediária com Ruído (NISQ) e futuros computadores tolerantes a falhas. Enquanto os benchmarks existentes focam na fidelidade de portas físicas ou amostragem de circuitos aleatórios, há uma escassez de benchmarks que utilizem rotinas quânticas promissoras, especificamente o Passeio Quântico de Tempo Discreto (DTQW) e a Amplificação de Amplitude (AA), para resolver problemas de grafos práticos. Os autores focam no problema de busca de nó em grafos: identificar um nó alvo específico "marcado" $v_t$ dentro de um grafo não direcionado partindo de um nó de origem $v_0$ . Este problema serve como um bloco de construção fundamental para aplicações do mundo real, como roteamento de telecomunicações, busca em bancos de dados e análise de redes complexas.

Metodologia: O Protocolo Quantum WalkScore (QWS)
Os autores propõem o Quantum WalkScore (QWS), um protocolo de benchmark escalável projetado para medir o maior tamanho de problema que um computador quântico consegue resolver com sucesso.

Famílias de Grafos: O benchmark utiliza duas topologias de grafos específicas para equilibrar simplicidade, escalabilidade e aplicabilidade ao hardware:
1. Grafos de Ciclo: Estruturas 1D com $2^n$ nós, onde cada nó se conecta a dois vizinhos.
2. Grafos de Toro 2D: Estruturas 2D com $2^n \times 2^n$ nós, onde cada nó se conecta a quatro vizinhos (condições de contorno periódicas).
Instância do Problema: Definida por $(n, d)$ , onde $n$ é o número de qubits e $d$ é a distância (arestas do caminho mais curto) entre os nós de origem e alvo.
Rotina Algorítmica:
1. Inicialização: O sistema é inicializado no estado $|v_0\rangle$ .
2. Passeio Quântico de Tempo Discreto (DTQW): O caminhante evolui por $num\_w$ passos. O protocolo exige $num\_w \ge d$ e $num\_w \equiv d \pmod 2$ para garantir a alcançabilidade. Uma moeda de Hadamard é usada para um passeio não enviesado.
3. Amplificação de Amplitude (AA): A rotina DTQW é incorporada em uma estrutura de AA (Brassard et al.) para aumentar a probabilidade de medir o estado alvo. Isso envolve $num\_aa$ iterações de reflexão sobre o alvo e o estado inicial.
4. Medição: A probabilidade de sucesso $p_{exp}$ é medida como a probabilidade de observar o estado do nó alvo.
Critérios de Pontuação:
- Limiar de Probabilidade ( $p^*$ ): Um limiar dinâmico é definido para garantir que o sucesso seja significativamente melhor do que o palpite aleatório. Para distância $d \le 2$ , $p^* = 1/3$ . Para $d > 2$ , $p^* = 1/5 + 1/2^d$ .
- Métrica: A probabilidade de sucesso é calculada pela média de vários lotes (4 lotes de 1000 shots) e múltiplos instâncias de nós alvo (2 para ciclos, 4 para toro).
- Pontuação QWS: A pontuação é o maior tamanho de problema $(n, d)$ para o qual a probabilidade de sucesso medida excede $p^*$ antes da primeira falha. A pontuação é calculada como $QWS_{cycle} = 2^{e_n-1} + e_d$ e $QWS_{torus} = 2^{e_n} + e_d$ , onde $(e_n, e_d)$ é a última instância bem-sucedida.

Principais Contribuições

Design de Protocolo: Introdução de um protocolo de benchmark completo e orientado a aplicações que integra DTQW e AA, duas rotinas críticas para futuros algoritmos quânticos.
Escalabilidade e Reprodutibilidade: O protocolo é projetado para ser aplicável a qualquer computador quântico baseado em portas, com parâmetros experimentais padronizados (contagem de shots, loteamento) e parâmetros algorítmicos flexíveis ( $num\_w$ , $num\_aa$ ) deixados para o usuário final otimizar.
Análise Teórica e Empírica: O artigo fornece garantias teóricas para a existência de parâmetros que podem teoricamente resolver qualquer tamanho de problema, juntamente com estimativas detalhadas de recursos (escalonamento de profundidade de circuito) para implementações algorítmicas e de hardware nativo.
Validação Experimental: O protocolo é executado em três gerações de processadores quânticos da IBM (Heron r2, Heron r3 e Nighthawk r1), fornecendo uma avaliação de prova de conceito das capacidades atuais do hardware.

Resultados

Simulações Sem Ruído: Simulações em um computador quântico ideal demonstram que o benchmark é solucionável para grandes tamanhos de problema. No cenário "suff-perf" (minimizando iterações de AA), as probabilidades de sucesso permanecem próximas ao limiar. No cenário "best-perf", as probabilidades de sucesso aproximam-se de 1, embora isso exija profundidades de circuito maiores.
Escalonamento de Profundidade de Circuito: A profundidade algorítmica teórica escala como $O(nd)$. No entanto, quando transpilado para a arquitetura Heron da IBM, a profundidade nativa escala como $O(n^{3.45}d)$ para grafos de ciclo e $O(n^{2.2}d)$ para grafos de toro 2D, destacando o overhead significativo do mapeamento de hardware.
Desempenho Experimental em Hardware IBM:
- Experimentos no processador ibm_kingston (Heron r2) mostraram que as probabilidades de sucesso caem rapidamente conforme o tamanho do problema aumenta devido ao ruído e à decoerência.
- O sistema passou com sucesso no limiar apenas até o tamanho de problema (3, 1). A probabilidade de sucesso despencou para resultados semelhantes a palpites aleatórios para tamanhos subsequentes, com exceção do tamanho de problema (4, 1), que não constituiu uma sequência de sucesso contínua. Consequentemente, o Quantum WalkScore para grafos de ciclo foi determinado como 5 sob o cenário "suff-perf".
- Para instâncias maiores (ex: profundidade > 700 portas), os resultados degradaram para níveis indistinguíveis de um palpite aleatório.
- Comparações entre as arquiteturas Heron r2, Heron r3 e Nighthawk r1 mostraram tendências semelhantes, com a Heron r3 oferecendo uma precisão ligeiramente melhor, mas todas as arquiteturas atuais tiveram dificuldades com circuitos excedendo ~1000 portas.

Significância e Alegações
O artigo afirma que o QWS serve como uma ferramenta necessária para preencher a lacuna entre métricas de hardware abstratas e o desempenho de aplicações práticas. Ao focar no problema de busca de nó em grafos, ele avalia diretamente a capacidade de um hardware em executar primitivas quânticas essenciais (DTQW e AA) necessárias para tarefas de otimização e busca.

Os autores enfatizam que o benchmark destaca a interação entre parâmetros algorítmicos e limitações de hardware. Os resultados demonstram que, embora o framework teórico permita resolver problemas de grande escala, os dispositivos NISQ atuais são limitados pela profundidade do circuito e pelo acúmulo de erros. O artigo conclui que o QWS fornece uma pontuação significativa e interpretável para rastrear a maturação de computadores quânticos, distinguindo o desempenho entre dispositivos NISQ e futuros dispositivos de Computação Quântica Tolerante a Falhas (FTQC). A modesta pontuação de 5 alcançada no hardware atual ressalta os significativos desafios tecnológicos que ainda restam antes que esses algoritmos possam ser aplicados a problemas práticos de grande escala.

Resumo Técnico: Quantum WalkScore (QWS)

Mais como este