Prova mostra limite quântico: encontrar a saída não revela o caminho
Em árvores soldadas, qualquer algoritmo quântico precisa de tempo exponencial para reconstruir uma rota fiável.
Um computador quântico consegue encontrar a saída de um labirinto matemático muito mais depressa do que um computador clássico. Uma nova prova mostra que reconstruir o caminho continua a exigir trabalho exponencial no modelo estudado.
O problema usa árvores binárias soldadas: duas estruturas ramificadas ligadas por uma região central irregular. Uma caminhada quântica explora vários percursos como uma onda e usa interferência para concentrar probabilidade na saída.
Encontrar não é explicar por onde se passou
O algoritmo que localiza a saída não conserva automaticamente um registo clássico das ligações visitadas. David Miloschewsky e Supartha Podder provaram que qualquer algoritmo quântico que produza uma rota fiável terá de gastar tempo exponencial.
A prova acompanha a informação aprendida, mantida em várias possibilidades e depois apagada. As secções exploradas separadamente raramente se encontram no enorme centro do grafo, impedindo a montagem eficiente de um percurso completo.
Um limite dentro de um modelo
O resultado remove duas restrições de uma prova de 2023. Outro grupo publicou uma demonstração independente cinco dias depois; as equipas procuram agora o limite quantitativo ótimo.
A conclusão não diz que computadores quânticos são lentos em geral. Identifica uma separação concreta entre obter uma resposta e fornecer a estrutura que a justifica, dentro do modelo de árvores soldadas.