Resolvendo o “Problema do Caixeiro Viajante” através da Computação Quântica

Um problema algorítmico clássico no campo da ciência da computação conhecido como Problema do Caixeiro Viajante (TSP) é um exemplo principal de um problema de otimização combinatória.

O que exatamente é o TSP? Este clássico da matemática envolve encontrar a rota mais curta possível para visitar N cidades exatamente uma vez antes de retornar à cidade de origem. No entanto, à medida que o número de cidades aumenta, também aumentam as rotas possíveis e o tempo de computação para encontrar a solução ótima. Enquanto esse problema pode ser resolvido usando métodos de aproximação, os computadores quânticos poderiam fornecer soluções muito melhores e muito mais rapidamente.

É exatamente isso que o físico teórico Prof. Dr. Jens Eisert e sua equipe demonstraram: que tais problemas podem ser resolvidos de forma melhor e mais rápida com computadores quânticos.

A computação quântica utiliza hardware e algoritmos que aproveitam a mecânica quântica para resolver problemas complexos além do alcance dos convencionais, incluindo supercomputadores. Apesar de seu poder, os supercomputadores — computadores clássicos massivos com milhares de núcleos de CPU e GPU — são limitados pela dependência da tecnologia de transistores do século XX ao resolver problemas de alta complexidade.

É aqui que a física quântica entra. Em contraste com os computadores clássicos, que codificam informações em bits binários (0s e 1s), os computadores quânticos utilizam bits quânticos ou qubits para executar algoritmos quânticos multidimensionais.

Além disso, ao contrário dos computadores convencionais, que usam ventiladores para resfriamento, os computadores quânticos exigem que seus processadores quânticos sejam mantidos a temperaturas extremamente baixas para preservar seus estados quânticos. Isso é alcançado por meio de superfluidos super‑resfriados.

Supercondutores são materiais que exibem um efeito mecânico quântico crítico, permitindo que elétrons se movimentem através deles sem resistência. À medida que os elétrons passam, eles se emparelham para transportar carga através de barreiras. Quando dois supercondutores são colocados em lados opostos de um isolante, forma-se uma junção Josephson, que é usada para conduzir qubits supercondutores.

Um qubit é útil na importante tarefa de colocar sua informação quântica em um estado de superposição, uma combinação das possíveis configurações do qubit. Grupos de qubits em superposição são capazes de criar espaços computacionais complexos e multidimensionais onde problemas complexos podem ser representados.

Aqui, pelo emaranhamento de dois qubits, alterações em um podem impactar o outro diretamente, enquanto quando esses qubits emaranhados são colocados em um estado de superposição, obtemos inúmeras probabilidades. A computação em um computador quântico funciona preparando uma superposição de todos os estados computacionais possíveis e, por meio da interferência, as soluções são encontradas.

Claro, construir um computador quântico com muitos qubits é um procedimento muito complexo, embora vários métodos estejam sendo explorados quanto ao que tais computadores podem realizar.

De acordo com Eisert, que lidera um grupo de pesquisa conjunto no Helmholtz‑Zentrum Berlin (HZB), um centro de pesquisa de materiais energéticos, e na universidade pública Freie Universität Berlin:

“Existem muitos mitos sobre isso, e às vezes uma certa quantidade de exagero e hype. No entanto, abordamos a questão de forma rigorosa, usando métodos matemáticos, e entregamos resultados sólidos sobre o assunto. Acima de tudo, esclarecemos em que sentido pode haver quaisquer vantagens.”

O Problema Crítico do Caixeiro Viajante

Um problema de otimização, o TSP tem grande importância econômica na indústria de logística e cadeia de suprimentos. Ele se enquadra na categoria mais ampla de problemas de otimização combinatória, que também inclui agendamento de tarefas, alocação de recursos, otimização de portfólio e até dobramento de proteínas, todos críticos para vários setores.

Dada a importância social e econômica desses problemas, eles têm sido objeto de intensa pesquisa. Assim, encontrar a resposta para problemas como a cadeia de suprimentos mais eficiente e a rota de entrega mais barata tem um impacto positivo em nossas vidas diárias.

