Supremacia Quântica vs. Computação Clássica

The D-Wave Two 512 qubit Vesuvius chip in the package, ready for cooling to near-absolute zero. At D-Wave’s Canadian headquarters for their Board meeting.

A Computação quântica nasceu de forma embrionária nos papers de (Feyman, 1982), (Benioff, 1982), (Deustch, 1985), posteriormente (Chuang e Yamamoto, 1995) mostraram um sistema de circuitos quânticos. Que além de estabelecerem os pontos positivos do tema, mostraram como ela poderia superar computadores clássicos em várias áreas da ciência.

Sendo que uma visão lendária do uso de sistemas quânticos para criação de uma moeda virtual por Stephen Wiesner em (Wiesner, 1983), um tema chamado quantum money, também foi uma publicação importante para o desenvolvimento do tema, uma que demorou mais de 10 anos para ser publicada, por essa ideia ser mau vista a priori, Bennet que era amigo dele teve que pedir ao jornal acadêmico lá para aceitar, senão nem veria a luz do dia..

O de (Bennett, 1973) que demonstra como é possível a computação ser reversiva, aumentando sua eficiência, com uma analogia legal sobre sistemas biológicos terem esse fundamento permitindo a comunicação que acontece nas células, no caso de RNA mensageiro, que de certa forma é reversiva.

Arute, F., Arya, K., Babbush, R. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019). https://doi.org/10.1038/s41586-019-16...

O artigo da Google (Arute et, al. 2019) fez um estrondo de grandes magnitudes na mídia, em mostrar (mesmo com um hype exagerado) que estamos a caminho de provar experimentalmente de uma vez por todas que computação quântica realmente é o futuro.

O termo supremacia quântica nasceu em (Preskill, 2012), é uma extensão do argumento de Feyman sobre como simular a natureza seria melhor com computadores quânticos, e essa supremacia embora seja um bom objetivo futuro na área, não deveria criar um hype desmembrado de bom senso sobre o tema (como acontece muito em IA). Mas isso acontece e muito.

Aaronson chegou a explicar na Quanta Magazine, sobre a dificuldade de explicar os benchmarks e problemas que são gigantes no momento para a criação desse tipo de sistema. Problemas de inteferência do ambiente, a falta de coisas simples como uma Quantum RAM, bons algoritmos de correção de erros sempre correm contra o que a mídia fala sobre o tema, com o hype sem sal que vemos sempre nas notícias populares em Tech.

Post do Scott Aaronson na Quanta Magazine, é um cortador de hype necessário para o melhor entendimento das necessidades e verdadeiras aplicações atuais sobre o tema.

Mas mesmo assim é importante que entendamos que embora hajam esses problemas, no longo prazo computação quântica será algo extremamente relevante para a sociedade e comunidade científica, como já está sendo cada vez mais no momento.

(Markov et, al. 2018) usou os sistema da Google Cloud quantum computing service, QuIDDPro e IBM Qiskit Terra para simulações como as de Schodinger-Feynman.

Esse artigo mostra como temos muitos recursos já disponíveis, mas na minha interpretação dos resultados, temos realmente entender mais aplicações práticas e que realmente superem a computação clássica no longo prazo.

Existem sim formas de validarmos problemas que são considerados tão difíceis atualmente e que nesse caso a computação quântica poderia a ajudar e muito a aumentar a velocidade de computação nesses casos como vemos em (Harrow e Montanaro, 2017) que também foi um artigo relacionado a google.

Coisas como:

1. Fatoração de números primos (Algoritmo de Shor é famoso por mostrar isso)[Shor, 1995]
2. Database Search (o Algoritmo de Grover pode ser considerado o mais conhecido nesse problema) [Grover, 1996]
3. O Algoritmo de Simon, Algoritmo de Bernstein–Vazirani e o de Deustch-Jozsa, são conhecidos como tentativas de mostrar teoricamente a velocidade superior de computadores quânticos em alguns problemas. [Simon, 1997 ; Deutsch e Jozsa, 1992]

É necessário também mostrar que esses algoritmos funcionam na vida real (Algo que não merece tanto hype asssim), algo que vamos falar posteriormente, mas antes é necessário mostrar alguns conceitos relacionados a velocidade de computação em sistemas clássicos.

