Computação Quântica, uma breve história

Não existe dúvida que a ciência da computação mudou completamente o espectro econômico do século passado, tendo seu ápice na internet no fim dos anos 90 e permitindo uma gama de novos tipos de transações, e-commerces, retail trading com pessoas podendo comprar e vender ações do sofá de sua casa num notebook, e agora mesmo num celular depois de talvez um dia depois da aceitação da sua conta no Broker.

Porém, nos mesmos anos 90 um novo tema veio a florescer, um tema que nasceu nos anos 70 com Stephen Wiesner e depois foi explorado por Benioff, Feynman, Deutsch, e muitos outros autores até sua realização no começo nos anos 2000. Aqui darei apenas uma breve história de como esse tema tomou tanta proporção, e quais são os efeitos econômicos que essa tecnologia pode causar no futuro.

O começo da teoria

Foi Stephen Wiesner a primeira pessoa a publicar (tentar) um artigo sugerindo usar o spin (rotação) de partículas como fótons para representar 0’s e 1’s e assim gerar informação e computação. A ideia é que no processo de entanglement por exemplo (entrelaçamento quântico), pares EPR ligados A e B que estão entrelaçados, sempre vão ter rotações ortogonais uma com a outra, sempre quando você medir A e ela estiver para cima (na sua rotação) a B estará para baixo, sempre o contrário, dando o princípio da ortogonalidade.

Isso é importante, pois sem a mesma seria impossível esse sistema funcionar. Outra propriedade é a superposição de partículas, em que a partícula A pode estar em ambos estados ao mesmo tempo no momento da medição, em que você deve usar uma função de probabilidade de densidade para entender os estados deste sistema, e outro ponto é o princípio da incerteza de Heisenberg, em que você não pode saber o momentum (massa vezes aceleração) e posição da partícula simultaneamente.

Então você poderia representar funções de onda que possuem uma sequência de spins (rotações) com cada rotação representando ou 0 ou 1, e assim, por exemplo, se você quiser mandar uma mensagem de texto: “o gato está fora da caixa”, a sequência binária que representa essa mensagem estará representada na função de onda que será enviada para a pessoa (vamos usar Alice e Bob), em que Bob terá que reconstruir uma mensagem de Alice, afinal, é impossível clonar estados quânticos pelo Teorema da Não Clonagem. Wiesner sugere no seu artigo algo já nesse sentido, o que posteriormente ficou conhecido como “Quantum Teleportation”, ou Teleportação Quântica.

Talvez uma dos papers mais importantes mesmo antes de Wiesner (e corrobora com o de Toffoli) é o de Charles Bennet sobre computação reversível, chamado “Logical reversibility of computation”, em que ele sugeriu um exemplo clássico de computação reversível, na forma que o RNA funciona, sabendo que de fato biologia molecular consiste de algoritmos usando as 4 bases de nucleotídeos (Adenina, Citosina, Guanina e Timina), e que o RNA precisa usar reversibilidade em certos contextos, ele diz:

“A enzima pode, portanto, ser comparada a uma simples máquina de Turing copiadora de fita que fabrica sua fita de saída em vez de simplesmente escrever nela. A cópia de fita é uma operação logicamente reversível, e a RNA polimerase é termodinâmica e logicamente reversível” (Bennet, 1973).

E outro exemplo:

“A polinucleotídeo fosforilase catalisa a reação do RNA com fosfato livre (mantido em alta concentração) para formar monômeros de nucleotídeo fosfato. Assim como a reação da polimerase, essa reação é termodinamicamente reversível” (Bennet, 1973).

E se isso era possível biologicamente (sendo que o DNA é basicamente uma Máquina de Turing), então seria possível realizar uma Máquina de Turing Reversível, e a computação quântica é um dos exemplos onde isso se mostrou possível posteriormente.

Nos anos 80

Wiesner não conseguiu publicar seu artigo de primeiro, na verdade, demorou mais de 10 anos para ele ser aceito e publicado (com um empurrão do Charles Bennet ainda que era amigo dele), a verdade é que os que revisaram o artigo não entendiam realmente do que se tratava, pois ele no fim falava de física e o jornal era de ciência da computação.

