A Toshiba Corporation realizou um grande avanço na otimização combinatória - a seleção das melhores soluções entre um enorme número de padrões combinatórios - com o desenvolvimento de um algoritmo que oferece o desempenho mais rápido e em maior escala do mundo, e uma melhoria de aproximadamente 10 vezes em relação aos métodos atuais. O novo método da Toshiba pode ser aplicado a tarefas assustadoras, mas essenciais, como identificar rotas de entrega eficientes, determinar as estruturas moleculares mais eficazes para investigar no desenvolvimento de novos medicamentos, e construção de carteiras de produtos financeiros lucrativos.

A técnica recém-desenvolvida, o algoritmo de bifurcação simulado, obtém rapidamente soluções aproximadas altamente precisas (boas soluções) para problemas complexos de otimização combinatória em grande escala - problemas que resistiram à solução por um longo tempo, e isso é muito difícil de resolver usando técnicas convencionais. Potencialmente ainda mais importante, o algoritmo também alcança excelente escalabilidade a um baixo custo usando os computadores atuais, o que pode revolucionar os processos de otimização atuais.

A Toshiba usará o algoritmo de bifurcação simulado para construir uma plataforma de serviço capaz de resolver rapidamente diversos problemas sociais e comerciais, visando a comercialização em 2019.

Detalhes da nova tecnologia são publicados no jornal acadêmico online Avanços da Ciência .

Muitos problemas só podem ser resolvidos examinando um vasto número de opções para encontrar as melhores combinações. Isso inclui a realização de logística eficiente (o problema do caixeiro viajante em matemática), direcionando o tráfego para aliviar o congestionamento, aplicando desenho molecular ao desenvolvimento de drogas, e otimização de carteiras financeiras. Hoje, realizar essa otimização combinatória requer uma enorme quantidade de computação, e usar os computadores atuais para encontrar soluções continua difícil.

Há expectativas crescentes de que os dispositivos de computação de última geração, como computadores quânticos, vai liderar o caminho para melhores soluções, e a pesquisa atual visa desenvolver computadores especialmente concebidos para otimização combinatória através do uso de circuitos supercondutores, lasers, e computadores digitais baseados em semicondutores. Apesar desses esforços, continua sendo um desafio aumentar o tamanho do problema solucionável e reduzir o tempo de computação.

Por exemplo, ainda é difícil para computadores quânticos com circuitos supercondutores resolver problemas complexos de grande escala. E embora os computadores digitais baseados em semicondutores de hoje tenham facilitado o aumento do tamanho do problema solucionável, algoritmos atuais para otimização combinatória são difíceis de paralelizar, dificultando o uso da computação paralela para acelerar a resolução de problemas.

A Toshiba resolveu esses problemas desenvolvendo um novo algoritmo de otimização combinatória, o algoritmo de bifurcação simulado. É altamente paralelizável, e pode, portanto, facilmente acelerar a resolução de problemas em um computador digital padrão por meio de computação paralela. Como os atuais sistemas computacionais de grande escala podem ser usados ​​como estão, não há necessidade de instalar novos equipamentos, tornando mais fácil aumentar a escala a um custo baixo.

Por exemplo, usando matrizes de portas programáveis ​​em campo (FPGAs), uma boa solução para um problema de otimização com 2, 000 variáveis ​​totalmente conectadas (aproximadamente 2 milhões de conexões) podem ser obtidas em apenas 0,5 milissegundos. Isso é aproximadamente 10 vezes mais rápido do que o computador quântico baseado em laser, reconhecido como o mais rápido do mundo, pode resolver o mesmo problema. Além disso, usando um cluster de oito GPUs, A Toshiba obteve uma boa solução para um problema de grande escala envolvendo 100, 000 variáveis ​​totalmente conectadas (cerca de 5 bilhões de conexões) em apenas alguns segundos. Esses resultados abrem novas maneiras de resolver problemas de otimização combinatória em grande escala em muitas áreas de aplicação diferentes.

O algoritmo de bifurcação simulado aproveita os fenômenos de bifurcação, processos adiabáticos, e processos ergódicos em mecânica clássica para encontrar rapidamente soluções altamente precisas. A Toshiba derivou o princípio de uma teoria de um computador quântico proposto pela própria empresa. Esta descoberta na mecânica clássica inspirada na mecânica quântica é um interessante academicamente, resultado altamente novo que sugere a existência de teoremas matemáticos desconhecidos.

Avançando este ano, A Toshiba agora tem como objetivo usar esta inovação tecnológica chave para realizar e comercializar uma plataforma de serviço que atenda a todas as necessidades de otimização em logística, finança, e outras áreas da sociedade moderna.