Para quais problemas os computadores quânticos são bons?

Assista ao vídeo sobre aplicações da computação quântica por Olivia Lanes, ou abra o vídeo em uma janela separada no YouTube.

Introdução

Na aula anterior, abordamos um único problema em profundidade — resolver o problema de otimização Max-Cut usando a formulação QUBO. Hoje vamos adotar uma abordagem diferente e discutir aplicações de curto prazo de forma mais ampla. Começaremos dando a você uma ideia de como decidimos quais tipos de problemas podem se beneficiar de uma solução quântica. Em seguida, veremos alguns exemplos recentes de trabalhos realizados em nossa comunidade. Isso vai ajudá-lo a desenvolver uma intuição para diferentes tipos de problemas de computação quântica e como os abordamos.

Dificuldade clássica vs. quântica

Antes de mergulhar nos exemplos, vamos primeiro discutir como estudamos e categorizamos a dificuldade de vários problemas. Alguns problemas podem ser facilmente resolvidos em um computador clássico, e não temos necessidade de um computador quântico para resolvê-los. Por outro lado, existem problemas muito difíceis para os quais os computadores quânticos são necessários para resolver. Um exemplo famoso é encontrar os fatores primos de inteiros enormes. A criptografia RSA depende da dificuldade desse problema, e o algoritmo de Shor foi projetado para resolvê-lo em um computador quântico. Outro exemplo é encontrar uma solução em um conjunto de dados não ordenado — isso pode teoricamente ser resolvido pelo algoritmo quântico conhecido como algoritmo de Grover. No entanto, a maioria dos especialistas concorda que esses tipos de algoritmos vão necessitar da implementação de correção de erros, e a tecnologia ainda não chegou lá.

Então, estamos buscando problemas que possamos abordar em algum ponto intermediário entre os muito fáceis e os muito difíceis — aqueles que os computadores quânticos de hoje podem enfrentar, mas com os quais os computadores clássicos têm dificuldade.

Classes de complexidade

A dificuldade desses problemas é categorizada e analisada em um ramo da ciência da computação chamado teoria da complexidade computacional. Existem muitas classes de complexidade diferentes na computação clássica, mas algumas das mais fundamentais são:

• P: Problemas que podem ser resolvidos em tempo polinomial à medida que a escala do problema aumenta. São fáceis de resolver.
• NP: Isso significa "polinomial não determinístico". Esses problemas não necessariamente podem ser resolvidos em tempo polinomial, mas suas respostas podem ser verificadas em tempo polinomial.
• NP-completo são os problemas mais difíceis em NP e não têm solução polinomial conhecida. É aqui que vivem problemas famosos como o caixeiro-viajante e o jogo Sudoku.
• BPP, ou problemas polinomiais de erro limitado, que podem ser resolvidos dentro de um certo limiar de erro por um computador clássico probabilístico em tempo polinomial.

Quando o conceito de computação quântica foi inventado, as pessoas dedicaram esforços consideráveis tentando descobrir qual classe de problemas esses novos tipos de computadores poderiam resolver eficientemente. Uma nova classe de problemas foi inventada:

• BQP, ou problemas polinomiais quânticos de erro limitado. Este é o equivalente quântico do BPP: é a classe de problemas de decisão que podem ser resolvidos por um computador quântico em tempo polinomial com uma pequena chance de erro.

Todas essas classes vivem em uma classe maior que chamamos de PSPACE. Acima está um diagrama das relações suspeitas entre algumas das classes de complexidade, mas isso é muito difícil de provar definitivamente de forma matemática. Você vai notar que BQP não necessariamente se sobrepõe com NP-completo. Mas você ainda pode ter visto algumas abordagens de computação quântica que tentam resolver problemas em NP-completo.

Um equívoco comum é que não há sentido em explorar soluções quânticas para quaisquer problemas onde não tenha sido encontrada uma prova matemática de aceleração quântica. Mas uma prova matemática de que um algoritmo quântico é mais rápido do que seu equivalente clássico é difícil de encontrar. O algoritmo de Shor e o de Grover são dois dos poucos exemplos onde isso foi feito até agora. Na verdade, provar rigorosamente que P e NP são diferentes é uma das questões abertas mais notórias de toda a matemática, mesmo que toda a intuição nos diga que devem ser.

