• Começa Com Um Estrondo

Este problema matemático de 90 anos mostra por que precisamos de computadores quânticos

O processador Sycamore, que é uma matriz retangular de 54 qubits conectada a seus quatro vizinhos mais próximos com acopladores, contém um qubit inoperável, levando a um computador quântico efetivo de 53 qubits. A imagem óptica mostrada aqui ilustra a escala e a cor do chip Sycamore como visto na luz óptica. (GOOGLE AI QUANTUM E COLABORADORES, RECUPERADO DA NASA)

Para encontrar a rota ideal entre muitos locais diferentes, precisamos do poder dos computadores quânticos.

É hora de fazer suas tarefas e você tem várias paradas para fazer. De sua casa, você tem que ir ao supermercado, ao posto de gasolina e à loja de ferragens, tudo antes de voltar para casa. Supondo que você saiba que começa e termina em sua casa, existem seis rotas possíveis que você pode seguir, pois você pode escolher:

• primeiro o supermercado, depois o posto de gasolina e depois a loja de ferragens,
• primeiro o supermercado, depois a loja de ferragens e depois o posto de gasolina,
• primeiro o posto de gasolina, depois o supermercado e depois a loja de ferragens,
• primeiro o posto de gasolina, depois a loja de ferragens e depois o supermercado,
• primeiro a loja de ferragens, depois o supermercado e depois o posto de gasolina, ou
• primeiro a loja de ferragens, depois o posto de gasolina e depois o supermercado.

Mas qual dessas rotas será o caminho mais eficiente? Isso é conhecido, no campo da matemática, como o problema do caixeiro viajante. Para resolvê-lo por mais de um punhado de paradas, quase certamente exigirá um computador quântico. Aqui está o porquê.

Para o “problema do caixeiro viajante”, existe um número muito grande de soluções possíveis, representando todas as combinações possíveis de rotas que ligam um determinado número de pontos. Para mais do que apenas alguns destinos, o número de soluções possíveis a serem consideradas aumenta muito rapidamente para que uma abordagem de força bruta seja eficaz. (SAURABH.HARSH / WIKIMEDIA COMMONS)

Se você tem vários destinos que precisa visitar, haverá uma rota de viagem mais eficiente do que todas as outras: que desperdiçará menos tempo e distância viajando entre eles. O exemplo acima – sobre sua casa, supermercado, posto de gasolina e loja de ferragens – tinha um total de quatro destinos, mas apenas seis caminhos possíveis. Como se vê, apenas três desses caminhos são únicos, porque cada opção (por exemplo, casa ⇨ supermercado ⇨ posto de gasolina ⇨ loja de ferragens ⇨ casa) é uma das outras opções ao contrário (por exemplo, casa ⇨ loja de ferragens ⇨ posto de gasolina ⇨ supermercado ⇨ casa).

Isso é bastante simples para apenas algumas paradas, mas o número de caminhos possíveis cresce extremamente rápido: como um fatorial matemático . Para 5 destinos, existem 12 caminhos únicos possíveis; para 10 destinos, são 181.400 caminhos únicos; para 15 destinos, existem mais de 43 bilhões de caminhos únicos.

Se o cálculo de cada caminho levasse um microssegundo no problema do caixeiro viajante, tentar resolver o problema usando força bruta se tornaria praticamente impossível além de talvez 12 a 15 destinos totais. (MARK JACKSON / CAMBRIDGE QUANTUM COMPUTING)

A abordagem mais simples para resolver esse tipo de problema é usar o que chamamos de força bruta. A abordagem de força bruta simplesmente levaria a maneira possível de viajar entre quantos destinos você tivesse, calcularia a distância desse caminho e determinaria qual era o mais curto. O problema é que o número de resultados possíveis – ou o número de passeios para o caixeiro-viajante – aumenta incrivelmente rápido.

Para qualquer número de destinos totais, chame-o N , o número de passeios possíveis é ( N -1)!/2. Se você tivesse apenas 5 destinos, não demoraria tanto para calcular as distâncias para todos os 12 passeios possíveis; um computador moderno típico leva cerca de um microssegundo para calcular um passeio. Mas se você fosse até 10 destinos, levaria quase um segundo inteiro. Em 15 destinos, leva cerca de meio dia e, para 20 destinos, levaria cerca de 2.000 anos. Quando você chegar a 25 destinos, terá que rodar seu computador por cerca de 10 bilhões de anos para otimizar seu caminho: aproximadamente o mesmo que a idade do Universo.

O Four Qubit Square Circuit da IBM, um avanço pioneiro em computação, pode um dia levar a computadores quânticos poderosos o suficiente para simular um universo inteiro. Mas o campo da computação quântica ainda está em sua infância, e a supremacia quântica ainda não foi alcançada para problemas com aplicações práticas. (PESQUISA IBM)

