O que é otimização?

Observação

Observe que os solucionadores de otimização do Microsoft QIO e 1QBit serão preteridos e não estarão mais disponíveis no serviço do Azure Quantum após 30 de junho de 2023.

A otimização é o processo para encontrar a melhor solução para um problema em um conjunto de opções possíveis, considerando o resultado desejado e as restrições.

A melhor solução pode ser definida de várias maneiras: pode ser a opção com o menor custo, o runtime mais rápido ou talvez o menor impacto ambiental. Para manter as coisas simples, o melhor geralmente é definido como uma função de custo a ser minimizada. Se você quisesse maximizar a função de custo (por exemplo, se quisesse maximizar a saída de energia de uma célula solar), bastaria multiplicar o custo por um negativo e, em seguida, minimizá-lo.

Para saber mais sobre problemas de otimização e a terminologia, confira os principais conceitos de otimização.

A otimização é uma classe de problemas de computação que são os principais candidatos para execução em computadores quânticos no futuro, fornecendo uma vantagem quântica sobre soluções clássicas. Você já pode implementar problemas de otimização usando solucionadores do Azure Quantum que são executados em hardware clássico do Azure atualmente, mais rapidamente do que em muitas outras técnicas de otimização clássicas.

O que é a otimização inspirada em quantum?

A emulação de efeitos quânticos em computadores clássicos levou ao desenvolvimento de novos tipos de soluções quânticas. Os algoritmos de otimização inspirada em quantum exploram algumas das vantagens da computação quântica em hardware clássico, oferecendo agilidade em relação às abordagens tradicionais.

Os algoritmos inspirados em quantum são algoritmos clássicos em que você emula os fenômenos quânticos essenciais que proporcionam o aumento de velocidade. Há muitos tipos de algoritmos inspirados em quantum; um algoritmo comumente usado baseia-se em um modelo computacional chamado computação quântica adiabática, que consiste no seguinte:

1. Primeiro, você prepara um sistema e o inicializa para seu estado de energia mais baixo.

2. Em seguida, transforme lentamente o sistema em um mais complexo que descreve o problema que você está tentando resolver. O modelo adiabático afirma que, desde que essa transformação ocorra de modo suficientemente lento, o sistema terá tempo para se adaptar e permanecerá na configuração de energia mais baixa. Quando as transformações estiverem concluídas, você poderá resolver o problema.

Uma boa analogia para isso é imaginar que você tenha um vidro de água. Se você mover esse vidro lentamente por uma mesa, o conteúdo não será despejado, pois o sistema tem tempo para se adaptar à sua nova configuração. Mas se você movesse o vidro rapidamente, o sistema seria forçado a mudar rapidamente, derramando água por todo o local.

Onde a otimização inspirada em quantum pode ser aplicada?

A aplicação da otimização inspirada em quantum a problemas do mundo real pode oferecer insights novos ou ajudar a reduzir os custos aos negócios, tornando os processos mais eficientes. A otimização inspirada em quantum oferece a oportunidade de:

• Encontrar uma solução mais rápida do que outras técnicas de otimização para um caso de uso fixo e uma qualidade de solução fixa.
• Encontre uma solução de qualidade mais alta do que outras técnicas de otimização para um problema fixo e uma quantidade fixa de tempo.
• Use um modelo mais realista do que outras técnicas de otimização, estendendo o problema para considerar mais variáveis.

Observação

Como os métodos de otimização inspirada em quantum são heurísticos, não há garantia de que eles encontrem a solução ideal e eles nem sempre superam as outras técnicas de otimização. Na realidade, isso depende do problema e descobrir o que faz com que a otimização inspirada em quantum tenha um desempenho melhor do que outros métodos em algumas situações e não outras, ainda é uma área ativa de pesquisa.

Aqui estão as condições necessárias para que a otimização inspirada em quantum tenha um bom desempenho, em comparação com outros algoritmos clássicos de otimização:

• Os cenários de otimização devem ser acidentados, mas estruturados. Esses cenários ocorrem frequentemente em problemas do mundo real. Para obter mais informações, confira Cenários de otimização.
• Se o número de variáveis for pequeno (por exemplo, menos de 100), os algoritmos mais simples já serão suficientes. Para solucionar problemas com centenas de variáveis, a otimização inspirada em quantum alcançou o aprimoramento em relação aos métodos usados anteriormente em ordens de grandeza.
• Parâmetros do problema que afetam a métrica de custo escolhida devem ser representados por meio das variáveis de uma função de custo. Express cost functions as polynomials over binary variables to obtain a PUBO problem.

Como a otimização inspirada em quantum resolve problemas?

Existem vários métodos para localizar o mínimo global de uma função de custo; uma das heurísticas mais bem-sucedidas e comumente usadas é o recozimento simulado. Uma heurística é uma técnica para encontrar uma solução aproximada, especialmente em situações em que pode levar muito tempo para encontrar uma solução exata. Você pode considerar a técnica como uma caminhada aleatória pelo espaço da pesquisa, em que cada caminhante cria um caminho no cenário de otimização.

