Novas dicas de abordagem de multiplicação Como melhorar os computadores quânticos

Na prática, muitos programas projetados para computadores clássicos não podem ser executados em computadores quânticos porque não podem esquecer seletivamente as informações. Novo algoritmo de multiplicação mostra como contornar esse problema.

Os bits clássicos são preto e branco e os bits quânticos são um pouco mais complicados

Quando eu tinha 9 anos, meus pais compraram um computador novo. Em quase todos os aspectos, ele era melhor que o antigo, exceto um: minhas corridas favoritas não começaram. Lembro como pensei - por que preciso de um computador novo se ele não inicia meu programa favorito?

Computadores quânticos têm o mesmo problema. Em teoria, eles são capazes de tudo o que o clássico é capaz. Na prática, sua natureza quântica torna quase impossível executar alguns dos algoritmos clássicos mais importantes.

É por isso que o trabalho , publicado em 15 de abril, contém boas notícias. Craig Gidney , cientista da computação do Google AI Quantum, com sede em Santa Barbara, Califórnia, descreve uma versão quântica do algoritmo clássico para multiplicar rapidamente números muito grandes. Em computadores clássicos, esse algoritmo está em execução há algum tempo. Mas antes do trabalho de Gidney, não estava claro se seria possível adaptá-lo para máquinas quânticas.

Mais importante, o algoritmo de multiplicação pertence à classe dos onipresentes algoritmos de ciência da computação. Gidney acredita que sua nova técnica permitirá que computadores quânticos implementem toda a classe desses algoritmos, que até agora foram considerados muito pesados ​​para serem usados ​​em uma máquina quântica.

Esse algoritmo de multiplicação tira proveito da descoberta, que foi o primeiro avanço na multiplicação realizado ao longo de vários milhares de anos. O método tradicional de multiplicação escolar requer n ² etapas, onde n é o número de caracteres nos números multiplicados. Por vários milhares de anos, os matemáticos acreditavam que não havia uma abordagem mais eficiente.

Mas, como esclarecemos recentemente no artigo “Os matemáticos descobriram a maneira ideal de multiplicar números ” , em 1960, o matemático soviético Anatoly Karatsuba descobriu uma maneira mais rápida. Seu método era dividir números longos em números mais curtos. Para multiplicar dois números de oito dígitos, por exemplo, você deve primeiro dividi-los em dois números de quatro dígitos e depois dividir cada um deles em dois números de dois dígitos. Depois, é necessário executar várias operações com números de dois dígitos e restaurar o resultado da multiplicação final. Para multiplicar números muito grandes, o método Karatsuba dá muito menos passos que o método escolar.

Quando um computador clássico é executado no algoritmo Karatsuba, ele exclui informações no processo. Por exemplo, ao restaurar números de dois dígitos para números de quatro dígitos, ele esquece os números de dois dígitos. Agora ele está interessado apenas em números de quatro dígitos. A versão clássica do algoritmo é semelhante a um alpinista jogando fora seu equipamento enquanto ele escala - ele pode se mover mais rápido se não carregar todo o lixo com ele.

Mas os computadores quânticos não podem descartar informações.

Computadores quânticos realizam cálculos através de manipulações com bits quânticos, ou "qubits". Eles estão entrelaçados um com o outro ou confusos. Essa confusão oferece aos computadores quânticos enormes oportunidades - em vez de armazenar informações em bits separados, os computadores quânticos usam interações complexas de todos os qubits. Como resultado, para determinadas tarefas, os computadores quânticos são capazes de demonstrar um poder computacional exponencialmente maior em comparação aos computadores clássicos.

No entanto, a mesma propriedade que torna os computadores quânticos tão poderosos também os torna frágeis. Como os qubits estão emaranhados, é impossível mudar alguns deles sem afetar os outros. Isso torna impossível excluir seletivamente as informações disponíveis para computadores clássicos. Soltar qubits é como cortar partes de uma teia - mesmo um único corte pode destruir toda a teia.

Esse requisito para a preservação da informação complica a criação de versões quânticas de algoritmos recursivos - ou seja, voltando-se para si. Na ciência da computação, os algoritmos recursivos são amplamente utilizados; no entanto, para funcionar da melhor maneira, eles precisam do computador para descartar informações a cada passo. Sem isso, a computação se tornará rapidamente impraticável. "Se você salvar informações sempre que executar uma operação, o espaço que ela ocupa aumentará com o número de operações", disse Ashley Montanaro , especialista em informações quânticas da Universidade de Bristol. Qualquer máquina prática ficará sem memória rapidamente.

Em um novo trabalho, Gidney descreve um método quântico para implementar a multiplicação de Karatsuba, que não requer um grande consumo de memória. Em vez de gerar valores intermediários para obter o resultado final, ele usa o método " otimização da recursão da cauda " para transformar diretamente a entrada em saída. Isso permite que o algoritmo evite criar informações intermediárias que um computador quântico não pode descartar. "Ele se livra do problema de qubits extras sem gerar qubits extras", disse Thomas Vaughn , especialista em informações quânticas da Universidade de Creiton.

Gidney acredita que seu método funcionará para adaptar muitos algoritmos recursivos clássicos para computadores quânticos. Até agora, os computadores quânticos estão em uma infância tão pequena que mal conseguem lidar com a multiplicação de um dígito. No entanto, o algoritmo está pronto e, quando seus esquemas forem aprimorados, eles se tornarão capazes de muito mais.