Porém, no começo dos anos 80 artigos importantes foram publicados nesse tema. Como o de Paul Benioff em 1980 sobre Quantum Turing Machines, mostrando que poderia sim haver uma Máquina de Turing Universal capaz de realizar qualquer função computável, usando computação quântica, onde você aumentaria a árvore de possibilidades de funções computáveis, o que posteriormente foi descrito melhor com o Algoritmo de Simon.

No mesmo ano Toffoli publicou sobre a famosa Toffoli Gate no paper “Reversible Computing”, mostrando que você poder realizar funções invertíveis computacionalmente, algo que uma Máquina de Turing tradicional não poderia fazer, e quando ela é reversível, você pode fazer algoritmos ainda mais eficientes, onde você usa um encoder (oracle) para converter essa função finita. E mesmo do ponto de vista energético, a reversível permite uma dissipação de energia menor, vencendo o Limite de Landauer.

No ano seguinte foi a vez de Richard Feynman, num artigo intitulado “Simulating Physics with Computers”, onde ele diz que seria muito mais eficiente e mais fácil simular a realidade com computadores quânticos do que clássicos, visto que em essência a realidade é quântica em diversos aspectos não só na química, biofísica e etc, mas em aspectos gerais se pensarmos no macro, como em teoria de campos que unem relatividade e quântica.

Em 1982 Wooters e Zurek descobriram o teorema da não clonagem (que foi descoberto por James L. Park), que é essencial para a computação quântica, pois demonstra que ela é mais segura à ataques Man–in–the–Middle onde um hacker Eve tenta interceptar o sinal de comunicação entre Alice e Bob, e na clássica isso é facilmente feito, você só precisa de internet e wireshark ou ethercap, caso a pessoa não use criptografia em trânsito, pegar as senhas fica fácil, porém usando um sistema de informação quântico, você pode até interceptar a mensagem, mas não clonar ela.

Em outros aspectos isso se relaciona com Quantum Money, que já tinha sugerido por Wiesner no seu paper original, uma forma de dinheiro digital usando informação quântica para que seja impossível que ele possa ser clonado (já no hardware), algo avançado por Peter Shor e Scott Aaronson e outros posteriormente, até usando teoria dos nós no processo.

Fim dos anos 80 e anos 90

Ainda na década de 80 vemos papers de David Deutsch, Asher Peres, Yoshihisa Yamamoto e outros que foram relevantes para avançar o tema ainda mais, o Deustch teve uma linha mais parecida com a de Paul Benioff anteriormente, tentando demonstrar a superioridade em alguns contextos de uma Quantum Turing Machine (embora não em todos os contextos).

O paper mais relevante em criptografia dessa década foi o "Quantum cryptography: Public key distribution and coin tossing” de 1984 publicado por Charles Bennett e Gilles Brassard, mostrando que seria possível uma criptografia de chave pública usando computação quântica, mesmo com os problemas da decoerência e outros pormenores. É interessante como eles tiveram a ideia de apresentar esse tema numa conferência da Índia, enquanto conversavam numa praia sobre o assunto.

É no começo dos anos 90 que começa a explosão, Peter Shor publicou o paper chamado “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, que mostrava como seria possível fatorar números primos com maior eficiência num computador quântico, e demonstrando um algoritmo que veio a ser chamado de Algoritmo de Shor.

Grover também publicou um paper extremamente relevante, chamado “A fast quantum mechanical algorithm for database search”, onde ele descreve um algoritmo para achar colisões em bancos de dados, o que foi depois chamado de Algoritmo de Grover.

O Impacto do Algoritmo de Grover e de Shor

Não seria um exagero afirmar que tanto o algoritmo de Grover e o de Shor mudaram o cenário completamente, o primeiro sugeria fatorar números primos de forma muito mais eficiente, o que colocaria em cheque a RSA, a forma criptográfica mais usada na internet e em sistema diversos que colocariam o sistema financeiro global em cheque.

O de Grover poderia fazer hashes ficarem ainda mais seguros, para quebrar uma SHA-3 da vida você precisa achar colisões em bancos de dados de hashes para poder crackear eles, e eles são extremamente importantes para algoritmos de verificação de identidade (como no bitcoin em Merkle Trees). Caso ele fosse operável, diversos métodos de hashing poderiam ser colocados em cheque. Então basicamente poderíamos ver o fim de dois elementos criptográficos extremamente importantes para a sociedade e comércio atual, embora realizar esses algoritmos para quebrar uma RSA, por exemplo,em 8 horas, não é nem de longe possível no momento. E nem se sabe quantos anos irá demorar para isso acontecer.

