A brief history of quantum vs classical computational advantage

Este artigo de revisão resume de forma abrangente todos os experimentos que reivindicam vantagem computacional quântica, examina criticamente seus desafios e refutações, discute vantagens teóricas em problemas específicos e destaca o progresso recente na correção de erros quânticos como um passo fundamental para alcançar vantagem no algoritmo de Shor.

O essencial

A Grande Imagem: A Grande Corrida

Imagine uma corrida entre dois corredores: Computadores Clássicos (os maratonistas super-rápidos e confiáveis que usamos hoje) e Computadores Quânticos (os velocistas misteriosos e relâmpagos que operam sob as regras estranhas da física quântica).

O objetivo deste artigo é manter uma planilha de pontuação de cada vez que o Velocista Quântico afirma: "Posso resolver este quebra-cabeça específico mais rápido que o Corredor Clássico!" O autor, Ryan LaRose, atua como um historiador esportivo, revisando cada corrida, cada protesto e cada desclassificação para nos dizer exatamente onde a corrida está hoje.

O artigo define "vantagem" simplesmente: Quem termina a tarefa primeiro? Não importa se a tarefa é útil (como curar uma doença) ou apenas um quebra-cabeça bobo; a única questão é a velocidade.

---

Parte 1: As Corridas de "Quebra-Cabeça Bobo" (Vantagem Experimental)

Até agora, os Velocistas Quânticos tentaram vencer três tipos específicos de corridas "bobas". Estas ainda não são úteis para construir pontes ou escrever e-mails; elas foram projetadas especificamente para serem difíceis para computadores clássicos, mas fáceis para os quânticos.

1. A Corrida de Amostragem de Circuitos Aleatórios (O "Caos do Lançamento de Moedas")

• A Tarefa: Imagine uma máquina que lança 53 moedas de uma vez, de forma completamente aleatória e caótica. O computador quântico faz isso e registra o padrão de caras e coroas. O computador clássico tem que adivinhar qual seria o padrão.
• A Primeira Vitória (Google, 2019): O computador "Sycamore" da Google fez isso em 200 segundos. Eles afirmaram que um supercomputador clássico levaria 10.000 anos para fazer a mesma matemática.
• O Contra-Ataque: Os corredores clássicos não desistiram. Eles inventaram novas e mais inteligentes maneiras de resolver o quebra-cabeça.
  • Analogia: Imagine que o corredor clássico percebeu que não precisava percorrer toda a pista; ele podia pegar um atalho através de um túnel que havia encontrado.
  • O Resultado: Com o tempo, os computadores clássicos ficaram mais rápidos. Em 2024, um supercomputador clássico conseguiu realizar a mesma tarefa em 86 segundos, superando o computador quântico.
• O Veredito: A primeira vitória da Google foi "refutada". O corredor clássico alcançou e ultrapassou-os. No entanto, a Google tentou novamente com quebra-cabeças maiores e mais difíceis (mais moedas, mais lançamentos), e essas corridas mais recentes ainda não foram refutadas.

2. A Corrida de Amostragem de Bósons Gaussianos (O "Pinball de Fótons")

• A Tarefa: Em vez de moedas, esta corrida usa partículas de luz (fótons) quicando por um labirinto de espelhos. O computador quântico os dispara e eles aterrissam em pontos específicos. O computador clássico tem que calcular onde eles aterrissaram.
• Os Concorrentes: Equipes da China (USTC) e do Canadá (Xanadu) construíram esses corredores baseados em luz.
• O Contra-Ataque: Assim como na corrida das moedas, os computadores clássicos encontraram "brechas". Eles perceberam que, se as partículas de luz não fossem perfeitas (o que nunca são), a matemática se tornava mais fácil. Eles construíram novos algoritmos para simular o labirinto de luz muito mais rápido do que o esperado.
• O Veredito: A maioria dessas alegações foi "fracamente refutada". Isso significa que os computadores clássicos ainda não venceram os quânticos até agora nos maiores quebra-cabeças, mas estão suficientemente perto de que um computador clássico ligeiramente melhor no futuro próximo provavelmente poderia.

