Imagine que você visita um labirinto com alguns amigos. Você sai da saída logo depois de entrar e espera por horas antes que seus amigos apareçam. Naturalmente, eles perguntam sobre o caminho que você percorreu - com certeza você pode refazer seus passos e mostrar-lhes o caminho, certo?

Não é assim em um mundo governado pelas estranhas leis da física quântica. Vinte anos atrás, pesquisadores de computação quântica desenvolveram um algoritmo que aproveitava essas leis para atravessar um tipo específico de labirinto matemático muito mais rápido do que qualquer algoritmo executado em um computador clássico comum. Mas essa aceleração tem um custo: o algoritmo quântico rápido encontra a saída, mas não tem ideia de como chegou lá.

Os pesquisadores há muito se perguntam se esse trade-off é inevitável. É realmente impossível encontrar a saída rapidamente sem esquecer o caminho?

“É meio alucinante que você precise fazer essa pergunta”, disse Mateus Coudron, cientista da computação do Instituto Nacional de Padrões e Tecnologia em Gaithersburg, Maryland.

Em novembro passado, Coudron e dois colegas deram um grande passo para resolver esse problema de longa data: eles provou que nenhum algoritmo em uma classe ampla e natural de algoritmos quânticos rápidos pode encontrar um caminho através desse labirinto especial, chamado grafo de árvore soldada. Os resultados mostram que qualquer algoritmo hipotético de descoberta de caminho que não adivinhasse cegamente teria que perder temporariamente o controle da entrada para ter alguma chance de sucesso. Parece que o esquecimento é inevitável.

“Não há como eu ter imaginado que eles poderiam realmente provar isso”, disse Simon Apers, pesquisador de computação quântica do Centro Nacional de Pesquisa Científica do Instituto de Pesquisa em Fundamentos da Ciência da Computação em Paris, acrescentando que o resultado “é muito útil para ilustrar o que os algoritmos quânticos podem e não podem fazer”.

O impulso quântico

Os computadores quânticos devem seu poder em parte a um fenômeno conhecido como superposição, que efetivamente permite que eles explorem simultaneamente muitas opções que um computador clássico precisaria considerar individualmente. Mas é não tão simples como realizar vários cálculos de uma só vez para economizar tempo. Verificar o resultado de uma superposição de escolhas nunca revela uma superposição de resultados — em vez disso, você obtém apenas um dos resultados possíveis, cada um com uma probabilidade diferente. Os algoritmos quânticos dependem do fato de que as contribuições para essas probabilidades podem interferir umas nas outras como ondas na superfície de um lago, aumentando a probabilidade de obter a resposta certa e reduzindo a probabilidade de todos os outros resultados.

Como a interferência tem que funcionar da maneira certa, nem toda tarefa computacional é passível de uma aceleração quântica e, de fato, os pesquisadores estão ainda malhando onde os algoritmos quânticos podem ajudar, décadas depois que a computação quântica foi proposta pela primeira vez. Mas eles tiveram alguns sucessos notáveis. Em 1994, Peter Shor desenvolveu um algoritmo quântico para fatorar grandes números — uma tarefa cuja aparente dificuldade para computadores clássicos é a base de grande parte da criptografia moderna. O algoritmo de Shor poderia fatorar rapidamente números tão grandes que todos os algoritmos clássicos conhecidos seriam praticamente inúteis.

Em 1996, o cientista da computação Lov Grover encontrou um segundo exemplo potencialmente prático: um algoritmo quântico para um problema de pesquisa muito genérico, semelhante a encontrar um único item escondido dentro de uma das muitas caixas idênticas.

“Classicamente, o que você poderia fazer é apenas tentar aleatoriamente um e ver se é bom, e então tentar novamente e ver se é bom, e continuar tentando até encontrar um bom elemento”, disse Apers. Essa abordagem leva um tempo proporcional ao número de caixas. Multiplique esse número por 100 e a pesquisa será 100 vezes mais lenta.

Com um algoritmo quântico, você pode fazer melhor. Grover provou que, se você configurar uma superposição de todas as caixas, poderá explorar a interferência para garantir praticamente que o algoritmo selecionará a caixa certa no final. Todo o processo leva um tempo proporcional à raiz quadrada do número de caixas: aumentar esse número por um fator de 100 apenas aumenta o tempo de execução por um fator de 10.

O algoritmo de Grover era uma ilustração notavelmente simples do valor da superposição quântica, mas a aceleração alcançada era relativamente modesta — tarefas que estavam muito além do alcance dos melhores algoritmos clássicos também prejudicariam o algoritmo de Grover. O algoritmo de fatoração de Shor ofereceu um vislumbre de um abismo dramático entre as capacidades dos computadores quânticos e clássicos. Existia uma variante do problema de busca de Grover que era como fatoração — praticamente intratável para computadores clássicos, mas fácil para computadores quânticos?

