Os melhores computadores digitais de hoje ainda lutam para resolver, em um prazo prático, uma certa classe de problema:problemas de otimização combinatória, ou aqueles que envolvem vasculhar grandes conjuntos de possibilidades para encontrar a melhor solução. Os computadores quânticos têm potencial para enfrentar esses problemas, mas aumentar o número de bits quânticos nesses sistemas continua sendo um obstáculo.

Agora, Pesquisadores do MIT Lincoln Laboratory demonstraram uma alternativa, forma analógica para acelerar a computação desses problemas. "Nosso computador funciona 'computando com a física' e usa a própria natureza para ajudar a resolver esses difíceis problemas de otimização, "diz Jeffrey Chou, co-autor principal de um artigo sobre este trabalho publicado na revista Nature's Relatórios Científicos . "É feito de componentes eletrônicos padrão, permitindo-nos dimensionar nosso computador de forma rápida e barata, aproveitando a indústria de microchip existente. "

Talvez o problema de otimização combinatória mais conhecido seja o do caixeiro viajante. O problema pede para encontrar o caminho mais curto que um vendedor pode seguir por várias cidades, começando e terminando no mesmo. Pode parecer simples com apenas algumas cidades, mas o problema se torna exponencialmente difícil de resolver conforme o número de cidades aumenta, atolando até mesmo os melhores supercomputadores. Ainda assim, os problemas de otimização precisam ser resolvidos no mundo real diariamente; as soluções são usadas para agendar turnos, minimizar o risco financeiro, descobrir drogas, planejar embarques, reduzir a interferência em redes sem fio, e muito mais.

"Já se sabe há muito tempo que os computadores digitais são fundamentalmente ruins para resolver esses tipos de problemas, "diz Suraj Bramhavar, também um co-autor principal. "Muitos dos algoritmos que foram concebidos para encontrar soluções precisam trocar a qualidade da solução por tempo. Encontrar a solução ideal absoluta acaba levando um tempo excessivamente longo quando o tamanho do problema aumenta." Encontrar soluções melhores e fazer isso em muito menos tempo pode economizar bilhões de dólares para as indústrias. Assim, pesquisadores têm buscado novas maneiras de construir sistemas projetados especificamente para otimização.

Encontrando o ritmo

A natureza gosta de otimizar energia, ou atingir metas da maneira mais eficiente e distribuída. Este princípio pode ser testemunhado na sincronia da natureza, como células cardíacas batendo juntas ou cardumes de peixes se movendo como um só. De forma similar, se você definir dois relógios de pêndulo na mesma superfície, não importa quando o pêndulo individual é colocado em movimento, eles eventualmente serão embalados em um ritmo sincronizado, alcançando seu ápice ao mesmo tempo, mas movendo-se em direções opostas (ou fora de fase). Este fenômeno foi observado pela primeira vez em 1665 pelo cientista holandês Christiaan Huygens. Esses relógios são um exemplo de osciladores acoplados, configurado de tal forma que a energia pode ser transferida entre eles.

"Basicamente, construímos um sistema eletrônico, versão programável deste [configuração do relógio] usando osciladores não lineares acoplados, "Chou diz, mostrando um vídeo do YouTube de metrônomos exibindo um fenômeno semelhante. "A ideia é que, se você configurar um sistema que codifique o cenário de energia do seu problema, então o sistema tentará naturalmente minimizar a energia sincronizando, e ao fazer isso, decidirá sobre a melhor solução. Podemos então ler esta solução. "

O protótipo do laboratório é um tipo de máquina Ising, um computador baseado em um modelo em física que descreve uma rede de ímãs, cada um dos quais tem uma orientação magnética de "spin" que pode apontar apenas para cima ou para baixo. A orientação final de cada giro depende de sua interação com todos os outros giros. As interações individuais spin-to-spin são definidas com um peso de acoplamento específico, o que denota a força de sua conexão. O objetivo de uma máquina Ising é encontrar, dada uma rede de força de acoplamento específica, a configuração correta de cada giro, Para cima ou para baixo, que minimiza a energia geral do sistema.

Mas como uma máquina Ising resolve um problema de otimização? Acontece que os problemas de otimização podem ser mapeados diretamente no modelo de Ising, de forma que um conjunto de spins com certos pesos de acoplamento pode representar cada cidade e as distâncias entre elas no problema do caixeiro viajante. Assim, encontrar a configuração de spins de menor energia no modelo de Ising se traduz diretamente na solução para a rota mais rápida do vendedor. Contudo, resolver esse problema verificando individualmente cada uma das configurações possíveis torna-se proibitivamente difícil quando os problemas crescem até mesmo para tamanhos modestos.

