Os computadores quânticos, utilizando qubits versáteis, estão na vanguarda da solução de problemas complexos de otimização, como o dilema do caixeiro viajante, tradicionalmente atormentado pela ineficiência computacional. Através de análises matemáticas rigorosas, os investigadores demonstraram que a computação quântica pode transformar fundamentalmente a resolução de problemas, oferecendo um aumento polinomial mais eficiente no tempo de computação em comparação com os métodos clássicos e produzindo soluções superiores.
O problema do caixeiro viajante é considerado um excelente exemplo de problema de otimização combinatória. Agora, uma equipe de Berlim liderada pelo físico teórico Prof. Jens Eisert da Freie Universität Berlin e HZB mostrou que uma certa classe de tais problemas pode realmente ser resolvida melhor e muito mais rápido com computadores quânticos do que com métodos convencionais.
Os computadores quânticos usam os chamados qubits, que não são zero nem um como nos circuitos lógicos convencionais, mas podem assumir qualquer valor intermediário. Esses qubits são realizados por átomos altamente resfriados, íons ou circuitos supercondutores, e ainda é fisicamente muito complexo construir um computador quântico com muitos qubits. No entanto, métodos matemáticos já podem ser usados para explorar o que os computadores quânticos tolerantes a falhas poderão alcançar no futuro.
“Existem muitos mitos sobre isso e, às vezes, uma certa quantidade de ar quente e exagero. Mas abordamos o assunto com rigor, utilizando métodos matemáticos, e entregamos resultados sólidos sobre o assunto. Acima de tudo, esclarecemos em que sentido pode haver alguma vantagem”, diz o Prof. Jens Eisert, que lidera um grupo de pesquisa conjunto na Freie Universität Berlin e no Helmholtz-Zentrum Berlin.
O problema do caixeiro viajante é um clássico da matemática. Um viajante deve visitar N cidades pelo caminho mais curto e retornar ao ponto de partida. À medida que o número N aumenta, o número de rotas possíveis explode. Este problema pode então ser resolvido usando métodos de aproximação. Os computadores quânticos poderiam fornecer soluções significativamente melhores e mais rapidamente. Crédito: HZB
Resolvendo Problemas Complexos
O conhecido problema do caixeiro-viajante serve como um excelente exemplo: um viajante tem que visitar várias cidades e depois retornar à sua cidade natal. Qual é o caminho mais curto? Embora este problema seja fácil de entender, torna-se cada vez mais complexo à medida que o número de cidades aumenta e o tempo de cálculo explode.
O problema do caixeiro viajante representa um conjunto de problemas de otimização de enorme importância económica, quer envolvam redes ferroviárias, logística ou otimização de recursos. Soluções suficientemente boas podem ser encontradas usando métodos de aproximação.
O presente trabalho (seta) mostra que uma certa parte dos problemas combinatórios pode ser resolvida muito melhor com computadores quânticos, possivelmente até com exatidão. Crédito: HZB/Eisert
Soluções e avanços quânticos
A equipe liderada por Jens Eisert e seu colega Jean-Pierre Seifert usou agora métodos puramente analíticos para avaliar como um computador quântico com qubits poderia resolver esta classe de problemas. Um experimento mental clássico com caneta e papel e muita experiência.
“Simplesmente assumimos, independentemente da realização física, que existem qubits suficientes e analisamos as possibilidades de realizar operações computacionais com eles”, explica Vincent Ulitzsch, estudante de doutoramento na Universidade Técnica de Berlim. Ao fazê-lo, revelaram semelhanças com um problema bem conhecido na criptografia, ou seja, a encriptação de dados. “Percebemos que poderíamos usar o algoritmo Shor para resolver uma subclasse desses problemas de otimização”, diz Ulitzsch.
Isto significa que o tempo de computação não “explode” mais com o número de cidades (exponencial, 2N), mas só aumenta polinomialmente, ou seja, com Nx, onde x é uma constante. A solução obtida desta forma também é qualitativamente muito melhor que a solução aproximada usando o algoritmo convencional.
“Mostramos que para uma classe específica, mas muito importante e praticamente relevante de problemas de otimização combinatória, os computadores quânticos têm uma vantagem fundamental sobre os computadores clássicos para certas instâncias do problema”, diz Eisert.
Referência: “Uma vantagem quântica superpolinomial em princípio para aproximar problemas de otimização combinatória por meio da teoria de aprendizagem computacional” por Niklas Pirnay, Vincent Ulitzsch, Frederik Wilde, Jens Eisert e Jean-Pierre Seifert, 15 de março de 2024, Avanços da Ciência.
DOI: 10.1126/sciadv.adj5170