No recozimento simulado, o algoritmo simula um caminhante que, idealmente, sempre move em direção ao declive, mas também pode fazer movimentos em aclive com alguma probabilidade diferente de zero. Isso cria a possibilidade de que o pedestre saia do mínimo local e, em seguida, desça para um mínimo adjacente mais profundo. As movimentações em aclive são chamadas de saltos térmicos. Isso ocorre porque o recozimento simulado é um algoritmo da física que imita o comportamento dos materiais à medida que eles são lentamente resfriados.

A otimização inspirada em quantum usa as técnicas para resolver problemas combinatórios de recozimento simulado, mas aplicando efeitos mecânicos quânticos.

O recozimento quântico é um algoritmo quântico que tem princípios semelhantes aos do recozimento simulado, mas eles diferem em algumas coisas. No recozimento simulado, o espaço de pesquisa é explorado através de saltos térmicos de uma solução para a próxima, enquanto o recozimento quântico usa um efeito quântico chamado tunelamento quântico, que permite que o caminhante atravesse essas barreiras de energia.

Nesse gráfico, você pode ver a diferença entre a abordagem clássica e a quântica. No recozimento simulado as flutuações térmicas ajudam um caminhante a superar uma barreira de energia e em um túnel quântico, os efeitos quânticos permitem que um caminhante atravesse a barreira de energia.

Técnicas de otimização do Azure Quantum

Depois de criar o problema de otimização, você pode enviá-lo a um dos solucionadores de otimização inspirados em quantum no Azure Quantum. Consulte Como enviar trabalhos de otimização.

O Azure Quantum oferece uma variedade de técnicas com inspiração quântica para solucionar problemas discretos e combinatórios de otimização. No entanto, não é possível determinar qual solucionador atenderá melhor um novo problema de otimização. Você pode explorar as especificações de cada destino para desenvolver sua estratégia e, no artigo Qual solucionador de otimização devo usar?, você encontrará diretrizes sobre como usar o parâmetro de comparação para encontrar um solucionador adequado.

Em relação às soluções de otimização, esses são os provedores disponíveis dos quais você pode escolher:

• Microsoft QIO: um conjunto de vários destinos que reformulam o problema de otimização inspirado por décadas de pesquisa quântica.
• 1QBit: algoritmo heurístico iterativo que usa técnicas de pesquisa para resolver problemas de QUBO.
• Toshiba SQBM+: a Toshiba Simulated Quantum Bifurcation Machine é um computador ISING com tecnologia de GPU que resolve problemas de otimização de combinações de grande escala em alta velocidade.

Destinos do Microsoft QIO

O provedor de QIO da Microsoft está habilitado em todos os workspaces do Azure Quantum. O Microsoft QIO oferece um conjunto diversificado de destinos para cada tipo de cenário de otimização.

• Têmpera Paralela: uma abordagem de otimização clássica relacionada, em que cópias de um sistema são mantidas em temperaturas diferentes, automatizando o aquecimento e o resfriamento repetidos em abordagens de têmpera. Pode ser usada para acelerar a recozimento quântico clássico e o (simulado), bem como muitas outras heurísticas.
• Recozimento simulado: um método de simulação clássico estocástico que imita o resfriamento lento de um material (recozimento) para remover imperfeições. A temperatura é reduzida de acordo com um agendamento. Saltos térmicos auxiliam a escapar dos mínimos locais no espaço de pesquisa.
• Recozimento de População: assim como o recozimento simulado simula um caminhante que, idealmente, sempre move em direção a um declive, o recozimento de população simula uma população de caminhantes metropolitanos, que consolidam continuamente os esforços de pesquisa em busca de estados favoráveis.
• Monte Carlo Quântico: uma otimização inspirada em quantum que imita o método de recozimento quântico usando simulações de Monte Carlo quântico. Análogo à temperatura no recozimento simulado, a força do recozimento quântico é reduzida ao longo do tempo. Os efeitos do recozimento quântico auxiliam a escapar dos mínimos locais no espaço de pesquisa.
• Monte Carlo Subestocástico: o Monte Carlo Subestocástico é um algoritmo de Monte Carlo de difusão inspirado pela computação quântica adiabática. Ele simula a difusão de uma população de caminhantes no espaço de pesquisa, em que os caminhantes são removidos ou duplicados com base no desempenho deles de acordo com a função de custo.
• Pesquisa Tabu: a Pesquisa Tabu examina as configurações vizinhas. Ela pode aceitar movimentos de deterioração se nenhum movimento de melhoria estiver disponível e proíbe movimentos para soluções visitadas anteriormente

Observe que esse é apenas um pequeno subconjunto de técnicas disponíveis e a Microsoft continua a desenvolver e adicionar solucionadores ao serviço do Azure Quantum. Para obter mais informações, consulte a lista de destinos do Microsoft QIO.