3. A Corrida de Simulação Quântica (A "Previsão do Tempo")

• A Tarefa: Simular como um sistema complexo (como um material magnético) muda ao longo do tempo.
• Os Concorrentes: IBM e D-Wave.
• O Contra-Ataque: A IBM alegou que simulou um sistema magnético mais rápido que um computador clássico. Mas dentro de duas semanas, pesquisadores clássicos mostraram que podiam simulá-lo em um laptop em poucos minutos.
• O Veredito: A alegação da IBM foi rapidamente "refutada". O corredor clássico encontrou uma rota muito mais rápida. A tentativa recente da D-Wave ainda está sendo observada, mas é provável que enfrente desafios semelhantes.

---

Parte 2: As Corridas "Teóricas" (As Provas Matemáticas)

Às vezes, matemáticos dizem: "Se construirmos um computador quântico perfeito, ele deveria vencer esta corrida." Mas a história mostra que os matemáticos clássicos são muito bons em encontrar novos truques.

• A Corrida do Sistema de Recomendação: Um algoritmo quântico foi proposto para recomendar filmes para você mais rápido que qualquer computador clássico.
  • A Reviravolta: Um matemático clássico (Ewin Tang) percebeu: "Ei, se dermos ao computador clássico a mesma estrutura de dados especial que o quântico usa, ele pode resolver o problema tão rápido quanto!"
  • O Resultado: A vantagem quântica desapareceu. Isso é chamado de "desquanticização".
• A Corrida de Otimização: Histórias semelhantes aconteceram com algoritmos projetados para resolver problemas complexos de agendamento. A vantagem quântica foi alegada e, em seguida, um algoritmo clássico foi encontrado que era tão bom quanto.

---

Parte 3: A Fronteira Final (Correção de Erros)

Aqui está a conclusão mais importante do artigo: Computadores quânticos são frágeis.

• A Analogia: Imagine que o Velocista Quântico é um corredor de vidro. Eles são incrivelmente rápidos, mas se tropeçarem em uma pedrinha minúscula (ruído), eles se estilhaçam. Para correr uma maratona (como fatorar números grandes para quebrar criptografia), eles precisam usar uma armadura.
• A Armadura: Esta armadura é chamada de Correção de Erros Quânticos. Ela usa muitos "qubits" físicos de "vidro" para criar um único "qubit" lógico e robusto.
• O Status Atual: Estamos apenas começando a construir essa armadura.
  • Em 2024, a Google anunciou um novo chip (Willow) onde o "qubit" lógico (o blindado) durou mais tempo que os "qubits" físicos individuais (os de vidro).
  • Este é o momento do "Santo Graal". Prova que adicionar mais partes para corrigir erros realmente torna o sistema melhor, e não pior.
• O Futuro: Até termos essa armadura, não podemos correr as corridas "úteis" (como quebrar códigos ou simular novos medicamentos). O artigo argumenta que a Correção de Erros é a fronteira final antes que os computadores quânticos possam realmente vencer os clássicos em problemas do mundo real.

Resumo: Onde Estamos?

O artigo conclui que a corrida é um ** cabo-de-guerra**.

1. Computadores quânticos dão um grande salto à frente.
2. Computadores clássicos ficam mais inteligentes, encontram atalhos e alcançam (ou ultrapassam).
3. Computadores quânticos constroem hardware melhor e tentam novamente.

Agora mesmo, estamos na fronteira. Vimos computadores quânticos vencerem em quebra-cabeças específicos e inúteis, mas computadores clássicos encontraram maneiras de vencê-los em quase todos eles. O artigo sugere que, para os computadores quânticos vencerem uma corrida útil, eles devem primeiro dominar a arte da Correção de Erros. Até lá, a liderança continuará mudando de mãos.