No entanto, otimizar as rotas de entrega para múltiplos destinos enquanto se consideram várias restrições, como congestionamento de tráfego, aumento dos custos operacionais, mudanças súbitas de rota, compromissos de negócios de última hora e solicitações de clientes, torna o TSP ainda mais desafiador de resolver. Apesar desses desafios, resolver o TSP é crucial para a entrega eficiente de mercadorias, o que garante um modelo de negócios viável.

Existem muitos benefícios em resolver esse problema, incluindo a redução da distância e das horas percorridas e a economia de combustível. Minimizar a distância percorrida pode ajudar a reduzir significativamente a pegada de carbono, o que se traduz em melhor qualidade do ar, desaceleração das mudanças climáticas e crescimento econômico. Além disso, resolver o TSP pode ajudar na entrega pontual de mercadorias e em reuniões pontuais com clientes, o que aprimora a experiência do cliente e os negócios de serviços de campo.

Como vimos, resolver o problema não apenas ajuda as empresas, mas esses benefícios também se estendem aos clientes, enriquecendo a experiência de todos os envolvidos.

Vários métodos podem ser usados para resolver o problema do TSP. Um desses métodos é a abordagem ‘Força Bruta’, que calcula todas as permutações possíveis para encontrar a rota mais curta. No método de ramificação e delimitação, o problema é dividido em várias séries de subproblemas, com a solução de cada etapa influenciando a solução encontrada nas etapas subsequentes.

Na programação dinâmica, o foco está em evitar cálculos redundantes. O algoritmo do Vizinho Mais Próximo, por sua vez, é um algoritmo de aproximação no qual você começa com o local de partida e então vai para o mais próximo. Uma vez que todas as cidades são cobertas, você retorna ao ponto de partida. Embora prático e relativamente rápido, esse método pode não fornecer sempre uma rota eficiente.

À medida que a tecnologia avança, o planejamento e a otimização de rotas podem ser feitos de forma muito mais eficaz. A Inteligência Artificial (IA), em particular, também pode ajudar a resolver o problema analisando rapidamente uma enorme quantidade de dados para auxiliar muitas empresas modernas a tomar decisões operacionais e estratégicas.

Os computadores quânticos também estão sendo investigados para resolver o problema; afinal, eles oferecem consideráveis acelerações computacionais em relação aos computadores clássicos. Há muito tempo se sugere que esses computadores podem realmente ajudar a melhorar as aproximações desses problemas.

Usando Técnicas de Computação Quântica para Resolver o TSP

Embora a computação quântica esteja despertando enorme interesse e fornecendo resultados promissores para certos problemas, a extensão dessa vantagem quântica permanece em grande parte inexplorada.

Assim, o estudo forneceu prova totalmente construtiva de que os computadores quânticos podem realmente superar os computadores convencionais na busca de aproximações para problemas de otimização combinatória.

O estudo mais recente, liderado por Eisert e seu colega Jean‑Pierre Seifert, utilizou apenas métodos analíticos para avaliar até que ponto um computador quântico com qubits pode resolver o problema do TSP.

“Assumimos simplesmente, independentemente da realização física, que há qubits suficientes e analisamos as possibilidades de executar operações computacionais com eles”, o que revela semelhança com um problema comum em criptografia, ou seja, a criptografia de dados, explicou Vincent Ulitzsch, estudante de doutorado na Universidade Técnica de Berlim.

Então, a equipe usou o algoritmo de Shor, um algoritmo quântico, para encontrar os fatores primos de um inteiro e resolver uma subclasse desses problemas de otimização. Com isso, o tempo de computação não explodirá mais à medida que o número de cidades aumenta. Ele aumentará apenas de forma polinomial, ou seja, com Nx, onde x é uma constante. Dessa forma, a solução obtida é também qualitativamente muito melhor do que a derivada da solução aproximada usando o algoritmo convencional.