Mas a forma como um algoritmo escala com o aumento do tamanho do problema — que é o que é refletido na classe de complexidade — nem sempre é a característica mais relevante de um algoritmo. Esse escalonamento geralmente representa o pior caso possível. É bastante possível que, na prática, o pior caso não seja o que encontramos com mais frequência.

Só porque as provas de dificuldade são complicadas não significa que não podemos progredir. Introduzimos a ideia de soluções heurísticas. Se você é um experimentalista, provavelmente conhece e gosta desses tipos de soluções. Uma heurística é qualquer abordagem para resolver um problema que é pragmática, mas não necessariamente ótima, pois as soluções não precisam ser ótimas para serem úteis. Por exemplo, pense em aplicações financeiras. Ainda não encontramos uma aceleração exponencial para a maioria dos algoritmos financeiros para os quais o quântico poderia ser usado, mas não precisamos de uma solução ótima. Em finanças, até mesmo uma solução que seja apenas 0,1% mais eficiente poderia equivaler a bilhões de dólares de lucro.

Os computadores quânticos de hoje e seus limites

Então, como sabemos quais casos de uso e problemas podem ser adequados para a computação quântica agora? Existe uma boa razão para acreditar que utilidade quântica, ou até mesmo vantagem, pode ser encontrada agora ou em um futuro próximo?

Talvez seja mais fácil primeiro nomear as coisas que o problema certamente não deve ter. Ele não pode exigir um número enorme de qubits. Ainda não temos processadores com milhares a milhões de qubits disponíveis. Essa é uma das principais razões pelas quais o algoritmo de Shor e similares estão tão longe de serem realizados. Os circuitos também não podem ser muito profundos. O limite para a profundidade do circuito depende de muitos fatores, mas em geral, se seu experimento requer uma profundidade que você ainda não viu na literatura, provavelmente não vai funcionar. E, por último, qualquer tipo de algoritmo que saibamos que exigirá correção de erros ainda não pode ser feito.

Todas essas limitações são abordadas no roteiro do IBM Quantum® e esperamos alcançar a correção de erros no início dos anos 2030, mas por enquanto, precisamos buscar experimentos que façam uso da maioria dos qubits atualmente disponíveis em um determinado QPU. Também enfatizamos a importância da mitigação e supressão de erros. E, por último, deve haver uma extensão óbvia para aplicações futuras que seriam importantes para a sociedade e que poderíamos ver eventualmente levando a uma vantagem quântica.

Áreas de aplicação e casos de uso

Agora vamos falar sobre alguns exemplos de casos de uso, que se enquadram em três categorias principais que identificamos como mais prováveis de ter resultados favoráveis no curto a médio prazo:

1. Simulações da Natureza. Os métodos clássicos atuais de simulações atômicas e moleculares são limitados por descrições matemáticas ineficientes da estrutura atômica. Armazenar e manipular um estado quântico exige recursos exponencialmente maiores em um computador clássico, mas pode ser feito eficientemente em um computador quântico. Isso poderia levar a desenvolvimentos no sequestro de dióxido de carbono, baterias alternativas ou na invenção de novos medicamentos. Alguns algoritmos especialmente relevantes nessa área são: o Variational Quantum Eigensolver (VQE), que é usado para estimar certas propriedades de um material, como estados de equilíbrio ou de energia mínima; o algoritmo de Simulação de Dinâmica Temporal (TDS), que é usado para estimar funções de resposta ou propriedades espectrais de materiais; e um recém-chegado, Diagonalização Quântica Baseada em Amostras (SQD), que achamos que vamos ouvir muito mais nos próximos tempos.

2. Otimização. Esta área é onipresente na computação, portanto os casos de uso são numerosos e variados. Alguns exemplos que ouvimos bastante são otimização de portfólio em finanças, design industrial e distribuição e cadeia de suprimentos. O algoritmo mais comum que você provavelmente vai ouvir relacionado a finanças é o que já cobrimos com alguma profundidade: o algoritmo de otimização aproximada quântica, ou QAOA.