Resumo técnico

Título: Uma Breve História da Vantagem Computacional Quântica versus Clássica
Autores: Ryan LaRose
Fonte: Quantum (Aceito em 14 de maio de 2026)

Enunciado do Problema

O artigo aborda o cenário em evolução da "vantagem computacional quântica" (também denominada supremacia quântica ou computação além da clássica). O problema central é definir e rastrear a fronteira móvel entre o que é computacionalmente viável para computadores clássicos versus computadores quânticos. Os autores definem vantagem computacional especificamente como uma redução no tempo de solução para um problema dado, independentemente da utilidade prática do problema. A revisão visa catalogar todas as alegações experimentais de vantagem quântica até a data, juntamente com os subsequentes desafios clássicos, refutações e desenvolvimentos teóricos que alteraram o status dessas alegações.

Metodologia

O artigo emprega uma metodologia de revisão abrangente, sintetizando dados históricos da física experimental, ciência da computação e teoria da complexidade.

1. Catalogação Cronológica: Os autores compilam uma linha do tempo de todos os experimentos que alegam vantagem quântica, categorizando-os por tipo de problema: Amostragem de Circuitos Aleatórios (RCS), Amostragem de Bosons Gaussianos (GBS) e Simulação Quântica (QSim).
2. Classificação de Status: Cada experimento recebe um status baseado na literatura subsequente:
   • Não Refutado: Nenhum algoritmo clássico simulou o experimento mais rápido até o momento.
   • Desafiado: Algoritmos clássicos melhoraram os tempos de simulação ou questionaram aspectos específicos do experimento.
   • Levemente Refutado: Existe um algoritmo clássico que provavelmente poderia simular o experimento em hardware clássico de futuro próximo.
   • Refutado: Um computador clássico simulou o experimento com sucesso mais rápido do que o dispositivo quântico.
3. Análise Teórica: A revisão examina a vantagem teórica em domínios específicos (otimização aproximada, sistemas de recomendação, química quântica) para destacar como a "dequantização" (o desenvolvimento de algoritmos clássicos inspirados em algoritmos quânticos) pode erodir acelerações teóricas.
4. Revisão de Correção de Erros: O artigo traça a história dos experimentos de correção de erros quânticos (QEC), identificando-os como a necessária "última fronteira" para alcançar vantagem em algoritmos como o de Shor, que exigem tolerância a falhas.

Principais Contribuições

• Tabela Abrangente de Status: O artigo fornece a Tabela 1, uma lista cronológica de todas as alegações de vantagem quântica (desde o Sycamore da Google em 2019 até a simulação da D-Wave em 2024) e sua posição atual em relação à refutação clássica.
• Narrativa Detalhada dos Desafios: Documenta a "corrida armamentista" entre experimentos quânticos e simulação clássica. Contribuições notáveis incluem o rastreamento de otimizações na contração de redes tensoriais (por exemplo, algoritmos "big head", partição de hipergrafos) e estratégias de exploração de ruído que reduziram os tempos de execução clássicos estimados de milhares de anos para horas ou segundos para experimentos específicos.
• Clarificação de Métricas: A revisão analisa criticamente a fidelidade do Benchmark de Entropia Cruzada (XEB), discutindo brechas onde algoritmos clássicos podem "falsificar" altos valores de XEB sem simular o circuito completo, e distinguindo entre refutações fracas e fortes.
• Dequantização Teórica: O artigo detalha como vantagens teóricas na otimização Max-E3LIN2 e em sistemas de recomendação foram perdidas quando algoritmos clássicos (por exemplo, de Barak et al. e Ewin Tang) igualaram ou superaram o desempenho quântico sob suposições de entrada semelhantes.
• Progresso em QEC: A Tabela 2 e a Seção 4 resumem o rápido progresso dos experimentos de correção de erros, notando a transição de códigos de repetição simples para códigos de superfície com distâncias de até 7, e o marco recente do experimento da Google em 2024, onde as taxas de erro lógico caíram abaixo do limiar da taxa de erro físico.