Ao usar conceitos criptográficos e teoria de aprendizado computacional, o estudo fornece “prova totalmente construtiva de que os computadores quânticos apresentam uma vantagem superpolinomial sobre os computadores clássicos na aproximação de problemas de otimização combinatória”.

O estudo ainda observou que a equipe de pesquisa fez progressos significativos na importante questão de quais potenciais os computadores quânticos podem oferecer para aproximar a solução de problemas de otimização combinatória, que têm impactos sociais e econômicos substanciais.

O estudo foi financiado pela Einstein Research Unit, pelo Berlin Mathematics Research Center (MATH+ Cluster of Excellence), pelo BMBF (Hybrid), pelo BMWK (EniQmA), pelo Munich Quantum Valley e pela DFG. O Ministério Federal da Educação e Pesquisa da Alemanha também forneceu apoio financeiro.

Explorando o Potencial da Computação Quântica

Embora seja uma grande conquista, esta não foi a primeira vez que a computação quântica foi usada para resolver o problema do caixeiro viajante. Houve muitas instâncias de entusiastas e pesquisadores investigando a solução do problema utilizando a computação quântica.

Em dezembro de 2022, um artigo propôs um algoritmo quântico para o TSP baseado na Busca Adaptativa de Grover (GAS). Dentro da estrutura GAS, há pelo menos duas dificuldades fundamentais — as soluções podem não ser viáveis, e o número de qubits dos computadores quânticos atuais é muito limitado e não pode atender aos requisitos mínimos, restringindo a aplicação de algoritmos quânticos para problemas de otimização combinatória.

Assim, o artigo aprimorou o oráculo de Detecção de Ciclo Hamiltoniano (HCD), que pode remover soluções impraticáveis automaticamente durante a execução do algoritmo. Eles também projetaram uma estratégia de “registro âncora” para economizar o uso de qubits, considerando plenamente o requisito de reversibilidade da computação quântica e superando a dificuldade de que os qubits usados não sejam simplesmente sobrescritos ou liberados. Isso permitiu que o estudo exigisse apenas 31 qubits, e a solução teve uma taxa de sucesso de 86,71%.

Em 2019, o autodeclarado conhecedor de física Joseph Cammidge escreveu sobre o uso de um processador quântico de recozimento, que lhe permitiu resolver o problema do caixeiro viajante para sete cidades e tem potencial teórico de resolver para nove cidades uma vez que as limitações tecnológicas sejam eliminadas.

Um novo método de computação, o recozimento quântico, tem demonstrado potencial para resolver problemas de otimização mais rapidamente que técnicas clássicas. Sua teoria implica que os qubits alcançarão um estado de baixa energia ótimo quando super‑resfriados.

No entanto, em 2021, um estudo financiado pela Supply Chain Digital & Data Science, Johnson & Johnson descobriu que o recozedor quântico pode lidar apenas com um tamanho de problema de 8 nós ou menos, e seu desempenho é inferior tanto em tempo quanto em precisão comparado ao solucionador clássico.

O uso da computação quântica para resolver o problema do TSP vem ocorrendo há algum tempo. Há mais de duas décadas, em 2001, um estudo começou a buscar um algoritmo quântico para resolver o problema.

No artigo, Buckley Hopper, da Universidade do Alabama, analisou os algoritmos quânticos de Grover e Shor. Ele observou que o algoritmo de Grover fornece apenas uma melhoria de raiz quadrada, implicando que não pode tornar um problema classicamente intratável tratável em um computador quântico. Quanto ao algoritmo de Shor, Hopper observou que, embora possa converter um problema de fatoração primo presumivelmente intratável em um tratável na máquina quântica, ele é adequado apenas para um tipo muito específico de problema.

No geral, Hopper “não encontrou um resultado satisfatório para um algoritmo que compute soluções aproximadas para o problema do caixeiro viajante”.

Alguns anos depois, o Institute of Electrical and Electronics Engineers (IEEE) apresentou um novo algoritmo para resolver o problema, inspirado tanto em algoritmos genéticos quanto em computação quântica. O IEEE constatou que os resultados da aplicação do algoritmo proposto em algumas instâncias do Problema do Caixeiro Viajante são consideravelmente melhores do que os fornecidos pelos algoritmos genéticos padrão.