No final da década de 1990, os pesquisadores começaram a explorar essa questão reformulando-a como uma questão sobre grafos — redes de pontos, ou nós, conectados por linhas, chamadas arestas. Qualquer problema de busca pode ser enquadrado na linguagem da teoria dos grafos, com um nó representando o ponto de partida, outro nó representando o destino e arestas representando as escolhas possíveis em cada etapa ao longo do caminho

O problema de Grover, por exemplo, corresponde a pesquisar um grafo no qual cada nó está conectado a todos os outros nós (porque você pode abrir caixas em qualquer ordem). Diferentes algoritmos clássicos para um determinado problema de busca equivalem a diferentes estratégias para explorar o grafo correspondente, um nó por vez, enquanto os algoritmos quânticos podem se mover ao longo de múltiplas arestas em superposição.

Ramificando-se

Em 2002, uma equipe de cientistas da computação finalmente identificado um problema de busca classicamente intratável que um algoritmo quântico poderia resolver facilmente. Eles começaram com um grafo simples chamado árvore, no qual cada nó brota duas arestas que levam a mais dois nós, que se dividem em mais dois ramos, e assim por diante. Começando de um único nó “raiz”, um grafo de árvore se ramifica várias vezes antes de terminar em uma camada final de nós chamada “folhas”. A equipe imaginou pegar duas árvores idênticas e “soldá-las”, posicionando-as com as folhas voltadas uma para a outra e, em seguida, usando um processo aleatório para conectar cada folha de uma árvore a duas folhas da outra. Eles então fizeram a seguinte pergunta: Começando em uma raiz do grafo de árvore soldada, você consegue encontrar o caminho para a outra?

Sem uma visão panorâmica do grafo, qualquer algoritmo clássico que tente resolver esse problema de busca ficará irremediavelmente perdido depois de atingir as camadas intermediárias do grafo — todas as arestas parecem idênticas e não há como distinguir aquelas que apontam para frente daquelas que levam para trás. Um algoritmo pode tropeçar no nó de saída acidentalmente, mas o tempo médio que ele gasta vagando cresce exponencialmente com o número de camadas na árvore.

Os autores do artigo de 2002 provaram que um algoritmo quântico simples – uma “caminhada quântica” que se espalha uniformemente pelo gráfico tomando muitos caminhos em superposição – pode encontrar o caminho para a saída muito mais rapidamente. Isso ocorre porque o layout simétrico do gráfico de árvore soldada leva à interferência entre os caminhos que concentram o fluxo na direção direta. O nó de saída é “como um ponto de foco do algoritmo”, disse Alexandre Belov, cientista da computação da Universidade da Letônia.

Há uma boa chance de que esse algoritmo de caminhada quântica converja na saída no tempo que é meramente proporcional ao número de camadas. Isso o torna exponencialmente mais rápido do que qualquer algoritmo clássico - uma aceleração comparável à do algoritmo de fatoração de Shor. Mas a interferência que causa a aceleração quântica também apaga todos os registros dos caminhos que o algoritmo percorre em seu caminho para a saída.

Os pesquisadores se perguntaram se havia alguma maneira de obter o melhor dos dois mundos – um algoritmo rápido que identifica um caminho da entrada à saída.

“Se for apenas a caminhada quântica básica que de alguma forma encontra a saída, isso não vai funcionar”, disse André Childs, um cientista da computação da Universidade de Maryland, College Park, co-autor do artigo de 2002 como estudante de pós-graduação e trabalhou com Coudron no novo resultado. “Mas talvez você possa apimentá-lo de alguma forma.”

Incrementando

Entre os primeiros a abordar o problema estava Ansis Rosmanis, um cientista da computação agora na Nagoya University Graduate School of Mathematics. Em um artigo de 2010, Rosmanis desenvolveu um classe de algoritmos que ele chamou de “caminhadas quânticas de cobras”, que complementam o algoritmo padrão de caminhada quântica com uma memória de onde estiveram.

À medida que o algoritmo de caminhada quântica padrão flui pelo gráfico, sua próxima etapa depende apenas de onde ele está atualmente - como ele chegou lá não importa. Nas caminhadas da cobra de Rosmanis, por outro lado, você precisa conhecer o passado para prever o futuro. Especificamente, a evolução da caminhada da cobra é determinada por “cobras”, sequências de nós adjacentes pelos quais a caminhada já passou. Existem muitas variedades de passeios de cobra, diferindo entre outros aspectos em como o comprimento dessas cobras muda ao longo do passeio.

Rosmanis mostrou que caminhadas quânticas de cobras usando superposições de várias cobras ainda podem exibir interferência útil, apesar de lembrar suas trajetórias, e que algumas caminhadas de cobras podem, em princípio, encontrar um caminho para a saída. Mas ele não conseguiu encontrar um algoritmo específico de caminhada de cobra que o fizesse tão rapidamente e também não conseguiu provar que tal algoritmo não existia. Caminhadas de cobra, ao que parecia, eram promissoras, mas escorregadias demais para definir. O trabalho de Rosmanis foi a última palavra no problema de localização de caminhos por quase uma década.