3. Aprendizado de máquina quântico. Esta área gerou muita empolgação nos últimos anos, mas é provável que o QML não seja útil tão cedo quanto a simulação. Mas existem, no entanto, alguns algoritmos impressionantes que estão sendo desenvolvidos para abordar alguns casos de uso muito importantes. Alguns desses casos de uso possíveis são processamento de linguagem natural, análise de tráfego de rede e até detecção de fraudes em transações financeiras. Algoritmos relevantes nesta área são a máquina de vetores de suporte quântica (QSVM), redes neurais quânticas (QNN) e redes adversariais generativas quânticas.

Dentro dessas amplas áreas de aplicação, a comunidade vê benefícios em grupos que trabalham juntos e estão focados em um tópico mais específico. A IBM® liderou uma iniciativa chamada Grupos de Trabalho para tentar ajudar colaboradores a se conhecerem e criar sinergia produtiva em quatro áreas específicas: saúde e ciências da vida, materiais e computação de alto desempenho (HPC), física de altas energias e otimização. E recentemente, um quinto grupo de trabalho sobre sustentabilidade foi criado.

Agora vamos nos aprofundar em alguns problemas que foram recentemente abordados por alguns desses grupos de trabalho. O principal objetivo aqui não é entender cada detalhe de um experimento — isso pode ser intimidador até mesmo para especialistas se o artigo estiver um pouco fora de sua área de especialidade. O objetivo é simplesmente ajudar a desenvolver uma intuição para os tipos de problemas para os quais os computadores quânticos são adequados e como abordamos sua solução. E se você estiver interessado, encorajamos você a ler os artigos completos.

Caso de Uso 1: Simulando a dinâmica de hádrons

Primeiro, vamos nos aprofundar em um artigo do grupo de Martin Savage na Universidade de Washington chamado Quantum Simulations of Hadron Dynamics in the Schwinger Model Using 112 Qubits.

Se você não é um físico de altas energias, ainda pode estar familiarizado com o termo "hádron", como no Grande Colisor de Hádrons (LHC), que é o gigantesco acelerador de partículas, com 27 km de circunferência, que tornou possível finalmente observar o bóson de Higgs. Um hádron é uma partícula subatômica composta formada por outras pequenas partículas chamadas quarks. Alguns exemplos de hádrons são nêutrons e prótons.

Para dar um pouco de contexto, o LHC foi construído para permitir o estudo da física fundamental colindo partículas em energias super altas. Com o LHC, os cientistas esperam aprender mais sobre o universo primitivo e as leis fundamentais da natureza. Em princípio, as interações dessas partículas poderiam ser simuladas do início ao fim com um computador quântico suficientemente poderoso. Ainda não chegamos lá, mas estamos progredindo.

O modelo de Schwinger é um modelo simples e popular usado para simular algumas dessas dinâmicas. É um modelo que descreve o comportamento de elétrons e pósitrons interagindo via fótons em 1+1D, ou seja, no tempo e em uma dimensão espacial. O modelo tem muitas semelhanças com a cromodinâmica quântica (QCD), que descreve como quarks e hádrons interagem, mas a QCD é extremamente difícil de simular. Portanto, o modelo de Schwinger é frequentemente usado como um modelo simplificado para investigar alguns fenômenos comuns a ambos.

Para entender por que abordaram esse problema, vamos nos fazer uma série de perguntas.

Primeiro, por que eles tinham razão para acreditar que simular isso em um computador quântico funcionaria? Nesse caso, os elétrons e pósitrons no modelo de Schwinger têm um efeito de blindagem, fazendo com que as correlações entre férmions distantes decaiam exponencialmente com a separação. Isso significa que não há tantas interações de longa distância necessárias de um qubit em um lado do chip para outro, o que sabemos ser muito propenso a erros. Portanto, isso é ótimo para o hardware disponível hoje.

Em seguida, por que esse tópico é de interesse? A física de altas energias em geral é de grande interesse. As pessoas estavam dispostas a gastar bilhões de dólares para construir o LHC, e muitos milhares de cientistas e técnicos em todo o mundo dedicaram suas carreiras a esse campo. Embora o modelo de Schwinger seja simplista e não seja projetado para cobrir três dimensões espaciais, ainda é uma simplificação útil da teoria completa.