Acabando com o Hype

É claro que Computação Quântica é um tema que soa muito divertido e interessante, mas o Hype pode cegar a mente das pessoas, mesmo de acadêmicos relevantes (o que acontece sempre com IA). Não é que todos os problemas computacionais podem ser melhor resolvidos com essa tecnologia, pelo contrário, existem problemas em que a computação clássica é superior a quântica, tem problemas NP-Hard que a Inteligência Artificial veio a resolver (como envelopamento de proteínas e Go pela Deep Mind da Google), e talvez tenham problemas que a computação neuromórfica (IA no hardware com memristor) pode ser melhor que ambos.

Mas é um fato que por mais que existe uma “Supremacia Quântica” de Preskill em alguns contextos, principalmente Scott Aaronson tem jogado um banho de água fria naqueles que acham que ela criaria um “Free Lunch”, um lanche grátis na ciência da computação chegando talvez perto de algum maluco dizer que faria P=NP, mas não é o caso.

Vão sim ter muitas áreas impactadas pela computação quântica, mas não todas, assim como muitas estão sendo impactadas pela IA, mas não todas, e não com tanta força e dominância como alguém poderia imaginar. Não podemos olhar para um hype e investir em empresas no setor de computação quântica (como a D-Wave, Xanadu e etc) seja no mercado de private equity ou de capital público, sem olhar para o fato que é uma tecnologia com implicações de longo prazo, então o risco em investir agora, seria o mesmo de quem investiu 20 anos atrás quando computação quântica com NMR estava começando, não necessariamente existe um retorno de curto–médio prazo.

O Futuro

Mas creio que no futuro, ela poderá ser extremamente importante, e algoritmos como Quantum Support Vector Machines (de classificação) é um exemplo que podemos ver até a combinação entre computação quântica e IA (que também é usada em algoritmos de correção de erros). O uso de grafeno e germânio vem a mostrar que existem diversos materiais sintéticos e diferenciados que podem melhorar a eficiência de computação, então o tema de "materials science" vem a ser extremamente relevante para novos tipos de arquiteturas.

Problemas como a decoerência e problemas crônicos como o princípio da incerteza de Heisenberg, sempre serão empecilhos, mas creio que sempre poderá haver avanços que um dia mudarão o tema completamente, e farão parte do hype, se tornar realidade. Quem sabe, veremos a Condensação de Fröhlich resolvendo o problema da decoerência no futuro (o que no momento é improvável).

Referências:

1. Wiesner, Stephen. "Conjugate coding." ACM Sigact News 15.1 (1983): 78-88.

2. Bennett, Charles H. "Logical reversibility of computation." IBM journal of Research and Development 17.6 (1973): 525-532.

3. Benioff, Paul. "The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines." Journal of statistical physics 22.5 (1980): 563-591.

4. Toffoli, Tommaso. "Reversible computing." International colloquium on automata, languages, and programming. Berlin, Heidelberg: Springer Berlin Heidelberg, 1980.

5. Feynman, Richard P. "Simulating physics with computers." Feynman and computation. cRc Press, 2018. 133-153.

6. Wootters, William K., and Wojciech H. Zurek. "A single quantum cannot be cloned." Nature 299.5886 (1982): 802-803.

7. Shor, Peter W., et al. Quantum Money. Vol. 19. MIT. January, 2012.

8. Aaronson, Scott. "Quantum copy-protection and quantum money." 2009 24th Annual IEEE Conference on Computational Complexity. IEEE, 2009.

9. Deutsch, David. "Quantum theory, the Church–Turing principle and the universal quantum computer." Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400.1818 (1985): 97-117.

10. Shor, Peter W. "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer." SIAM review 41.2 (1999): 303-332.

11. Grover, Lov K. "A fast quantum mechanical algorithm for database search." Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996.

12. Preskill, John. "Quantum computing and the entanglement frontier." arXiv preprint arXiv:1203.5813 (2012).

13. Preskill, John. "Why I called it ‘quantum supremacy’." Quanta Magazine 2.10 (2019): 2019.

14. Fröhlich, Herbert. "Long‐range coherence and energy storage in biological systems." International Journal of Quantum Chemistry 2.5 (1968): 641-649.