O que é Computação Quântica?
Computação Quântica é a utilização de propriedades de sistemas quânticos, tais como o entrelaçamento quântico e a superposição de estados, para realizar cálculos e resolver problemas. Para realizar esses cálculos utilizamos um Computador Quântico, que pode ser construído de diversas maneiras, cada uma com sua especialidade. Esse tópico é abordado com mais profundidade no post “Tipos de Computadores Quânticos” desse mesmo blog, o qual recomendo a leitura.
Os bits da Computação Quântica são chamados de qubits e podem assumir o valor zero, um, ou qualquer combinação entre eles durante o cálculo de operações lógicas. Diferentemente, na Computação Clássica os bits podem assumir apenas dois valores (0 ou 1), de maneira única e discretizada durante todos os cálculos que são feitos. Isso acontece pois o qubit se encontra em uma superposição dos dois possíveis estados até que seja feita uma medida direta e seu estado verdadeiro determinado.
Quando surgiu?
As primeiras ideias de um computador quântico surgiram na década de 1980 com a proposição feita por Paul Benioff, de que seria possível construir uma máquina de Turing utilizando um sistema de mecânica quântica. Máquina de Turing é o nome dado a um modelo matemático para computação que pode realizar uma sequência de operações muito simples. Com a sequência correta de operações uma máquina de Turing é capaz de realizar qualquer algoritmo computacional.
Segundo Benioff, seria possível descrever um sistema quântico que, a partir de um estado inicial especifico, iria evoluir com o tempo e cada estado que esse sistema assumisse representaria uma etapa lógica de uma máquina de Turing. Dessa forma, seria possível utilizar esse sistema quântico para calcular qualquer algoritmo computacional, mesmo que, num primeiro momento, de maneira ineficiente.
Em 1981, na primeira Convenção da Física da Computação, Feynman sugere que os Computadores Quânticos pudessem realizar simulações físicas que são impossíveis de serem realizadas pelos Computadores Clássicos. Conforme aumentamos o sistema quântico que desejamos simular, a eficiência da simulação cai exponencialmente se ela for feita em um computador tradicional, mas se desejamos aumentar o sistema clássico que simulamos, a eficiência cai apenas polinomialmente. Ou seja, os computadores tradicionais (ou Computadores Clássicos) são bons o suficiente para simular sistemas clássicos grandes, mas não são capazes de simular sistemas quânticos muito grandes, limitando nossas possibilidades.
Por isso, num computador quântico hipotético, seria possível simular sistemas quânticos maiores sem haver uma perda tão grande na eficiência dos cálculos. Esse computador quântico deveria rodar baseado nas leis da mecânica quântica para realizar seus cálculos, o que deve proporcionar a ele um ganho exponencial na velocidade de processamento se comparado ao clássico. Isso abriria portas para que uma gama de problemas fosse resolvida, ajudando a compreender o funcionamento de sistemas complexos e possibilitando a previsão de propriedades de matérias a partir da simulação de estruturas.
O que ela resolve?
Na décadas seguinte começaram a surgir mais estudos a respeito da computação quântica e apenas em 1992 surgiu uma das primeiras evidências de que computadores quânticos poderiam resolver certos problemas mais facilmente do que computadores clássicos.
Alguns desses estudos deram origem a algoritmos quânticos que começaram a mostrar como seria possível utilizar os fenômenos quânticos para obter um ganho computacional. Entre eles está o algoritmo de Shor, para fatoração de números inteiros, o algoritmo de Deutsch-Jozsa para avaliar se funções são balanceadas ou constantes e o algoritmo de Grover de busca de elementos em uma lista desorganizada.
Suponha que no seu sistema exista uma função dentro de uma caixa preta e você não sabe se essa função é balanceada (o resultado muda dependendo da entrada) ou constante (o resultado é o mesmo independente da entrada). O algoritmo de Deutsch-Jozsa utiliza uma superposição de estados e transformações no sistema de forma que no final do processamento, ao realizar apenas uma medida seja possível determinar se a função é balanceada ou constante. Mesmo o melhor algoritmo clássico precisaria testar todas as possíveis entradas, uma a uma, para determinar o mesmo resultado.
Portanto, ele resolve de maneira eficiente e determinística esse problema, que não pode ser resolvido tão facilmente por um algoritmo clássico. Por isso, o algoritmo de Deutsch-Jozsa é um dos primeiros algoritmos quânticos a resolver um problema de maneira mais eficiente do que os clássicos e mostrou que existem problemas para os quais seria melhor utilizar um algoritmo quântico.
Já o algoritmo de Shor se propõe a fatorar números inteiros através da periodicidade de uma função. Ele é dividido em duas partes, uma clássica, que transforma a fatoração de um número inteiro em um problema de periodicidade, e uma parte quântica, que encontra essa periodicidade utilizando a transformada quântica de Fourier. Esse algoritmo é, na teoria, capaz de quebrar o sistema de criptografia atual, uma vez que esse sistema é baseado na fatoração de números inteiros muito grandes. Entretanto ainda há gargalos na implementação desse algoritmo e até hoje 21 foi o maior número fatorado utilizando o algoritmo de Shor.
Porém, para contornar essa possível quebra no sistema de criptografias existem estudos e aplicações atualmente que utilizam a mecânica quântica para criptografar dados, esse ramo é chamado de Criptografia Quântica.
O algoritmo de busca proposto por Grover, em um primeiro momento, apresenta um ganho quadrático se comparado com os algoritmos clássicos de busca. Isso significa que, se o algoritmo clássico leva 100 etapas para encontrar o resultado, o algoritmo de Grover levaria apenas 10. Se o clássico levasse um milhão de passos, o quântico precisaria apenas de mil para resolver o mesmo problema.
Entretanto para realizar as operações esse algoritmo precisa de um oráculo, que resumidamente teria a função de traduzir as informações da lista original em qubits e assim poder encontrar e nos dar o valor desejado. O problema para a aplicação desse algoritmo está na formação do oráculo, que levaria uma quantidade muito maior de passos do que o ganho proposto pelo algoritmo inicialmente, uma vez que ele precisaria ler e traduzir cada um dos elementos da lista.
Vários outros algoritmos quânticos surgiram de lá pra cá e muitos alegam resolver certos problemas de maneira muito mais eficiente do que os melhores algoritmos clássicos existentes. Entretanto, muitos deles se propõem a resolver apenas uma parte do problema e fazem uma séria de suposições que, quando levadas em consideração, mostram que eles não são tão eficientes se comparados com os clássicos. Alguns algoritmos não levam em consideração a complexidade que existe em inserir os dados (ou preparar os estados iniciais do sistema) nem na leitura dos resultados (ou medida dos estados do sistema final), que muitas vezes traz consigo o caráter probabilístico, algo intrínseco à mecânica quântica.
Igor Mandatti Bonizio
