Ontem eu ganhei acesso a um computador quântico real da IBM! Eles tem agora um website onde você pode submeter remotamente jobs para esse computador quântico, e mandam os outputs por email. Esse website é de acesso restrito, mas eu falei que era blogueiro de ciência e podia divulgar os resultados para os brasileiros em português (colou hehe).

Pois bem, o computador tem 5 qubits e é quântico para valer. Você não programa com linguagens de programação, ao invés disso, a interface é tipo um pspice, mas com portas lógicas quânticas ao invés de portas binárias. (Mas eu já aviso que se você tiver medo de álgebra linear com números complexos, não vai passar do básico).

O computador em si é bem rústico: além de ter que lidar com superposição e entrelaçamento, você ainda tem que pensar que saída é probabilística e tem ruído. Na prática, para ver resultados consistentes você precisa rodar o mesmo algoritmo 1024 vezes e ver na média o resultado.

Dos algoritmos que eu rodei, o mais fácil de entender é o algoritmo de Grover. Ele é o equivalente à busca linear (dado um vetor não ordenado, achar o índice do elemento procurado). Ele é O(n) em um comptador clássico, mas no quântico é O(sqrt(n)). O funcionamento é curioso, você começa com os qubits entrelaçados em todas as soluções possíveis, e rotaciona o espaço de modo que a solução desejada fica um pouco mais provável que o aleatório puro. Se você rodar esse bloco sqrt(n) vezes, dá para provar que a solução correta fica muito mais provável que todas as outras, aí você aplica o threshold e corta. Na wiki tem os detalhes:

https://en.wikipedia.org/wiki/Grover%27s_algorithm

No fim de semana eu quero tentar o algoritmo de Shor de fatoração quântica (ele é muito parecido com o Pollard Rho, mas a detecção de ciclo é feita com entrelaçamento).