Resultados

• Volatilidade Experimental: A revisão constata que quase todas as principais alegações experimentais de vantagem quântica enfrentaram desafios significativos.
  • RCS da Google (2019, 53 qubits): Alegou inicialmente um tempo de execução clássico de 10.000 anos. Isso foi desafiado por otimizações de redes tensoriais e, eventualmente, fortemente refutado em 2024 (Zhao et al.) usando 1.432 GPUs para simular o experimento em 86,4 segundos.
  • GBS do USTC (Jiuzhang 1.0, 2.0, 3.0): Alegações de vantagem foram levemente refutadas por Oh et al. (2023), que usaram redes tensoriais para simular esses experimentos significativamente mais rápido do que os dispositivos quânticos, embora os experimentos permaneçam não refutados no sentido "forte" para as maiores instâncias.
  • QSim da IBM (2023): Uma alegação de vantagem na simulação do modelo de Ising com campo transversal foi refutada em semanas por múltiplas abordagens clássicas (redes tensoriais, propagação de crença, teoria de perturbação de Clifford) executadas em laptops ou GPUs únicas.
  • D-Wave (2024): Uma alegação recente de vantagem em simulação quântica permanece não refutada no momento da redação, embora os autores notem que é provavelmente um alvo para futuros desafios clássicos.
• Mudanças Teóricas: O artigo demonstra que a vantagem teórica não é estática. Algoritmos para sistemas de recomendação e otimização aproximada (QAOA) viram suas vantagens quânticas erodidas por algoritmos clássicos "dequantizados" que utilizam estruturas de dados ou técnicas de aproximação semelhantes.
• Marcos de Correção de Erros: Embora a computação quântica tolerante a falhas ainda não seja uma realidade, a revisão destaca que os qubits lógicos estão agora alcançando tempos de vida mais longos do que seus componentes físicos e que as taxas de erro estão se aproximando do limiar necessário para tolerância a falhas escalável.

Significado e Alegações

O artigo alega que a história da vantagem quântica é um alvo dinâmico e em movimento, e não uma conquista estática.

• Alvo em Movimento: Os autores enfatizam que a vantagem computacional é definida em relação aos melhores conhecidos algoritmos e hardware clássicos em um momento específico. À medida que os algoritmos clássicos melhoram (muitas vezes inspirados por insights quânticos), a fronteira da vantagem retorna aos computadores clássicos.
• Crise de Verificação: Uma parte significativa do artigo destaca a dificuldade de verificar a vantagem quântica. Muitos experimentos atuais (como RCS) são classicamente difíceis de verificar, criando um paradoxo onde a alegação de vantagem depende de computações clássicas que são, em si mesmas, intratáveis. O artigo aponta para "amostragem de circuitos picados" e "Amostragem de Código Oculto" como direções futuras propostas para vantagem verificável de forma eficiente.
• O Papel da Correção de Erros: A revisão postula que, para algoritmos com acelerações exponenciais comprovadas (como o algoritmo de Shor), a "última fronteira" não é apenas a contagem de qubits, mas a correção de erros quânticos. Sem tolerância a falhas, a sobrecarga da correção de erros pode negar qualquer aceleração teórica.
• Perspectiva Moderada: Os autores concluem que, embora a vantagem quântica seja provável para problemas específicos, o campo está atualmente na "fronteira" entre a dominância quântica e clássica. Eles alertam contra assumir uma vantagem permanente, notando que o status provavelmente continuará a mudar à medida que as tecnologias clássica e quântica evoluem. O artigo serve como um registro histórico para impulsionar pesquisadores em direção a novas formulações de problemas que sejam classicamente difíceis, quanticamente fáceis, verificáveis de forma eficiente e cientificamente úteis.