Então, em 2019, Coudron encontrou o gráfico de árvore soldada em um contexto diferente: ele e um colega provou que todos os algoritmos de caminhada quântica que encontram a saída carecem de uma propriedade universal entre os algoritmos que eram conhecidos por produzir acelerações quânticas exponenciais para outros problemas. O resultado não estava diretamente relacionado à descoberta de caminhos, mas Coudron começou a suspeitar que as técnicas matemáticas que lhe permitiram provar essa afirmação abrangente sobre as propriedades de todos os algoritmos de gráficos de árvores soldadas também poderiam ajudar a resolver a questão de saber se os passeios de cobra (ou outros algoritmos) poderiam encontrar um caminho. Depois de se mudar para Maryland no final daquele ano, ele iniciou uma colaboração com Childs, na esperança de resolver essa questão de forma decisiva.

Childs, Coudron e seu aluno de pós-graduação Amin Shiraz Gilani começou fazendo duas suposições para restringir o escopo do problema. Primeiro, eles decidiram ignorar algoritmos estranhos que tentariam se teletransportar para pontos aleatórios no gráfico na esperança de tropeçar na saída. Essa estratégia é como tentar vencer um videogame procurando uma falha para explorar - tecnicamente possível, talvez, mas contra o espírito do problema. Também é difícil imaginar que tal comportamento possa ser útil, já que as chances de cair no ponto certo tornam-se minúsculas em gráficos grandes. Ignorar os algoritmos que pulam aleatoriamente tornou mais fácil analisar os algoritmos restantes, que os autores apelidaram de algoritmos “genuínos” – incluindo os algoritmos de caminhada da cobra de Rosmanis e talvez outros que ninguém ainda havia descoberto.

A segunda suposição mais substantiva dos autores era que um algoritmo de descoberta de caminho rápido permaneceria "enraizado" - isto é, construiria um caminho para o nó de saída sem nunca perder o controle da entrada. Muitos passeios de cobra estão enraizados, mas é possível, em princípio, que um passeio de cobra não enraizado encontre um caminho para a saída - ele teria que se separar do nó de entrada e, em seguida, encontrar a entrada e a saída mais tarde.

Os três pesquisadores provaram que, para cada algoritmo quântico enraizado genuíno, eles poderiam criar um algoritmo clássico que imitaria seu comportamento observável. Como eles também puderam provar que nenhum algoritmo clássico poderia encontrar a saída rapidamente, isso foi suficiente para descartar essa ampla classe de possíveis algoritmos quânticos de localização de caminhos. Algoritmos genuínos simplesmente não conseguem reunir interferência suficiente para encontrar um caminho através do labirinto.

O caminho a seguir

O novo resultado não é necessariamente o fim da história. “Mesmo depois de estudar algoritmos quânticos por um bom tempo, eles continuam me surpreendendo,” Shelby Kimmel, um cientista da computação do Middlebury College, escreveu em um e-mail. Ainda pode haver um engenhoso algoritmo de descoberta de caminhos fora da classe que os pesquisadores consideraram, apenas esperando para ser descoberto.

Embora os algoritmos que não são genuínos pareçam extremamente improváveis ​​de funcionar, um algoritmo não enraizado talvez possa construir um caminho da entrada à saída começando de algum lugar no meio. “Talvez você possa configurá-lo de forma que a cobra entre e se solte, mas de alguma forma decida se esticar”, disse Childs. “Isso ainda não está descartado.”

Os pesquisadores ainda precisam encontrar aplicações práticas para a aceleração quântica exponencial que Childs e seus colegas descobriram há 20 anos, em parte porque depende da simetria especial do gráfico da árvore soldada, que é improvável que exista em qualquer rede do mundo real. Mas muitas vezes há tanto valor em entender o que os algoritmos quânticos não podem fazer. A descoberta de Shor de um algoritmo quântico rápido para fatoração de grandes números, que ameaça minar criptografia de última geração, destacou a necessidade de problemas que também são conhecidos por serem difíceis para algoritmos quânticos.

Um tipo de criptografia não vulnerável ao algoritmo de Shor baseia-se na suposição de que é difícil encontrar caminhos entre pontos em gráficos específicos. A evidência de que encontrar caminhos através de árvores soldadas é realmente difícil para algoritmos quânticos pode motivar os pesquisadores a desenvolver novos protocolos criptográficos baseados no gráfico de árvore soldada, embora eles não tenham tido sorte até agora.

“Talvez isso signifique que o tipo de estrutura que está neste problema simplesmente não é adequado para codificar problemas com os quais nos preocupamos”, disse Childs. “Ou talvez você só tenha que ver da maneira certa.”