A primeira vantagem quântica exponencial para um problema de streaming natural

Como a lebre aprendeu com a tartaruga, velocidade não é tudo. Cientistas teóricos da computação do Sandia National Laboratories e da Boston University descobriram que computadores quânticos são inigualáveis ​​na resolução de um problema matemático avançado. Incomumente, eles provaram que computadores quânticos não são mais rápidos do que computadores comuns; em vez disso, eles usam muito menos memória.

A revelação derruba a sabedoria convencional de que o valor de um computador quântico é que ele pode resolver certos problemas muito mais rápido do que um normal. Também pode ajudar pesquisadores a encontrar mais usos no mundo real para a tecnologia que avança rapidamente.

“Esta é a primeira vantagem quântica exponencial para um problema de streaming natural”, disse Ojas Parekh, da Sandia, membro da equipe.

A memória é importante para qualquer computador. Quanto mais memória ele tiver, maiores problemas ele pode resolver. Para computadores quânticos, que armazenam informações em qubits, “o espaço realmente importa porque é difícil construir computadores quânticos com muitos qubits”, disse Parekh.

A equipe apresentou suas descobertas no Simpósio sobre Teoria da Computação, que ocorreu de 24 a 28 de junho em Vancouver, British Columbia. A prova matemática está disponível no arXiv servidor de pré-impressão.

O valor dos computadores quânticos pode ser a eficiência da memória, não apenas a velocidade

Em 1994, o cientista americano Peter Shor surpreendeu o mundo quando provou que os futuros computadores quânticos seriam capazes de quebrar algoritmos de criptografia padrão assustadoramente rápidos. Nos 30 anos desde então, no entanto, os pesquisadores encontraram apenas um punhado de outros problemas que esses computadores podem resolver mais rápido do que os normais.

A pesquisa que surge em Sandia e na Universidade de Boston agora aponta para uma área diferente onde a vantagem quântica é possível.

“Muito do foco na pesquisa de vantagem quântica tem sido em alcançar vantagem de tempo”, disse Nadezhda Voronova, uma candidata a Ph.D. no departamento de ciência da computação da Universidade de Boston. “A pesquisa sobre vantagem quântica com relação a outros recursos, como memória, tem sido relativamente limitada.”

Mudar a atenção para esses outros atributos, como eficiência, pode ajudar os cientistas a encontrar usos mais práticos para computadores quânticos.

“Estamos atualmente perdendo vantagens quânticas importantes porque estamos focados ou tendenciosos em relação a certos tipos de problemas?”, disse Parekh.

O que é um problema natural de streaming e por que isso é importante

O problema matemático no centro da alegação da equipe, chamado corte máximo direcionado, é significativo porque é o que os pesquisadores chamam de problema natural.

“Quando falamos sobre um problema natural”, disse John Kallaugher, de Sandia, “o que queremos dizer é que é um problema de interesse independente — que as pessoas já o estudavam no cenário clássico”.

Parekh explicou ainda, “O problema do corte máximo direcionado equivale a encontrar os dois grupos de agentes em uma rede com a maior comunicação direcionada de um grupo para outro. Esse problema encontra aplicações em segurança cibernética e análise e design de redes sociais.”

Os computadores normalmente precisam de muito mais memória, pois esse tipo de problema se torna mais complexo. Mas os computadores quânticos não, descobriu a equipe. Eles são exponencialmente mais eficientes com seu uso de memória, pelo menos quando os dados chegam em um fluxo. Os cálculos de fluxo são úteis quando os conjuntos de dados são muito grandes para caber na memória de um computador ou quando os dados estão sendo criados continuamente.

Kallawher publicou anteriormente que os computadores quânticos poderiam ter uma vantagem distinta, mas menor, do que a que ele e sua equipe provaram agora. A nova descoberta de uma razão exponencial é significativa porque uma vantagem precisa ser muito grande para valer o tempo e o dinheiro necessários para construir e executar um computador quântico.

Assim como o algoritmo de Shor, a nova descoberta ainda é teórica porque ainda não foi demonstrada em um computador.

Descoberta sugere papéis futuros da computação quântica

O corte direcionado máximo não é muito útil por si só. No entanto, é um problema de otimização amplamente conhecido em matemática avançada, que a equipe de pesquisa vê como uma dica para os tipos de usos práticos que os computadores quânticos podem ter no futuro.

“Na segurança cibernética, por exemplo, resolver problemas de otimização de forma eficiente pode levar a uma melhor alocação de recursos, estratégias aprimoradas de resposta a incidentes e avaliações de risco mais precisas”, disse Voronova.

Kallawher acrescentou: “Isso pode apontar o caminho para algoritmos que podem lidar com problemas grandes demais para qualquer computador clássico processar.”

“Poderia haver mais algoritmos como esse”, especulou Voronova.

“Ninguém tem, realmente, o quadro completo”, disse Parekh.