Este problema – como muitos problemas que se pode formular – pertence a uma classe de problemas que são classificados como computacionalmente caros. Para encontrar a solução ótima entre uma infinidade de combinações possíveis requer examinar todos os caminhos razoáveis ​​que se possa imaginar, quantificar a distância (ou tempo) necessária para esse caminho e, em seguida, escolher o mais curto (ou mais rápido).

Na prática, a abordagem da força bruta não é a única, e métodos superiores para encontrar soluções exatas (em grande parte descartando caminhos obviamente não ótimos) existem, semelhantes aos avanços feitos no xadrez de computador. A maior solução exata foi alcançada em 2006, quando o caminho mais curto por 85.900 cidades foi encontrado . Demorou mais de um século de CPU-anos para encontrar essa solução.

O problema do caixeiro viajante aplicado a formigas em uma colônia de formigas. As formigas inicialmente traçam um caminho (1), mas acabam explorando uma infinidade de possíveis caminhos interconectados (2) ao longo do tempo. Eventualmente, a maioria das formigas segue a solução mais eficiente (3), deixando um rastro de feromônio que todas as formigas acabam seguindo (4). (NOJHAN / WIKIMEDIA COMMONS)

Esse tipo de problema, apesar de sua simplicidade, possui um grande número de aplicações práticas. (E não, não apenas para pessoas chamadas Papai Noel.) Se você tem uma série de pacotes indo para uma série de endereços, você deve seguir o caminho ideal. Se você está planejando sua rota de viagem, de viagens de recados a viagens de carro, você não vai querer perder tempo ou quilometragem. E se você estiver no setor aéreo, no setor de manufatura ou no setor de transporte, desejará levar seus passageiros e cargas ao destino da maneira mais rápida e eficiente possível.

Mas se o seu problema for muito complexo – se você tiver muitos destinos, por exemplo – você só conseguirá encontrar soluções aproximadas; você não pode ter certeza de que encontrou a melhor rota, ou mesmo uma das melhores rotas. A solução a que você chega será limitada pelo seu poder computacional e pela qualidade do seu algoritmo. Alguns problemas, simplesmente, são difíceis de resolver com computadores clássicos.

Um circuito quântico de 9 qubits, conforme micrografado e rotulado. As regiões cinzentas são de alumínio, as regiões escuras são onde o alumínio é gravado e as cores foram adicionadas para distinguir os vários elementos do circuito. Para um computador como este, que usa qubits supercondutores, o dispositivo deve ser mantido super-resfriado a temperaturas de milikelvin para funcionar como um verdadeiro computador quântico e operar adequadamente apenas em escalas de tempo significativamente abaixo de ~ 50 microssegundos. (C. NEILL ET AL. (2017), ARXIV: 1709.06678V1, QUANT-PH)

Felizmente, muitos problemas computacionalmente difíceis – incluindo, possivelmente, alguns aspectos do problema do caixeiro viajante – são muito menos difíceis (e muito menos caros computacionalmente) usando um computador quântico. Foi provado, há apenas alguns anos, que computadores quânticos possuem uma vantagem computacional mais do que qualquer coisa que um computador clássico poderia alcançar.

Quando a supremacia quântica foi alcançada pela primeira vez em 2019 (embora apenas para um problema específico), foi um exemplo impressionante de como os computadores quânticos poderiam resolver problemas praticamente de forma mais rápida e eficiente do que os computadores clássicos convencionais. Embora seja sempre possível que novos algoritmos ou métodos possam levar a uma solução mais rápida para qualquer problema específico em um computador clássico, os computadores quânticos mantêm algumas vantagens fundamentais.

Quando você realiza um experimento em um estado de qubit que começa como |10100> e o passa por 10 pulsos de acoplador (ou seja, operações quânticas), você não obterá uma distribuição plana com probabilidades iguais para cada um dos 10 resultados possíveis. Em vez disso, alguns resultados terão probabilidades anormalmente altas e alguns terão probabilidades muito baixas. Medir o resultado de um computador quântico pode determinar se você está mantendo o comportamento quântico esperado ou perdendo-o em seu experimento. (C. NEILL ET AL. (2017), ARXIV: 1709.06678V1, QUANT-PH)

Em vez de bits que devem ser 0 ou 1, eles trabalham com estados qubit indeterminados que existem em superposições de 0 e 1 simultaneamente. Além disso, você também pode realizar operações quânticas (em vez de apenas as clássicas) nesses qubits diretamente, mantendo toda essa estranheza quântica (incluindo indeterminismo) até o final da computação.