Clique aqui para saber sobre o estado atual da computação quântica.

Empresas que Trabalham com Computação Quântica

Agora, vamos dar uma olhada em alguns nomes que estão trabalhando na pesquisa e desenvolvimento da computação quântica:

#1. IBM

A International Business Machines Corporation (IBM ) está envolvida em uma ampla gama de setores, incluindo IA, serviços de nuvem, TI, financiamento de clientes e financiamento comercial. O gigante tecnológico também está envolvido em computação quântica por meio de sua IBM Quantum Platform, que oferece acesso público e premium aos seus serviços de computação quântica baseados na nuvem. Estes incluem um conjunto de processadores quânticos protótipos da IBM, tutoriais sobre computação quântica e um livro didático interativo.

Mais recentemente, cientistas da IBM declararam que estão um passo mais perto de superar um obstáculo que desbloqueia o potencial revolucionário dos computadores quânticos. Para isso, eles introduziram um novo código de correção de erros quânticos, que dizem ser cerca de dez vezes mais eficiente que os métodos anteriores.

No final do ano passado, a empresa também lançou o computador quântico chamado Condor, com 1.121 qubits supercondutores dispostos em padrão de favo de mel. A IBM também revelou o IBM Quantum System Two, seu primeiro computador quântico modular e arquitetura de supercomputação centrada em quantum, que é escalável e, portanto, pode ser atualizado com chips que serão lançados nos próximos cinco anos.

Com uma capitalização de mercado de US$ 175 bilhões, as ações da IBM estão sendo negociadas a US$ 190,86, alta de 16,66% no ano (YTD). A IBM registrou receita (TTM) de US$ 61,86 bilhões, com EPS (TTM) de 8,03, P/E (TTM) de 23,76 e ROE (TTM) de 33,36%. A empresa paga um dividend yield de 3,48%.

#2. D-Wave Systems

Esta empresa de computação quântica desenvolve e entrega sistemas, softwares e serviços relacionados. Seus produtos incluem The Leap e The Advantage, e fornece aplicações quânticas para agendamento, logística, descoberta de medicamentos, processos de fabricação e mais.

No início deste mês, a D-Wave afirmou que máquinas quânticas agora podem resolver problemas com aplicações do mundo real mais rapidamente que qualquer computador comum. No início deste ano, a empresa anunciou um computador quântico com 1.200 qubits, 10.000 acopladores e um tempo de solução 20 vezes mais rápido em problemas de otimização difíceis.

As ações da empresa estão atualmente sendo negociadas a US$ 1,86, alta de 138,6% no ano (YTD), com uma capitalização de mercado de US$ 267 milhões. Ela reportou US$ 8,247 milhões em vendas (TTM), EPS (TTM) de -0,66 e P/E (TTM) de -3,19, e anunciou um crescimento de mais de 20% nas vendas tanto no seu Q4 quanto nos resultados de final de 2023, enquanto as reservas aumentaram 34% e 89%, respectivamente.

Curiosamente, o CEO da empresa, Dr. Alan Baratz, declarou o impulso da firma, citando a parceria estratégica de vários anos com a Zapata AI, a introdução do protótipo Advantage2 com mais de 1.200 qubits, joint ventures com a NEC Australia e a Deloitte Canada, e a nomeação do ex‑secretário de Segurança Interna Kirstjen Nielsen para o conselho de diretores.

Conclusão

Espera‑se que o mercado de computação quântica alcance US$ 6,5 bilhões em 2028, e seu potencial para resolver o Problema do Caixeiro Viajante (TSP) tem ramificações para várias indústrias, como manufatura, logística, gerenciamento da cadeia de suprimentos, comércio eletrônico, transporte e pesquisa. Afinal, pode resultar em benefícios substanciais, notavelmente aumentando a produtividade, reduzindo despesas e estimulando a inovação em diversos setores.

Clique aqui para a lista das cinco melhores empresas de computação quântica.