Como você faria para devolver os livros às prateleiras corretas em uma grande biblioteca com o mínimo de caminhada? Como você determinaria a rota mais curta para um caminhão que entrega muitos pacotes em várias cidades? Estes são alguns exemplos do "problema do caixeiro viajante, "um tipo de problema de" otimização combinatória ", que freqüentemente surge em situações cotidianas. Resolver o problema do caixeiro viajante envolve procurar o mais eficiente de todos os itinerários possíveis. Para fazer isso facilmente, exigimos a ajuda de baixo consumo de energia, inteligência artificial de alto desempenho.

Para resolver este enigma, os cientistas estão explorando ativamente o uso de circuitos integrados. Neste método, cada estado em um problema de caixeiro viajante (por exemplo, cada rota possível no caminhão de entrega) é representada por "células de rotação, "cada um com um de dois estados. Usando um circuito que pode armazenar a força de um estado de célula de spin sobre o outro, a relação entre esses estados (ou para usar nossa analogia, a distância entre duas cidades para o caminhão de entrega) pode ser obtida. Usando um grande sistema contendo o mesmo número de células de spin e circuitos que os componentes (ou as cidades e rotas para o caminhão de entrega) no problema, podemos identificar o estado que requer menos energia, ou a rota cobrindo a menor distância, resolvendo assim o problema do caixeiro viajante, ou qualquer outro tipo de problema de otimização combinatória.

Contudo, uma grande desvantagem da forma convencional de usar circuitos integrados é que requer pré-processamento, e o número de componentes e o tempo necessário para inserir os dados aumentam à medida que a escala do problema aumenta. Por esta razão, esta tecnologia só foi capaz de resolver o problema do caixeiro viajante envolvendo no máximo 16 estados, ou cidades.

Um grupo de pesquisadores liderado pelo professor Takayuki Kawahara, do Departamento de Engenharia Elétrica da Universidade de Ciência de Tóquio, teve como objetivo superar esse problema. Eles observaram que as interações entre cada célula de spin é linear, que garantiu que as células de spin só pudessem interagir com as células próximas a elas, prolongando o tempo de processamento. "Decidimos organizar as células de forma ligeiramente diferente para garantir que todas as células de spin pudessem ser conectadas, "O Prof Kawahara explica.

Para fazer isso, eles primeiro organizaram os circuitos em uma matriz bidimensional, e as células de spin separadamente em um arranjo unidimensional. Os circuitos, então, liam os dados e um agregado desses dados era usado para mudar os estados das células de spin. Isso significaria que o número de células de spin necessárias e o tempo necessário para o processamento seriam drasticamente reduzidos.

Os autores apresentaram suas descobertas no IEEE 18º Simpósio Mundial em Inteligência Aplicada de Máquina e Informática (SAMI 2020). "Nossa nova técnica representa, portanto, um método totalmente acoplado, "comenta o Prof Kawahara, "e tem potencial para resolver um problema de caixeiro-viajante que envolve até 22 cidades." Os autores têm esperança de que esta tecnologia terá aplicações futuras como um sistema de alto desempenho com baixos requisitos de energia para equipamentos de escritório e terminais de tablet para encontrar facilmente soluções ideais a partir de um grande número de combinações.