Para resolver as tarefas de otimização mais difíceis, basta adicionar lasers

Um dispositivo estranho conhecido como Ising Optical Machine é capaz de controlar o tráfego aéreo e ajudar a NFL a programar jogos.

No ano passado, uma falha no sistema de distribuição entre os funcionários da American Airlines poderia levar à interrupção do cronograma de milhares de voos durante a temporada de férias. O erro permitiu que os pilotos recusassem voos sem serem substituídos por outro piloto, e cerca de 15.000 vôos foram ameaçados. E embora a companhia aérea tenha conseguido rastrear o problema a tempo e distribuir funcionários , essa bagunça se tornou um lembrete de quanto dependemos dos computadores para organizar o horário de trabalho de um grande número de serviços e funções, dos quais nossa comunidade agora depende completamente.

Por exemplo, todas as principais companhias aéreas possuem algoritmos sofisticados de otimização de gráficos que comparam pilotos e voos. E embora o incidente com a American Airlines não tenha ocorrido diretamente devido à falha do algoritmo, o resultado pode ser semelhante. Tal recusa levaria a centenas de milhares de pessoas em uma situação difícil ou muito inconveniente, enquanto a companhia aérea estava procurando uma maneira de sair da situação.

O triunfo da ciência algorítmica e da lei de Moore é que agora podemos abordar muitas tarefas complexas de otimização, incluindo áreas como transporte, logística e programação. A maior parte do mundo moderno não será capaz de funcionar normalmente sem esses algoritmos: anualmente 50.000 navios de carga transportam mercadorias, 25.000 TWh de eletricidade são gerados e os roteadores transportam 1 Zettabyte de tráfego por si mesmos. Tudo isso funcionaria muito menos eficientemente. No entanto, as organizações geralmente trabalham com soluções abaixo do ideal devido a prazos apertados e falta de recursos de computador disponíveis. Além disso, ainda existem muitas oportunidades para melhorar os métodos que usamos para ajudar a resolver a maioria dos problemas de otimização.

Dada a importância da otimização e o fato de que a era de grandes e estáveis ​​melhorias na velocidade do processador parece estar chegando ao fim, os pesquisadores começaram a estudar a questão de saber se máquinas especialmente projetadas para otimização podem melhorar significativamente nossa capacidade de resolver problemas complexos.

Uma abordagem promissora é o desenvolvimento de máquinas ópticas projetadas para otimização. Um grupo de cientistas da Universidade de Stanford (que inclui o autor do artigo), liderado por Yoshihik Yamamoto, iniciou esses estudos sete anos atrás. Agora, esse tópico está sendo estudado por vários grupos de cientistas, além de pesquisadores dos laboratórios HP e NTT . Após anos de trabalho, há uma confiança crescente de que pelo menos um desses grupos poderá algum dia criar uma máquina que possa nos ajudar a abordar alguns dos problemas de otimização mais difíceis que a indústria moderna exige para resolver.


A tarefa do vendedor: a complexidade de tarefas, como encontrar o caminho mais curto entre vários pontos, aumenta com o número de pontos. Modelá-los sob o pretexto de problemas de otimização de Ising pode ajudar a resolvê-los mais rapidamente.

Lembre-se do problema clássico do vendedor, no qual o vendedor se desloca de cidade em cidade, vendendo mercadorias. Ele não quer perder tempo e dinheiro com gasolina. Essa é uma tarefa de otimização, cujo objetivo é encontrar o caminho mais curto para o vendedor, uma vez que ele precisa chegar a cada ponto uma vez e, no final da viagem, ele quer voltar para onde começou.

Para cinco cidades, o problema é resolvido simplesmente. Pode ser calculado simplesmente considerando todos os 12 caminhos . No entanto, se o vendedor esforçado pretende visitar 50 cidades, o método de busca que considera todos os caminhos possíveis será insuportável - haverá mais desses caminhos que o novo decilhão , ou 1060 - um e 60 zeros.