Esse é um exemplo tirado do curso One Way Quantum Computation no Coursera, da Saint Petersburg University, é uma das primeiras aulas em que o professor fala sobre velocidade computacional. Vale dizer que EXP para exponencial, deveria estar fora de NP -HARD.

Vamos a algumas definições de velocidade computacional:

1. P : Um problema resolvido em tempo polonomial como: Sorting algorithms, Bubble sort e Heapsort takes, a definição de velocidade desse caso pode ser vista aproximadamente como O(N).
2. NP: Uma classe de problemas que são complexos ao ponto de podermos validar que pode ser resolvido rapidamente, mas não podemos resolver ele de forma linear, na prática é lento pra se resolver. Não podem ser resolvido em tempo polinomial.
3. NP- Hard: Problemas que são difíceis ao ponto de poderem ser considerados como parte da classe NP, e meio que são ligados a outros problemas que chamamos de NP-Complete.
4. NP-Complete: são problemas NP que quando resolvidos, podem nos dar a chave para resolvermos outros problemas NP de uma vez, no sentido que eles são tão parecidos de certa forma que se você resolve um, resolve todos.

Alguns dos problemas considerados NP Complete são:

1. SAT
2. 3 SAT
3. Graph 3-Colourability
4. Monochromatic triangle
5. Vertex Cover
6. Chromatic Index
7. Traveling Salesman