Por fim, como esse trabalho foi feito, ou como abordaríamos o problema se estivéssemos buscando continuar esse trabalho? Em experimentos do tipo simulação, o VQE é uma das abordagens mais comuns, e o primeiro passo é quase sempre o mesmo: preparar o estado fundamental. Neste caso, é um estado de vácuo. Neste experimento, eles usam uma nova versão do VQE chamada SC-ADAPT-VQE (que significa Scalable Circuits - Adaptive Derivative-Assembled Pseudo-Trotter ansatz-VQE) para preparar tanto o estado fundamental quanto o pacote de onda de hádrons nesse vácuo. O próximo passo é deixar os hádrons evoluírem no tempo. Por fim, identificar os observáveis que você deseja medir e medi-los.

Se esses passos parecerem um pouco familiares, tirando a parte do pacote de onda de hádrons, é porque esses passos são muito semelhantes ao que cobrimos no exemplo do QAOA na aula anterior. Começamos em um estado familiar (aqui o estado de vácuo) e, em seguida, deixamos evoluir no tempo com uma série de Hamiltonianos exponenciados. Muitos algoritmos variacionais seguem essa abordagem geral. Uma grande diferença aqui, no entanto, é que criamos o pacote de onda de hádrons centrado no nosso circuito, antes de começarmos a deixá-lo evoluir.

Então, como criamos o pacote de onda? No vácuo, um hádron pode ser excitado criando um par férmion-antiférmion em sítios adjacentes. Ao preparar uma superposição de tais hádrons em locais diferentes, um pacote de onda arbitrário pode ser preparado. Os autores centraram seu pacote de onda no meio do circuito para observar a evolução sem atingir um limite.

Mas lembre-se: o nome do jogo ao trabalhar com QPUs ruidosos é manter a profundidade do circuito gerenciável. Para fazer isso, o protocolo SC-ADAPT-VQE usa simetrias e hierarquias em escalas de comprimento para determinar circuitos quânticos de baixa profundidade para a preparação de estados. Isso criará um ansatz com um número menor de parâmetros e, portanto, uma profundidade mais rasa.

O experimento foi realizado em um dispositivo IBM Quantum Heron e incluiu alguns tipos diferentes de mitigação e supressão de erros: desacoplamento dinâmico, extrapolação de ruído zero, twirling de Pauli e uma técnica desenvolvida recentemente chamada renormalização de decoerência de operadores.

Acima está uma figura do artigo mostrando o observável de interesse, o condensado quiral, que é basicamente uma fase superfluida dos hádrons. Agora podemos ver o pacote de onda no centro dos sítios que foram designados para executar esse experimento. As linhas pretas são os resultados sem erros da simulação clássica (computacionalmente cara), enquanto os pontos com barras de erro são os resultados do computador quântico IBM de 133 qubits, Torino.

Vemos dois passos temporais diferentes na evolução do pacote de onda. No tempo $t=1$, você pode ver que o condensado quiral é estreito e localizado, e também corresponde bem à simulação clássica. Em $t=14$, está muito mais espalhado. A comparação com o simulador não é tão perfeita agora, mas você ainda pode ver um acordo muito bom entre a teoria e os dados, o que é encorajador.

Em conclusão, este é um exemplo muito legal do tipo de trabalho de simulação ao qual você pode não pensar inicialmente em aplicar a computação quântica, mas que mostra grande promessa. Não é perfeito, mas você não precisa ser um especialista em física de partículas para ver que o computador quântico prevê com precisão a propagação para fora do pacote de onda, que é exatamente o que esperaríamos encontrar. Esperamos que trabalhos futuros nessa área continuem e que os físicos de altas energias continuem encontrando formas de incorporar a computação quântica em seus fluxos de trabalho. O objetivo é resolver problemas teóricos difíceis com mais precisão e usar experimentos para aceitar ou rejeitar teorias, na esperança de descobrir nova física, construir detectores melhorados e chegar a uma melhor compreensão da natureza em seu nível mais fundamental.

Caso de Uso 2: Otimização de um vidro de spin de Ising

