Um conhecido problema computacional busca encontrar a rota mais eficiente para um caixeiro viajante visitar clientes em várias cidades. Aparentemente simples, é surpreendentemente complexo e muito estudado, com implicações em campos tão amplos como manufatura e controle de tráfego aéreo.

Pesquisadores da University of Central Florida e da Boston University desenvolveram uma nova abordagem para resolver esses difíceis problemas computacionais mais rapidamente. Conforme relatado em 12 de maio em Nature Communications , eles descobriram uma maneira de aplicar a mecânica estatística, um ramo da física, para criar algoritmos mais eficientes que podem ser executados em computadores tradicionais ou um novo tipo de máquina computacional quântica, disse o professor Eduardo Mucciolo, presidente do Departamento de Física da Faculdade de Ciências da UCF.

A mecânica estatística foi desenvolvida para estudar sólidos, gases e líquidos em escalas macroscópicas, mas agora é usado para descrever uma variedade de estados complexos da matéria, do magnetismo à supercondutividade. Métodos derivados da mecânica estatística também foram aplicados para entender os padrões de tráfego, o comportamento das redes de neurônios, avalanches de areia e flutuações do mercado de ações.

Já existem algoritmos de sucesso baseados em mecânica estatística que são usados ​​para resolver problemas computacionais. Esses algoritmos mapeiam problemas em um modelo de variáveis ​​binárias nos nós de um gráfico, e a solução é codificada na configuração do modelo com menor energia. Ao construir o modelo em hardware ou simulação de computador, os pesquisadores podem resfriar o sistema até que ele atinja sua energia mais baixa, revelando a solução.

"O problema com esta abordagem é que muitas vezes é necessário passar por transições de fase semelhantes às encontradas ao passar de uma fase líquida para uma fase de vidro, onde existem muitas configurações concorrentes com baixa energia, "Mucciolo disse." Essas transições de fase tornam o processo de resfriamento lento, tornando o método inútil. "

Mucciolo e seus colegas físicos Claudio Chamon e Andrei Ruckenstein da BU superaram esse obstáculo mapeando o problema computacional original em um modelo estatístico elegante sem transições de fase, que eles chamaram de modelo de vértice. O modelo é definido em uma rede bidimensional e cada vértice corresponde a uma porta lógica reversível conectada a quatro vizinhos. Os dados de entrada e saída ficam nos limites da rede. O uso de portas lógicas reversíveis e a regularidade da rede foram ingredientes cruciais para evitar o obstáculo de transição de fase, Disse Mucciolo.

"Nosso método basicamente executa as coisas ao contrário, para que possamos resolver esses problemas muito difíceis, "Mucciolo disse." Atribuímos a cada uma dessas portas lógicas uma energia. Nós o configuramos de forma que toda vez que essas portas lógicas forem satisfeitas, a energia é muito baixa - portanto, quando tudo estiver satisfeito, a energia geral do sistema deve ser muito baixa. "

Chamon, um professor de física na BU e o líder da equipe, disse que a pesquisa representa uma nova forma de pensar sobre o problema.

"Este modelo não exibe transição de fase termodinâmica em massa, então uma das obstruções para se chegar às soluções presentes nos modelos anteriores foi eliminada, " ele disse.

O modelo de vértice pode ajudar a resolver problemas complexos de aprendizado de máquina, otimização de circuito, e outros grandes desafios computacionais. Os pesquisadores também estão explorando se o modelo pode ser aplicado à fatoração de semi-primos, números que são o produto de dois números primos. A dificuldade de realizar esta operação com semi-primos muito grandes é a base da criptografia moderna e ofereceu uma base lógica para a criação de computadores quânticos em grande escala.

Além disso, o modelo pode ser generalizado para adicionar outro caminho para a solução de problemas computacionais clássicos complexos, aproveitando o paralelismo da mecânica quântica - o fato de que, de acordo com a mecânica quântica, um sistema pode estar em vários estados clássicos ao mesmo tempo.

"Nosso artigo também apresenta uma estrutura natural para a programação de dispositivos computacionais para fins especiais, como máquinas D-Wave Systems, que usam a mecânica quântica para acelerar o tempo de solução de problemas computacionais clássicos, "disse Ruckenstein.

Zhi-Cheng Yang, um estudante de pós-graduação em física na BU, também é co-autor do artigo. As universidades solicitaram uma patente sobre aspectos do modelo de vértice.