As possíveis soluções para esse problema podem ser fornecidas por algoritmos que usam diferentes caminhos de desvio e aproximações razoáveis. Mas mesmo os melhores podem fazer o computador mais poderoso pensar. Em um exemplo recente, a Universidade Waterloo, no Canadá, tentou encontrar o caminho mais curto entre quase 50.000 cidades nos Estados Unidos que estavam no registro nacional de lugares históricos e provar a exatidão de sua decisão. Para fazer isso, ele usou 310 processadores poderosos que funcionavam sem parar por 9 meses.

Mas a otimização envolve muito mais tarefas do que apenas a tarefa do vendedor. Outro desafio é o agendamento. Por exemplo, a Liga Nacional de Futebol dos Estados Unidos deve agendar anualmente várias centenas de jogos, enquanto tenta cumprir milhares de regras, que, por exemplo, proíbem as equipes de jogar mais de três jogos em seu próprio campo seguidos. Para resolver esse problema, em 2017, a NFL usou um cluster de 400 computadores .


Otimização de Ising : neste problema de Ising, a energia do sistema é menor quando os spins de seus elétrons são direcionados em direções opostas aos spins dos vizinhos. Os sistemas que podem encontrar o estado com energia mínima no modelo de Ising podem ajudar a acelerar a solução de problemas complexos de otimização.

As empresas de manufatura precisam planejar a manutenção da máquina. As universidades precisam de um horário. Os serviços de correio precisam planejar rotas de entrega. Grandes cidades, como Pequim ou Tóquio, adorariam aprender a gerenciar com eficiência os fluxos de milhões de carros que tentam dirigir pelas ruas durante o horário de pico. Essas tarefas podem incluir centenas ou milhares de eventos que precisam ser planejados e, em muitos casos, soluções práticas ainda não estão disponíveis, porque exigem muito tempo ou muitos computadores.

Por muitos anos, os pesquisadores tentam criar máquinas especiais para resolver problemas de otimização. Em meados da década de 1980, David Tank, que trabalhava nos laboratórios da AT&T Bell, e John Hopfield, ambos que trabalhavam na AT&T Bell e Caltech, sugeriram o uso de circuitos eletrônicos analógicos representando redes neurais para resolver problemas de otimização como o problema do vendedor ambulante. Seu trabalho deu origem a décadas de pesquisa nessa área. Então, em 1994, Leonard Edleman, da Universidade do Sul da Califórnia, descobriu que, em teoria, o DNA pode ser usado para resolver problemas desse tipo. Sua idéia deu origem a uma enxurrada semelhante de pesquisas. No entanto, essas tentativas de desenvolver abordagens radicalmente novas e eficazes para solucionar problemas de otimização levaram a alternativas práticas aos computadores e tecnologias convencionais, que continuam sendo hoje as principais ferramentas para solucionar esses problemas.

As tentativas de criar máquinas ópticas especiais capazes de resolver problemas de otimização se concentraram em um desses problemas, conhecido como otimização de Ising. Ela recebeu o nome do físico Ernst Ising, o famoso trabalho sobre o modelo de momentos magnéticos e sua explicação das transições entre diferentes estados magnéticos. Acontece que muitos problemas comuns de otimização, incluindo agendamento e localização de caminhos, podem ser facilmente transformados em problemas de otimização de Ising.

Para entender como o modelo de Ising está relacionado à otimização, você precisa começar a usá-lo na física para entender o magnetismo. Considere uma barra magnética convencional. Usando o modelo de Ising, pode-se imaginar uma barra magnética, como uma rede tridimensional de átomos, na qual cada um dos átomos é uma barra magnética. Os elétrons nos átomos têm uma propriedade chamada rotação. Os spins dos elétrons de valência - localizados nas camadas externas do átomo - são direcionados para cima ou para baixo. A direção dos giros determina a magnetização do material. Se todas as costas estiverem voltadas para cima, o material será magnetizado. Se abaixado, o material também é magnetizado - somente com a polaridade oposta. Se as costas estiverem misturadas, o material não será magnetizado.

Essas rotações também interagem entre si. Em uma barra magnética, a " energia total " de dois elétrons vizinhos é menor se seus spins estiverem alinhados - ou seja, eles são direcionados na mesma direção. Por outro lado, sua energia total é maior se os giros forem multidirecionais.