(Fonte: An Annotated List of Selected NP-complete Problems. https://cgi.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html )

É visto que se você resolver SAT, conhecido também como SAT Solvers, você pode ter a chave para resolver os seguintes, já que o problema entre eles é parecido de certa forma, todos eles tem uma compatibilidade alta com a teoria dos gráficos, algo que permite a gente realmente dizer, você resolve um, resolve todos.

Porém existem problemas NP- Complete que não é bem assim. A Deep Mind, empresa de IA famosa pela criação do AlphaGO, AlphaZero entre outros sistemas de IA, criou em 2021 o AlphaFold que consegue prever com uma acuracidade absurda as estruturas de proteínas usando apenas Aprendizado Supervisado como modelo e IA e o banco de dados do Protein Data Bank (PDB ) como base de dados para o experimento.

https://deepmind.com/blog/article/alphafold-a-solution-to-a-50-year-old-grand-challenge-in-biology

Protein Folding foi um problema considerado NP Complete por muitos anos. No filme Traveling Salesman de Timothy Lanzone de 2012, tem uma parte que um dos pesquisadores que resolveram o problema NP nesse diálogo fictício , como esse problema poderia ser resolvido pelo sistemas deles que tinha provado que P = NP, que todos os problemas NP poderiam ser resolvidos de forma rápida, ou seja, polinomialmente pelo sistema deles, resolvendo o problema que a Deep Mind resolveu na vida real em 2021.

Essa é a prova que IA realmente pode transformar problemas complexos em algo que pode ser resolvido rápido no longo prazo. Shogi,Go, Starcraft II, Dota 2 e outros jogos que venceram campeões mundiais era jogos que poderiam e foram considerados NP- Complete, e foram vencidos pela IA.

Existem outras formas de medir a complexidade em resolver um problema computacional, separando ele em classes. Das acima a mais importante é a BQP, que já falamos no canal do Aranea Science no Youtube, no vídeo acima.

Ela é a definição de uma classe de problemas que podem ser resolvidos em tempo polinomial usando computação quântica com erro de até 1/3. Há uma prova do (Aaronson, S. 2005) que BQP = PP que têm um erro de até 1/2 em todas as instâncias do sistema.

Isso só mostra o quanto teoricamente computadores quânticos são bons para resolver problemas difíceis classicamente. Não que todos os problemas podem ser resolvidos melhor que os clássicos, mas existe, uma classe de problemas em que BQP seria a melhor forma de resolver eles rapidamente.

Problemas que Computação quântica manda em geral Teoricamente

Quantum Computing; Ion Trapping

No geral, teoricamente, fatoração de números primos é algo que o Algoritmo de Shor mostra que é possível e superior usando computadores quânticos, têm várias implicações desse algoritmo, embora seja difícil implementá-lo na prática (Harrow e Montanaro, 2018).

Todos os sistemas da internet usam pelo menos RSA, AES ou ECC, para proteger o seus sistemas de ataques man-in-the-Middle em que o hacker quer interceptar você falando no whatssap por exemplo e ouvir a conversa. Pode até ser logins, senhas, criptomoedas, jogos, aplicativos, tudo usa sistemas criptográficos para se proteger de ataques como esse e outros (Cook, 2003; Sudan, 2010; Sipser, 1992).

Porém essas criptografias funcionam apenas pela dificuldade de fatorarmos números primos classicamente, é impossível atualmente resolver uma chave RSA de 2048 bits sem demorar o tempo da sua vida mesmo com um super computador Fujitsu do Japão, que possui 158,976 nodes de 48 núcleos de processamento, 32 GB de RAM cada um e milhões de Teraflops de processamento.

(Gidney et, al. 2021) tentou demonstrar teoricamente como seria possível fatorar uma chave RSA de 2048 bits com “apenas” 20 milhões de Qubits. Um número realmente absurdo para os padrões atuais de 72 Qubits do Sycamore e os de + 5000 Qubits da D-Wave Systems.

Em 8 horas ainda, pensem em dominar o mundo em 8 horas, já que você poderia através também de outras formas de hacking para chegar a rede de um sistema Naval por exemplo, que usaria outras formas criptográficas também que não seriam um problema mais para você.

Por isso a NIST (entidade governamental dos estados unidos em tecnologia) começou o Post-Quantum Cryptography Challenge, para pesquisadores do mundo todo desenvolverem sistemas que fossem resistentes a Computação Quântica, com muitos candidatos promissores. Foi assim que foi criada a AES por acaso, antigamente chamada de Rijndael block cipher.

Com o Algoritmo de Grover no caso, a aplicação mais prática na minha visão, seria mais voltada para quebrar a criptografia de Hashes através de técnicas para achar colisões entre os hashes usando database search que é o foco desse algoritmo.

Ele pode ser usado no futuro, se possível é claro, são sabemos se a teoria vai se comprovar na prática, mas ele poderia por exemplo destruir todo o sistema de criptomoedas que se baseia em validar as transações usando hashes em uma Merkle Tree no caso do bitcoin, e inverter todas as transações de todo o Ledger do bitcoin e roubar todas as moedas assim.

Isso é Super Impossível classicamente no momento, e esse conceito está LONGE de ser realizado, mas é possível que seja necessário a criação de novos tipo de modelos de hashs quantum-secure, que aguentem o algoritmo de Grover se funcionar em futuro próximo.

SHA2, SHA3, BLAKE2, bcrypt, Scrypt, Argon2 poderiam sim ser considerados quantum-safe segundo o cryptobook.nakov, isso usando 384 bits ou mais.

Tem essa questão de se você aumenta a chave, a criptografia pode se tornar Quantum Secure como usar uma RSA de 4096 ou bits ou mais, mas o seu aplicativo ou sistema web vai ficar muito lento, isso é um problema. E não se pode validar se aumentar a chave resolve o problema para sempre.

Nas questões de segurança temos também o Teorema da Não-Clonagem ou No-Cloning Theorem (Wootters e Zurek, 1982), que estabelece que um sistema de comunicação quântica não pode ser clonado.

Isso é de extrema importância. Ataques Man-in-the-middle podem ser bem mais complexos usando esse meio, já que o hacker não consegue interceptar a mensagem e conseguir interpretar os dados de forma correta.

Paper que provou que a comunicação mais rápida do que a velocidade da luz seria impossível.

Ainda que a computação quântica tenha esses pontos positivos, há um detalhe que se fosse verdade iria ser um hype brutal, que entanglement de 2 qubits permitiria comunicar informação mais rápido que a velocidade da luz, porém (Dieks, 1982) mostrou como o experimento não foi bem feito e que nada verdade isso seria impossível, esse é um fato até hoje.

Do ponto de vista da Relatividade Especial de Einstein, nada pode ser mais rápido do que a luz, isso inclui comunicação clássica entre sistemas computacionais. Violar esse princípio básico seria bem difícil para a física em geral, no momento, impossível, não faria sentido, ao menos neste contexto, então o paper de Dieks se tornou muito importante para desmentir essa falácia.

Por fim Computação Quântica é superior em algumas áreas, outras que não falamos são na Física e Química em que na visão inicialmente proposta por (Feyman, 1982) que simular a natureza seria melhor com computadores que usassem um design totalmente diferente, já que tudo na química e física no fim tem efeitos quânticos no contexto micro da coisa, simular a natureza seria melhor dessa forma a priori.

Nesse sentido computadores quânticos são superiores aos clássicos em alguns problemas, não todos dessas áreas.

Referências:

1. Benioff, P. Quantum mechanical hamiltonian models of turing machines. J Stat Phys 29, 515–546 (1982). https://doi.org/10.1007/BF01342185
2. Feynman, Richard Phillips. “Simulating physics with computers.” International Journal of Theoretical Physics 21 (1982): 467–488.
3. Deutsch,1985.Quantum theory, the Church–Turing principle and the universal quantum computer, Proc. R. Soc. Lond. A40097–117http://doi.org/10.1098/rspa.1985.0070
4. Chuang and Yamamoto. “Simple quantum computer.” Physical review. A, Atomic, molecular, and optical physics 52 5 (1995): 3489–3496 .
5. Wiesner, Stephen. “Conjugate coding.” SIGACT News 15 (1983): 78–88.
6. Bennett, Charles H.. “Logical reversibility of computation.” Ibm Journal of Research and Development 17 (1973): 525–532.
7. Arute, F., Arya, K., Babbush, R. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019). https://doi.org/10.1038/s41586-019-16...
8. Aaronson, What Makes Quantum Computing So Hard to Explain?, Quantized Columns, Quanta Magazine, Jun. 2021.
9. Markov et, al. Quantum Supremacy Is Both Closer and Farther than It Appears, arXiv:1807.10749 [quant-ph].
10. Harrow, A., Montanaro, A. Quantum computational supremacy. Nature 549, 203–209 (2017). https://doi.org/10.1038/nature23458
11. Preskill, J. (2012). Quantum computing and the entanglement frontier. arXiv: Quantum Physics
12. Preskill, Why I Called It ‘Quantum Supremacy’, Quantized Columns, Quanta Magazine, Oct. 2019.
13. Grover, Lov K.. “A fast quantum mechanical algorithm for database search.” STOC ’96 (1996).
14. Simon, On the power of Quantum Computation, SIAM J. COMPUT. Vol. 26, №5, pp. 1474–1483, October 1997.
15. Deutsch, David and Richard Jozsa. “Rapid solution of problems by quantum computation.” Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439 (1992): 553–558.
16. Bernstein e Vazirani, Quantum Complexity Theory, SIAM J. Comput., 26(5), 1411–1473, Volume 26, Issue 5.
17. Shor, Peter W.. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.” SIAM J. Comput. 26 (1999): 1484–1509.
18. Aaronson, Scott and Alexei Y. Arkhipov. “The computational complexity of linear optics.” Electron. Colloquium Comput. Complex. 17 (2011): 170.
19. David Matuszek, Polynomial-Time Algorithms, Copyright © 1996 by David MatuszekLast modified Apr 23, 1996. https://www.seas.upenn.edu/~cit596/notes/dave/p-and-np2.html.
20. An Annotated List of Selected NP-complete Problems. https://cgi.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html.
21. Jumper, J., Evans, R., Pritzel, A. et al. Highly accurate protein structure prediction with AlphaFold. Nature 596, 583–589 (2021). https://doi.org/10.1038/s41586-021-03819-2
22. Aaronson, S. (2005). Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 461, 3473–3482.
23. Cook, Stephen A.. “The importance of the P versus NP question.” J. ACM 50 (2003): 27–29.
24. Sudan, The P vs. NP problem, May 2010.
25. Sipser, Michael. “The history and status of the P versus NP question.” STOC ’92 (1992).
26. Gidney, Craig and Martin Ekerå. “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.” Quantum 5 (2021): 433.
27. Wootters, W., Zurek, W. A single quantum cannot be cloned. Nature 299, 802–803 (1982). https://doi.org/10.1038/299802a0.
28. D. Dieks,Communication by EPR devices,Physics Letters A,Volume 92, Issue 6,1982,Pages 271–272,ISSN,03759601,https://doi.org/10.1016/0375-9601(82)90084-6.