quinta-feira, 12 de maio de 2016

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).




sexta-feira, 6 de maio de 2016

O Euclides era foda pra caralho mesmo. Eu estava aqui de boa tomando banho quando me caiu a ficha de que os cinco postulados deles na verdade são propriedades do espaço. Olha só, na forma original eles são assim:
1. Por dois pontos passa um reta.
2. Uma reta sempre pode ser estendida indefinidamente.
3. Dado um ponto e um raio, você pode construir um círculo.
4. Todos os ângulos retos são congruentes.
5. Dado uma reta e um ponto fora dela, você pode construir uma paralela.
O Heath fala que o quarto postulado é esquisito, tinha outras afirmações equivalentes que ele poderia ter usado. Mas ele precisava do quarto nessa formulação exata, senão não tinha como descrever o quinto de forma não-ambígua.
Aí eu fiquei pensando se existem outras maneiras, e achei uma equivalente só com proposições sobre o espaço:
1. O espaço é contínuo.
2. O espaço é infinito.
3. O espaço é métrico.
4. O espaço é invariante a rotações.
5. O espaço tem curvatura zero.
Esses cinco postulados alternativos que eu bolei são equivalentes aos postulados do Euclides, você pode usar esses para provar os dele e vice-versa.
Para mim mostra que o Euclides manjava muito, ele não tinha essas noções modernas sobre o espaço mas achou uma maneira grega de dizer a mesma coisa!