Máquina óptica de Ising: um oscilador óptico paramétrico (OPO) com feedback de medição pode resolver problemas de otimização expressos na forma do modelo de Ising - um conjunto de rotações de elétrons e sua influência um no outro. As fases dos pulsos ópticos no OPO representam rotações e o efeito é introduzido em um array de portas programável pelo usuário ( PPM ). É necessário concluir cerca de cem passagens pelo sistema antes que os impulsos no OPO se tornem poderosos o suficiente para produzir uma solução para o problema.

No modelo de Ising, resumimos a energia das interações entre os spins de cada par de elétrons em um conjunto de átomos. Como a quantidade de energia depende se as rotações estão alinhadas ou não, a energia total do conjunto depende da direção de todas as rotações do sistema. Assim, a tarefa geral da otimização de Ising é determinar em que estado os giros devem estar para minimizar a energia do sistema.

No modelo mais simples, acredita-se que apenas rotações adjacentes interajam. No entanto, no problema geral de otimização de Ising, qualquer rotação pode interagir com qualquer outra, independentemente da distância, e o sinal e a força dessas interações podem ser únicos para cada par de costas. Em uma formulação tão generalizada, esse problema é muito difícil de resolver - assim como resolver o problema de um vendedor que visita centenas de milhares de potenciais compradores. Se conseguirmos encontrar uma maneira de resolver rapidamente os problemas de otimização da Ising, e uma maneira de falar sobre o problema do vendedor ambulante e problemas semelhantes da mesma maneira que os problemas da Ising, também poderemos resolver esses problemas rapidamente. A energia mínima do sistema no problema de Ising representará a rota mais rápida entre as cidades, a solução mais eficaz para embalar um navio de carga ou qualquer outro problema de otimização necessário.

Então, como você converte o caminho de um vendedor viajante em costas? A principal tarefa é estabelecer a conformidade: precisamos apresentar nosso problema de otimização de uma forma em que uma máquina projetada para resolver problemas de otimização da Ising possa resolvê-lo. Primeiro, você precisa comparar o problema de otimização inicial - por exemplo, encontrar um caminho para o vendedor de aspiradores de pó - com um conjunto de rotações e determinar como as rotações afetam uma à outra. Graças a estudos realizados nas últimas décadas em ciência da computação e pesquisa operacional , é geralmente conhecida uma comparação de vários problemas de otimização com as formas Ising.

No entanto, é difícil trabalhar com átomos individuais e os spins de seus elétrons, então nos concentramos em criar uma máquina que implementa o modelo de Ising usando pulsos de luz em vez de spins de elétrons. O problema de Ising é comparado com o momento e as interações entre eles. O resultado é avaliado em termos da energia total do problema, e um estado com energia mínima é considerado a solução ideal. Então, essa decisão é traduzida para um idioma que faz sentido para a tarefa original - por exemplo, da maneira mais curta possível para um vendedor.

A chave para a capacidade do nosso protótipo de corresponder rotações a pulsos de luz é o OPO, um dispositivo semelhante a laser. Mas a OPO, ao contrário de um laser convencional, produz luz que está exatamente na fase, ou exatamente na fase antifásica, para alguma luz básica. É exatamente isso que é necessário para representar os estados binários da rotação, para cima e para baixo. Podemos imaginar uma rotação direcionada para cima como um estado em que a luz do OPO está em fase com a base e, vice-versa, uma rotação direcionada para baixo corresponde à luz na fase antifásica.

Existem várias maneiras de criar uma máquina Ising usando o OPO. Grupos da NTT, Caltech, Cornell e Columbia, entre outros, têm abordagens diferentes. O protótipo da máquina Ising, mostrado pela primeira vez em Stanford em um experimento liderado por Alireza Marandi (que agora trabalha em Caltech), usou uma tecnologia com a qual continuamos trabalhando ainda mais: multiplexação por divisão de tempo multiplexada e conexão óptica.

Vamos olhar para este termo difícil. Começamos com uma fonte de laser pulsado. A fonte envia pulsos de luz simultâneos com duração de vários picossegundos em duas direções. O primeiro impulso se torna básico; ele se divide e segue dois caminhos diferentes.

