Em 2019, O Google afirmou que foi o primeiro a demonstrar um computador quântico realizando um cálculo além das capacidades dos supercomputadores mais poderosos de hoje.

Mas na maioria das vezes, criar um algoritmo quântico que tenha chance de vencer um computador clássico é um processo acidental, Cientistas da Universidade Purdue dizem. Para trazer mais orientação para este processo e torná-lo menos arbitrário, esses cientistas desenvolveram uma nova teoria que pode eventualmente levar a um projeto mais sistemático de algoritmos quânticos.

A nova teoria, descrito em um artigo publicado na revista Tecnologias Quantum Avançadas , é a primeira tentativa conhecida de determinar quais estados quânticos podem ser criados e processados ​​com um número aceitável de portas quânticas para superar um algoritmo clássico.

Os físicos referem-se a este conceito de ter o número certo de portas para controlar cada estado como 'complexidade'. Uma vez que a complexidade de um algoritmo quântico está intimamente relacionada à complexidade dos estados quânticos envolvidos no algoritmo, a teoria poderia, portanto, trazer ordem para a busca de algoritmos quânticos, caracterizando quais estados quânticos atendem a esses critérios de complexidade.

Um algoritmo é uma sequência de etapas para realizar um cálculo. O algoritmo geralmente é implementado em um circuito.

Em computadores clássicos, os circuitos têm portas que mudam os bits para um estado 0 ou 1. Um computador quântico, em vez disso, depende de unidades computacionais chamadas "qubits" que armazenam 0 e 1 estados simultaneamente em superposição, permitindo que mais informações sejam processadas.

O que tornaria um computador quântico mais rápido do que um computador clássico é o processamento de informações mais simples, caracterizado pela enorme redução no número de portas quânticas em um circuito quântico em comparação com um circuito clássico.

Em computadores clássicos, o número de portas em circuitos aumenta exponencialmente em relação ao tamanho do problema de interesse. Este modelo exponencial cresce tão surpreendentemente rápido que se torna fisicamente impossível de manusear, mesmo para um problema de interesse de tamanho moderado.

"Por exemplo, mesmo uma pequena molécula de proteína pode conter centenas de elétrons. Se cada elétron pode assumir apenas duas formas, então, para simular 300 elétrons exigiria 2300 estados clássicos, que é mais do que o número de todos os átomos do universo, "disse Saber Kais, professor do Departamento de Química de Purdue e membro do Instituto de Engenharia e Ciência Quantum de Purdue.

Para computadores quânticos, existe uma maneira de as portas quânticas aumentarem "polinomialmente" - em vez de apenas exponencialmente como um computador clássico - com o tamanho do problema (como o número de elétrons no último exemplo). "Polinomial" significa que haveria drasticamente menos etapas (portas) necessárias para processar a mesma quantidade de informações, tornando um algoritmo quântico superior a um algoritmo clássico.

Os pesquisadores até agora não tiveram uma boa maneira de identificar quais estados quânticos poderiam satisfazer essa condição de complexidade polinomial.

"Há um espaço de busca muito grande para encontrar os estados e a sequência de portas que correspondem em complexidade para criar um algoritmo quântico útil capaz de realizar cálculos mais rápido do que um algoritmo clássico, "disse Kais, cujo grupo de pesquisa está desenvolvendo algoritmos quânticos e métodos de aprendizado de máquina quântica.

Kais e Zixuan Hu, um associado de pós-doutorado em Purdue, usou a nova teoria para identificar um grande grupo de estados quânticos com complexidade polinomial. Eles também mostraram que esses estados podem compartilhar uma característica de coeficiente que poderia ser usada para identificá-los melhor ao projetar um algoritmo quântico.

"Dado qualquer estado quântico, agora somos capazes de projetar um procedimento de amostragem de coeficiente eficiente para determinar se ele pertence à classe ou não, "Hu disse.