Nosso próximo exemplo foca em otimização e será um mergulho profundo em um artigo chamado Bias-Field Digitized Counterdiabatic Quantum Optimization, realizado por membros da equipe Kipu Quantum e da Universidade do País Basco, na Espanha.

No artigo, os autores desenvolveram um novo método de otimização e o aplicaram para encontrar o estado fundamental de um vidro de spin de Ising. Como discutimos anteriormente, muitos problemas de otimização combinatória podem ser reformulados como a busca por estados de baixa energia de Hamiltonianos de Ising. O modelo de Ising descreve a interação de uma matriz de spins microscópicos. Em alguns regimes, o modelo prevê que os spins se comportam como um vidro, no qual os momentos magnéticos estão desordenados acima de uma chamada "temperatura de congelamento."

Começaremos como fizemos antes, com uma série de definições. A primeira é contraadiabático, que é um tipo de evolução que suprime efeitos não adiabáticos experimentados por um sistema, independentemente da velocidade com que esses processos ocorrem. Lembre-se do teorema adiabático do último episódio — geralmente você precisa evoluir um sistema muito lentamente se quiser que ele permaneça no estado fundamental. Isso é um grande problema porque quanto mais lentamente precisamos evoluir as coisas, mais tempo temos para que ocorram erros. A condução contraadiabática (CD) visa combater isso adicionando termos que contrabalanciam essas excitações indesejadas. A ideia principal aqui é acelerar todo o experimento e reduzir a profundidade do circuito quântico suprimindo excitações que poderiam causar transições espúrias.

Agora para o outro jargão no título: o campo de viés. Outros algoritmos iterativos, como o VQE, inserem parâmetros clássicos nos estados e usam otimizadores clássicos para pesquisar o espaço de parâmetros multidimensional para o conjunto de parâmetros que produz um valor de expectativa mínimo para um Hamiltoniano fixo. Neste caso, eles variam o Hamiltoniano a cada vez, movendo-se adiabaticamente de um caso conhecido para o caso de interesse. Para mudar o Hamiltoniano, eles simplesmente aplicam diretamente o valor de expectativa de Pauli-Z de uma iteração como um campo de viés no Hamiltoniano para a próxima iteração. Dessa forma, eles direcionam a dinâmica em direção à solução real sem a necessidade de otimizadores clássicos.

Então, por que esse experimento é de interesse? Os vidros de spin de Ising são de interesse fundamental na física, mas essa nova abordagem é ainda mais geral do que isso. Ela poderia ser aplicada a muitos problemas de otimização, então o artigo é de amplo interesse.

E por que achávamos que isso funcionaria? O algoritmo que eles estão propondo acelera a evolução para reduzir a profundidade do circuito, ao mesmo tempo em que suprime transições não adiabáticas. Além disso, não depende de nenhuma sub-rotina de otimização clássica, o que pode ser um problema levando a platôs estéreis e ficando preso em mínimos locais. Por último, os autores também se certificam de alinhar as interações no Hamiltoniano do problema com a conectividade do hardware nos QPUs reais, o que é sempre muito importante.

Então, como esse método funciona? Mais uma vez, ele não usa otimizadores clássicos, ao contrário da maioria dos outros algoritmos quânticos iterativos. Em vez disso, ao alimentar a solução de cada iteração como entrada para a próxima, o algoritmo de otimização quântica digitalizada com campo de viés refina incrementalmente o estado fundamental, aproximando-o cada vez mais do estado final evoluído. E combinado com os protocolos contraadiabáticos, podemos fazer isso mesmo com circuitos quânticos de profundidade curta que devem rodar sem problemas em hardware ruidoso.

Então, quando o experimento foi realizado, os autores escolheram executar o algoritmo no computador quântico IBM Quantum Brisbane de 127 qubits. Abaixo está uma figura mostrando a 8ª iteração do algoritmo de otimização para uma instância de vidro de spin de vizinhos mais próximos gerada aleatoriamente em 100 qubits. Eles comparam resultados idealizados de simulação clássica de DCQO e BF-DCQO, bem como o resultado experimental executado no computador quântico. Eles também mostram o resultado de um solver clássico chamado Gurobi como referência. Com apenas 10 iterações, o BF-DCQO fornece uma melhora drástica em comparação com o DCQO. Embora o resultado experimental seja um pouco diferente do resultado ideal devido ao ruído, o desempenho ainda é melhor do que o DCQO ideal. Isso mostra que ainda há muito progresso excelente sendo feito em relação à otimização quântica e bons resultados estão sendo reportados em mais de 100 qubits pela primeira vez.