O segundo é usado como fonte de energia para o OPO: estimula um cristal no OPO, que emite pulsos de fótons. Cada pulso é transmitido a uma bobina de cabo em loop óptico de várias centenas de metros, dependendo do número de pulsos que precisamos. Existem centenas ou mesmo milhares de pulsos OPO neste anel, e eles perseguem em círculo um após o outro, passando pelo cristal repetidamente.


Acima: O autor do artigo e seu ex-parceiro de laboratório, Alireza Marandi, estão analisando o protótipo do computador óptico de Ising.
Abaixo: a maioria dos eventos ocorre dentro do carretel de cabo óptico

As fases desses pulsos desempenharão o papel dos giros do modelo de Ising. Mas imediatamente após sua criação, antes de passarem pelo ciclo várias vezes, eles são tão fracos que suas fases não são bem definidas. A maneira como os fazemos interagir, finalmente, fornecerá as fases finais e a solução para o nosso problema de Ising.

Lembre-se da luz de base da descrição do experimento? Em um ponto do loop, há um divisor que seleciona uma pequena porção de cada pulso, que é comparada com o pulso base no detector de homodino. A tensão de saída do detector contém informações sobre a fase e a amplitude do detector. Este sinal é digitalizado e alimentado no PPVM. Nele, o próprio problema de Ising é apresentado.

Lembre-se de que resolver o problema de Ising significa encontrar o estado mínimo de energia para um conjunto de rotações nas quais as rotações interagem de maneiras diferentes, e essas interações adicionam energia adicional à energia total do sistema. No HME, cada impulso indica uma rotação. Portanto, para cada pulso - e em nossa configuração usamos 100 - o PPMM realiza cálculos, que incluem as medições registradas de todos os outros pulsos, que, de acordo com o problema de Ising, devem afetar o giro em consideração. O processador aplica os cálculos às configurações do modulador de intensidade e modulador de fase localizados em um dos caminhos do pulso de base. O pulso base modificado é alimentado no anel do cabo de fibra óptica, no qual o OPO pulsa a espionagem.

É fundamental escolher o momento certo - precisamos do pulso base combinado para combinar com o pulso OPO certo. Se feito corretamente, os dois pulsos se misturam. Dependendo de estarem em fase ou não, o impulso introduzido no sistema inclina o impulso OPO para representar uma rotação direcionada para cima ou para baixo.

Para cada pulso OPO no loop, repetimos todo esse processo e, para atingir os estados finais da fase, os pulsos podem viajar dezenas de milhares de vezes ao longo de todo o comprimento do loop. Depois disso, um computador separado lê um conjunto de fases, interpreta-as como elétrons do problema de Ising com giros apontando para cima ou para baixo e, em seguida, transforma isso em uma solução significativa para o problema de otimização inicial que você precisa resolver.

Em nossos experimentos, criamos um sistema com quatro rotações e depois com 16 rotações. Os parâmetros da tarefa foram baseados em hardware em instalações na forma de segmentos ramificados de um cabo óptico de um determinado comprimento. Nessas experiências, descobrimos com sucesso estados de energia mínima, e isso nos motivou a desenvolver essa abordagem. Em 2016, criamos uma máquina de feedback baseada em PPVM capaz de resolver problemas de Ising com 100 rotações. A comparação da velocidade de nossas instalações com sistemas especializados, incluindo o aparelho de " recozimento quântico " da NASA, nos deu confiança de que as máquinas Ising OPO podem ser otimizadores eficientes.

Os resultados foram promissores, mas ainda temos muito a aprender antes de entendermos se essa abordagem óptica pode chegar à frente de um processador convencional na solução de problemas práticos de otimização. É possível que a capacidade da máquina de resolver problemas possa ser aprimorada usando estados quânticos de luz, que são muito difíceis de simular. Estamos apenas abordando a solução de muitas dessas questões e planejamos nos próximos anos estudar a interação extremamente interessante entre teoria e experimento, desenvolvendo esse novo tipo de computador.