É aí que reside o verdadeiro poder da computação quântica: aproveitar o fato de que alguns problemas podem ser resolvidos de forma eficiente usando um computador quântico, mas os computadores clássicos só podem resolvê-los de forma ineficiente. Isso foi comprovado em 2018 pelos cientistas da computação Ran Raz e Avishay Tal , que demonstrou que os computadores quânticos podem resolver de forma eficiente problemas que:

• não são rapidamente solucionáveis ​​por um computador clássico,
• não podem ter suas soluções verificadas rapidamente por um computador clássico,
• e não se enquadram na categoria generalizada de todos os problemas que os computadores clássicos poderia teoricamente resolver em tempo polinomial .

Mostrado aqui é um componente de um computador quântico (um refrigerador de diluição), como mostrado aqui em uma sala limpa de uma foto de 2016. Os computadores quânticos alcançariam a Supremacia Quântica se pudessem concluir qualquer cálculo de forma significativamente mais rápida e eficiente do que um computador clássico. Essa conquista, por si só, no entanto, não nos permitirá alcançar todos os sonhos que temos do que a Computação Quântica poderia trazer para a humanidade. (GETTY IMAGENS)

Isso nos traz de volta ao problema do caixeiro viajante. Não é um problema que seja rapidamente solucionado por um computador clássico, mesmo com os melhores algoritmos já criados. Se você receber uma distância específica, poderá verificar facilmente se algum caminho encontrado é mais curto que essa distância ou não, mas não há garantia de que seja a distância mais curta de todas.

Mas, na verdade, é isso que você quer saber: o caminho mais curto possível é exatamente igual à distância específica coberta pelo caminho mais curto que você encontrou?

Talvez algum dia, mesmo que isso não tenha acontecido em todo o tempo em que esse problema foi examinado, possamos descobrir um algoritmo para um computador clássico que possa encontrar essa solução com eficiência. Não é garantido que tal algoritmo exista, mas a busca para descobrir um continua sendo a esperança de muitos.

As abordagens de força bruta são inadequadas para resolver um problema de caixeiro viajante com muitos nós, como o caminho de 35 nós ilustra aqui. No entanto, existem outros algoritmos que permitem encontrar soluções candidatas, que podem ser verificadas quanto à “falta” abaixo de um determinado limite. (XYPRON / DOMÍNIO PÚBLICO)

Independentemente de esse problema específico - ou a generalização de todos esses problemas teóricos - eventualmente ceder a um computador clássico ou não, no entanto, ainda haverá problemas que vão além dos limites do que um computador clássico poderia fazer com eficiência. Existem problemas que podemos colocar que têm uma resposta sim ou não, mas que não são solucionáveis ​​em tempo polinomial por um computador clássico, mesmo teoricamente.

No entanto, pelo menos alguns desses problemas, mesmo aqueles que não podem ser resolvidos com eficiência por um computador clássico, podem ser resolvidos com eficiência por um computador quântico. Embora não saibamos se o problema do caixeiro-viajante algum dia será eficientemente solucionado por um computador clássico, sabemos que existem categorias de problemas que computadores quânticos podem resolver eficientemente o que os clássicos não podem . Se existe uma solução clássica, então também existe uma solução quântica; mas mesmo que não exista uma solução clássica, uma solução quântica ainda pode ser possível.

Controlar até mesmo um único qubit e manter seu estado quântico em longas escalas de tempo é um desafio para todas as abordagens da computação quântica. Aqui, um único qubit é mostrado sendo controlado por plasma elétrico. A maioria dos qubits são tipicamente controlados por um campo magnético, mas este é controlado por pulsos elétricos seletivos. (GETTY)

Encontrar a rota mais eficiente entre um grande número de nós – a essência do problema do caixeiro viajante – tem uma infinidade de aplicações práticas. Ele aparece no sequenciamento de DNA. Ele aparece no planejamento e fabricação de microchips. Ele eleva sua cabeça no planejamento de corridas de observação de muitos objetos em astronomia. E é essencial para otimizar as rotas de entrega e a logística da cadeia de suprimentos. Mas apesar de toda a sua importância e relevância na sociedade humana, ainda não sabemos como resolver o problema de forma eficiente: no que os cientistas da computação chamam tempo polinomial .

Mesmo que tal solução não exista, e talvez não com um computador clássico, o mundo dos computadores quânticos oferece uma esperança incomparável. Um computador quântico pode resolver classes de problemas que nenhum computador clássico pode resolver com eficiência, e talvez um dia isso inclua o problema do caixeiro-viajante. Quando suas opções de força bruta são muito caras e um algoritmo eficiente o ilude, não desista de resolver o problema completamente. A revolução da computação quântica ainda pode tornar isso possível.

Começa com um estrondo é agora na Forbes , e republicado no Medium com um atraso de 7 dias. Ethan é autor de dois livros, Além da Galáxia , e Treknology: A ciência de Star Trek de Tricorders a Warp Drive .

Compartilhar: