Computadores quânticos podem resolver problemas de otimização combinatória mais facilmente do que métodos convencionais, mostra pesquisa
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 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.
O trabalho da equipe é publicado na revista Science Advances .
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, usando métodos matemáticos, e entregamos resultados sólidos sobre o assunto. pode haver alguma vantagem", diz o Prof. Eisert, que dirige um grupo de pesquisa conjunto na Freie Universität Berlin e no Helmholtz-Zentrum Berlin.
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.
A equipe liderada por 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 essa classe de problemas, um experimento mental clássico com caneta e papel e muita experiência.
“Nós 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, Ph.D. estudante da Universidade Técnica de Berlim.
Ao fazer isso, a equipe revelou semelhanças com um problema bem conhecido em criptografia, ou seja, a criptografia de dados.
“Percebemos que poderíamos usar o algoritmo Shor para resolver uma subclasse desses problemas de otimização”, diz Ulitzsch. Isso significa que o tempo de computação não “explode” mais com o número de cidades (exponencial, 2
N
), mas só aumenta polinomialmente, ou seja, com N
x
, 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.