Caso de Uso 3: Previsão de estrutura secundária de mRNA

Por fim, vamos discutir um artigo da Moderna Pharmaceuticals chamado mRNA Secondary Structure Prediction Using Utility-Scale Quantum Computers.

Primeiro, uma breve revisão sobre mRNA. O RNA mensageiro é um tipo de RNA envolvido na síntese de proteínas. Ele basicamente lê as instruções fornecidas pelo DNA. A estrutura secundária do mRNA é como a cadeia está dobrada, como mostrado no diagrama abaixo. E o problema de previsão de estrutura secundária de RNA é o problema de encontrar o dobramento mais estável da sequência de bases ou nucleotídeos que compõem o RNA: adenina (A), citosina (C), uracila (U) e guanina (G). A imagem abaixo mostra algumas estruturas de dobramento comuns encontradas no mRNA, cada cor representa um tipo diferente de estrutura secundária. O que torna uma estrutura mais favorável do que as outras não é bem compreendido; tudo que podemos fazer é calcular qual estrutura produz a menor energia livre em comparação com o estado não dobrado. E é aí que os computadores quânticos entram.

Então, por que as estruturas secundárias de mRNA são importantes? A previsão precisa delas é crucial não só para entender o DNA e nossos genes, mas também para projetar terapêuticas baseadas em RNA, como a vacina contra a COVID-19.

Há muito tempo se sabe que esse é um problema de otimização formidável para computadores clássicos devido ao enorme número de configurações possíveis. Para algumas configurações, sabe-se que é um problema NP-completo. No entanto, em um computador quântico, podemos formular a previsão de estrutura secundária como um problema de otimização binária — algo que sabemos como lidar. Além disso, já havia evidências na literatura de previsões precisas de RNA em dispositivos quânticos de pequena escala e simuladores quânticos. Mas isso funcionaria em hardware maior?

Este experimento foi realizado usando algo chamado eigensolver quântico variacional de valor em risco condicional, que é uma modificação de um algoritmo VQE tradicional e espera-se que alcance uma melhor convergência.

O gráfico acima mostra a distribuição das probabilidades de medição das bitstrings amostradas, com as energias correspondentes para uma instância de 42 nucleotídeos e 80 qubits. Aqui, as bitstrings simbolizam emparelhamentos de nucleotídeos. Ele ilustra que a bitstring de menor energia encontrada pelo computador quântico corresponde àquela do solver clássico comparativo, o que é ótimo. Também é mostrada a estrutura dobrada ideal dessa cadeia de nucleotídeos com base na bitstring de menor energia que o computador quântico encontrou.

Conclusão

Esperamos que esses três casos de uso tenham lhe dado contexto suficiente para entender como é o trabalho de ponta na área agora, e a confiança para tentar novos experimentos quânticos que você pode não ter tentado antes.

Lembre-se: a computação quântica não é boa para todo problema. E isso é apenas uma prova de como ficamos bons na computação clássica. Só porque você acha que poderia aplicar a computação quântica a um problema não significa que vai produzir resultados interessantes; você deve considerar o escalonamento.

A profundidade do circuito é uma faca de dois gumes. Precisamos que seja consideravelmente grande para fazer trabalho interessante que os computadores clássicos não podem fazer, mas agora não podemos aumentar a profundidade demais porque o ruído do hardware vai fazer a fidelidade diminuir. Tudo se resume a encontrar esse ponto ideal e saber que é um alvo em movimento. Então, reserve um tempo entre agora e a próxima aula para pensar em um problema que você encontrou em sua pesquisa e como poderia abordá-lo com o que aprendemos até agora. E hey, sua solução pode não funcionar, e tudo bem. É por isso que isso é pesquisa.