Nos últimos anos, tem havido esforços para construir máquinas quânticas que mapeiam para o modelo de Ising, o mais notável deles é um da empresa canadense D-Wave Systems. Essas máquinas podem oferecer uma maneira eficiente de pesquisar o grande espaço de solução e encontrar a resposta correta, embora operem em temperaturas criogênicas.

O sistema do laboratório executa uma pesquisa semelhante, mas faz isso usando osciladores eletrônicos simples. Cada oscilador representa um spin no modelo de Ising, e da mesma forma assume uma fase binarizada, onde osciladores que são sincronizados, ou em fase, representam a configuração "spin up" e aqueles que estão fora de fase representam a configuração "spin down". Para configurar o sistema para resolver um problema de otimização, o problema é primeiro mapeado para o modelo de Ising, traduzindo-o em pesos de acoplamento programáveis ​​conectando cada oscilador.

Com os pesos de acoplamento programados, os osciladores podem funcionar, como o braço do pêndulo de cada relógio sendo lançado. O sistema então relaxa naturalmente até seu estado geral de energia mínima. Lendo eletronicamente a fase final de cada oscilador, representando "spin up" ou "spin down, "apresenta a resposta à pergunta feita. Quando o sistema funcionou com mais de 2, 000 problemas de otimização aleatória, chegou à solução correta 98 ​​por cento das vezes.

Anteriormente, pesquisadores da Universidade de Stanford demonstraram uma máquina Ising que usa lasers e eletrônicos para resolver problemas de otimização. Esse trabalho revelou o potencial para uma aceleração significativa da computação digital, embora, de acordo com Chou, o sistema pode ser difícil e caro de dimensionar para tamanhos maiores. O objetivo de encontrar uma alternativa mais simples deu início às pesquisas do laboratório.

Aumentando a escala

O circuito oscilador individual que a equipe usou em sua demonstração é semelhante ao circuito encontrado dentro de telefones celulares ou roteadores wi-fi. Uma adição que eles fizeram é uma arquitetura de barra transversal que permite que todos os osciladores no circuito sejam diretamente acoplados uns aos outros. "Encontramos uma arquitetura que é escalonável para fabricar e pode permitir conectividade total a milhares de osciladores, "Chou diz. Um sistema totalmente conectado permite que ele seja facilmente mapeado para uma ampla variedade de problemas de otimização.

"Este trabalho do Laboratório Lincoln faz uso inovador de uma arquitetura de barra transversal na construção de uma máquina Ising analógico-eletrônica, "diz Peter McMahon, um professor assistente de física aplicada e engenharia na Cornell University que não esteve envolvido nesta pesquisa. "Será interessante ver como os desenvolvimentos futuros desta arquitetura e plataforma irão se comportar."

O protótipo da máquina Ising do laboratório usa quatro osciladores. A equipe agora está elaborando um plano para dimensionar o protótipo para um número maior de osciladores, ou "nós, "e fabricá-lo em uma placa de circuito impresso." Se conseguirmos, dizer, 500 nós, há uma chance de começarmos a competir com os computadores existentes, e em 1, 000 nós, podemos ser capazes de vencê-los, "Bramhavar diz.

A equipe vê um caminho claro para a expansão porque a tecnologia é baseada em componentes eletrônicos padrão. Também é extremamente barato. Todas as peças de seu protótipo podem ser encontradas em um típico laboratório de engenharia elétrica de graduação e foram compradas online por cerca de US $ 20.

"O que me emociona é a simplicidade, "Bramhavar acrescenta." Espera-se que os computadores quânticos demonstrem um desempenho incrível, mas os desafios científicos e de engenharia necessários para aumentá-los são bastante difíceis. Demonstrando até mesmo uma pequena fração dos ganhos de desempenho previstos com computadores quânticos, mas fazendo isso usando hardware da indústria de eletrônicos existente, seria um grande salto em frente. Explorar o comportamento natural desses circuitos para resolver problemas reais apresenta uma alternativa muito atraente para o que a próxima era da computação poderia ser. "

Esta história foi republicada por cortesia do MIT News (web.mit.edu/newsoffice/), um site popular que cobre notícias sobre pesquisas do MIT, inovação e ensino.