Computação Quântica 101: é um tipo de mágica

Ao sentar para escrever essas linhas, me veio à mente os primeiros versos da canção do Queen: “It’s a kind of magic, it’s a kind of magic, a kind of magic (No way)”. Antes de explicar o motivo, vale lembrar que este é o sexto texto de uma série em andamento sobre computação quântica. Os textos anteriores podem ser encontrados na numeração correspondente a seguir: 1, 2, 3, 4 e 5.

As bases da computação quântica foram lançadas em 1981 pelo físico Richard Feynman em uma lendária palestra. Posteriormente, Feynman elaborou sua fala em um artigo publicado no International Journal of Theoretical Physics. Lá ele pontuou que a construção de dispositivos de computação baseados em princípios quânticos poderia desbloquear poderes muito maiores do que os dos computadores clássicos [1].

Feynman concluiu a palestra de 81 com uma piada que se tornou famosa:

“A natureza não é clássica, caramba, se você quiser fazer uma simulação da natureza, é melhor que seja quântica.” Richard Feynman [1]

Há quase 30 anos, Peter Shor nos apresentou o primeiro uso potencialmente transformador dos computadores quânticos. Explico, grande parte da segurança do mundo digital baseia-se no pressuposto de que fatorar grandes números é uma tarefa desafiadora e demorada. Shor nos mostrou como usar Qbits para fazer isso num piscar de olhos, pelo menos em relação aos métodos clássicos.

O algoritmo de Shor aproveita os princípios da superposição quântica e do emaranhamento (entanglement) para realizar a fatoração de maneira exponencialmente mais rápida do que os algoritmos clássicos mais conhecidos [2]. Não sabemos quando acontecerá (ou mesmo se acontecerá), mas é esperado que o método demonstrado por Shor um dia “quebre” a internet. O algoritmo traz implicações significativas para a criptografia, particularmente em relação a métodos amplamente utilizados, como o RSA, que depende justamente da dificuldade de fatorar grandes números.

Mas para tarefas menos glamourosas do que a fatoração, é difícil dizer com certeza se os métodos quânticos são superiores aos clássicos [3]. No entanto, a busca por outras aplicações quânticas, que tenham tanto sucesso quanto o algoritmo de Shor, tornou-se uma espécie de jogo aleatório.

Esse jogo, que nos últimos vinte anos uniu físicos, matemáticos e cientistas da computação em um esforço conjunto para identificar mais claramente o poder do reino quântico, parece começar a dar resultados.

Para que a leitora ou o leitor possa entender mais claramente o objetivo do esforço, vale a pena uma explicação adicional. No mundo ideal, o que gostaríamos de ter seria um número que possa ser atribuído a um arranjo de Qbits para se saber o quanto deles seria necessário para realizar uma operação quântica. Reconheço que dito assim, parece algo solto. Reformulando a frase, o que se procura é uma métrica universal quântica.

Isso significa dizer que, se o número dessa métrica for baixo, seria fácil simular o cálculo em um laptop. Se for alto, os Qbits calculados representariam a base para a resolução de um problema computacional que estaria verdadeiramente além do alcance de qualquer computador clássico. Em suma, um cálculo que possa definir se um arranjo de Qbits gera a tal “supremacia quântica”.

Lembremos que os Qbits retratam o ingrediente físico que está na origem do poder potencial dos dispositivos quânticos. São a representação de algo que existe no universo, mas ainda nos é desconhecido. O termo usado para se denominar comumente essa potencialidade é “quantumness”.

A métrica original de quantumness é aquela mesma usada por Shor em seu algoritmo: o emaranhamento. Somadas ao emaranhamento, já conseguimos encontrar mais duas. São essas duas que evocam a canção do Queen que citei no início do texto. As chamamos de mágica, mas me permitam manter o suspense mais um pouquinho antes de abordá-las.

Cada uma das três métricas representa uma maneira distinta de separar os reinos quântico e clássico. Em paralelo ao desenvolvimento dos computadores quânticos, físicos começaram a se perguntar se alguma das outras duas métricas apareceriam fora da computação quântica e em que quantidade. Estudos preliminares descobriram que todas as três aparecem e que podem oferecer uma nova maneira de compreender assuntos variados da mecânica quântica, como por exemplo, as fases da matéria quântica e a natureza destrutiva dos buracos negros. Tentarei mostrar nesse texto, a topografia desse reino quântico de três partes.

Emaranhamento é o “cara”

Na década de 1990, parecia óbvio que o ingrediente físico que tornava os computadores quânticos poderosos seria o emaranhamento. O próprio Erwin Schrödinger havia identificado a ligação entre partículas distantes como o traço característico da mecânica quântica [4].

Relembrando o que vimos no primeiro texto desta série, o emaranhamento é o fenômeno no qual duas partículas quânticas formam um estado compartilhado. Ele encapsula o que Einstein chamou de “ação assustadora à distância” [5]. Era difícil de ser reproduzido artificialmente na mecânica quântica à época e, portanto, representava aquilo em que os computadores quânticos poderiam se destacar.

Quando as partículas não estão emaranhadas, é possível acompanhá-las individualmente. Quando estão emaranhadas, modificar ou manipular uma partícula em um sistema envolve levar em conta as suas ligações com outras partículas emaranhadas. Essa tarefa cresce exponencialmente à medida que se adiciona mais partículas. Para especificar completamente o estado de n Qbits emaranhados, é preciso algo como 2^n (2 elevado à n potência) de Cbits (os bits clássicos, lembram?). Isso quer dizer que para se calcular o efeito do ajuste de um Qbit, é preciso realizar cerca de 2^n operações clássicas. Para três Qbits são apenas oito etapas. Mas para 10 Qbits temos 1.024. É a definição matemática de aumento exponencial.

Em 2003 foi publicado um artigo em que os autores elaboraram um processo simples para usar um computador clássico para simular um “circuito” quântico, que é uma série específica de operações realizadas em Qbits pelos chamados quantum gates (como vimos no quarto texto da série). Jozsa e Linden, os autores, mostraram que se você fornecesse a um algoritmo clássico algum arranjo inicial de Qbits, seria possível prever o arranjo final desses Qbits depois de terem passado pelo circuito quântico [6]. Os autores provaram que, desde que o algoritmo programado simulasse um circuito que não emaranhasse Qbits, ele poderia lidar com números cada vez maiores de Qbits sem aumentar exponencialmente o seu tempo de execução.

Em outras palavras, Jozsa e Linden mostraram que um circuito quântico livre de emaranhamento era fácil de ser simulado em um computador clássico. No sentido computacional, o circuito não era intrinsecamente quântico. A coleção de todos esses circuitos não-emaranhados (ou, equivalentemente, todos os arranjos de Qbits que possam surgir desses circuitos não-emaranhados) formava uma espécie de ilha clássica em um vasto mar quântico.

Nesse mar estavam os estados resultantes dos circuitos verdadeiramente quânticos. Aqueles para os quais uma simulação clássica poderia levar bilhões de anos para ser executada. Por esta razão, se passou a considerar o emaranhamento não apenas uma propriedade quântica, mas um recurso quântico. Mantendo a analogia marítima, era a ferramenta necessária para se alcançar aquelas profundezas desconhecidas onde residiam os algoritmos quânticos “raiz”, como o de Shor. Ainda hoje, o emaranhamento é um dos recursos quânticos mais estudados na computação, principalmente a sua relação com a complexidade computacional.

Ghosh et al., por exemplo, mostraram que, para uma classe específica de circuitos quânticos (os algoritmos de rede tensorial – tensor network algorithms), o emaranhamento determina o quão difícil é simular classicamente o circuito [7]. O que o estudo diz, basicamente, é que assim que conseguimos gerar um certo emaranhamento, é possível provar que não existe um algoritmo clássico que simule aquela situação. 

No entanto, o trabalho de Ghosh et al. é válido apenas para um tipo de circuito [7]. Mesmo o trabalho de Jozsa e Linden, de 20 anos atrás, já reconhecia que o emaranhamento por si só não conseguia capturar a riqueza do nosso oceano quântico. Os autores escreveram (em tradução livre minha):

“Apesar do papel essencial do emaranhamento, argumentamos que é, no entanto, enganador vê-lo como um recurso chave para o poder computacional quântico” Jozsa e Linden [6]. 

Uma pitada de Mágica

Em 1998, o físico Daniel Gottesman explicou que, em um tipo específico de circuito quântico (um grupo de produtos tensoriais de matrizes de Pauli e Clifford gates), a quantidade quântica aparentemente quintessencial (o exponencial 2^n) era “molemente” simulável por um computador clássico [8].

Obviamente o autor não colocou a questão nos termos acima. No método de Gottesman, a operação de emaranhamento tinha um custo computacional de aproximadamente zero [8]. Custava essencialmente nada. Isso quer dizer que poderíamos emaranhar quantos Qbits quiséssemos, que um computador clássico, ainda assim, conseguiria acompanhar. Era o teorema de Gottesman–Knill (Gottesman discutiu seu método com o matemático Emanuel Knill, que o ajudou a formalizá-lo). 

A capacidade de simular classicamente o emaranhamento parecia um milagre, mas havia uma pegadinha. O algoritmo derivado do teorema de Gottesman-Knill não conseguia lidar com todos os circuitos quânticos, apenas aqueles que estavam presos aos Clifford gates. Se adicionássemos por exemplo, uma porta T, que é um dispositivo aparentemente inócuo que gira um Qbit de uma maneira específica, o circuito travava.

Especificamente a porta T, parecia fabricar algum tipo de recurso quântico que não podia ser simulado em um computador clássico. Em pouco tempo, uma dupla de físicos russos, Sergey Bravyi e Alexei Kitaev, daria à essência quântica produzida pela rotação proibida da porta T um nome atraente: mágica [9].

Os autores elaboraram dois esquemas, conhecidos como Bravyi-Kitaev,  para realizar qualquer cálculo quântico. Poderíamos incluir portas T no próprio circuito ou poderíamos usar um “estado mágico” de Qbits que foram preparados com portas T por outro circuito e alimentá-lo em um circuito Clifford [9]. De qualquer forma, a mágica era essencial para alcançar a plenitude quântica.

Em 2016 Bravyi, em conjunto com o físico David Gosset, desenvolveu um algoritmo para simular circuitos com um nível mais baixo de mágica em computadores clássicos. O método dos autores, embora gerasse um crescimento exponencial de tempo para rodar cada porta T adicionada, conseguia limitar esse crescimento temporal. Este, não era tão explosivo como em outros casos [10]. Haviam desenvolvido um método um tanto quanto eficiente para simular classicamente um circuito mágico que continha centenas de Clifford gates e quase 50 portas T [10]. Já era possível medir a quantidade de mágica em um conjunto de Qbits.  

A importância de uma métrica para a mágica não é exagerada. Quanto mais mágico um arranjo de Qbits for, mais difícil é para um computador clássico simulá-lo. Esta segunda métrica de quantumness permite que a mágica seja usada como recurso quântico. Mas, diferentemente do emaranhamento, que já era um fenômeno físico familiar antes de ser aplicado à computação quântica, não havia certeza se a mágica funcionava fora dos computadores. Resultados recentes sugerem que sim.

Em 2021, Ellison et al. identificaram que algumas fases da matéria quântica, assim como acontece no caso do emaranhamento, possuem padrões específicos de mágica [11]. Com uma métrica de complexidade computacional baseada no estado de mágica, ganha-se mais precisão para se identificar essas fases. Por exemplo, Oliviero et al. disponibilizaram há alguns dias um estudo que mostra que teoricamente seria possível, com a ajuda da métrica mágica, reconstruir as páginas de um diário engolido por um buraco negro observando apenas a radiação que ele emite [12]. No caso em questão, o buraco negro teria que possuir uma “dose” mais baixa de mágica.

As duas métricas nos abriram uma fresta para a manipulação quantumness. Já sabemos que para criarmos sistemas verdadeiramente quânticos, é bem provável que seja necessário alguma combinação de emaranhamento e mágica. Temos claro que nenhum deles sozinho é suficiente. Se um estado quântico tiver pontuação zero em qualquer uma das métricas, você pode simulá-lo em seu laptop. Para isso, precisa um pouco de Jozsa e Linden [6] (se o emaranhamento for zero) ou de Bravyi e Gosset [10] (se a mágica for zero).

Ainda assim, o mergulho nesse oceano continua. Sabemos que apenas emaranhamento e mágica não garantem quantumness necessária para darmos saltos dentro da tecnologia quântica.

Com vocês, a Mágica Fermiônica

Chegou a hora de falarmos da nossa terceira métrica de quantumness. Ela começou a tomar forma há quase um quarto de século. Ainda assim, é a menos desenvolvida das três. 

Em 2001, Leslie Valiant descobriu uma maneira de simular uma terceira família de tarefas quânticas [13]. Assim como a técnica de Jozsa e Linden [6], que se concentra em circuitos sem portas emaranhadas, e o algoritmo Bravyi-Gosset [10], que pode rodar em circuitos sem muitas portas T, o algoritmo de Valiant se restringe a circuitos que não possuam um Swap gate, uma operação que pega dois Qbits e troca suas posições. 

Valiant mostrou que, contanto que não troquemos Qbits, podemos emaranhá-los e infundi-los com tanta mágica quanto quisermos que, ainda assim, conseguiríamos simulá-los em um laptop. A questão era que ao se trocar Qbits com os Swap gates, o circuito ganhava um poder computacional que ia muito além da capacidade de qualquer computador clássico [13]. A mudança de apenas dois Qbits abria as portas para um poder inimaginável. Saber sua origem era fundamental.

Alguns meses depois, em 2002, Barbara Terhal e David DiVincenzo [14] descobriram a fonte desse poder. O estudo mostrou que os circuitos livres de Swap gate de Valiant, conhecidos como circuitos “matchgate”, simulavam secretamente uma classe bem conhecida de problemas físicos. Semelhante à forma como os computadores simulavam galáxias em crescimento ou reações nucleares (sem realmente ser uma galáxia ou uma reação nuclear), os circuitos matchgate simulavam um grupo de férmions, uma família de partículas elementares que contém elétrons.

Quando Swap gates não são usados, os férmions simulados não interagem. Ficam “livres” e nunca se esbarram. Problemas envolvendo elétrons livres são relativamente fáceis de serem resolvidos, às vezes até com lápis e papel. Os Swap gates estimulam que férmions simulados interajam e, uma vez que isso aconteça, problemas envolvendo este tipo de partícula se tornam extremamente difíceis de serem resolvidos, se não impossíveis. Como os circuitos matchgate simulam o comportamento de férmions livres e não interagentes, eles podem facilmente ser aplicados em computadores clássicos para simular essa situação quântica específica sem gerar erro de runtime (o famoso estouro de memória que deixa o computador mais lento).

Mas após a descoberta inicial, os circuitos matchgate permaneceram praticamente inexplorados. Eles não eram tão relevantes para os principais esforços da computação quântica e eram muito mais difíceis de se analisar.

Em julho de 2023, a situação mudou. Três times de pesquisadores [15] [16] [17], trabalhando em projetos independentes, coordenaram a divulgação de seus trabalhos para o mesmo dia.

Todos os três grupos essencialmente reformularam as ferramentas matemáticas que os pioneiros da métrica mágica desenvolveram para explorar os circuitos de Clifford e as aplicaram ao domínio dos circuitos matchgate. Joshua Cudby e Sergii Strelchuk [15] se concentraram em medir matematicamente o recurso quântico que possuía circuitos de entrega. Conceitualmente, esse recurso corresponde à “interatividade” ou o quanto os férmions simulados conseguem sentir uns aos outros. Nenhuma interatividade é classicamente fácil de simular, acréscimos de interatividade tornam as simulações ainda mais difíceis. Mas o quão mais difícil uma simulação se torna com uma dose extra de interatividade? Existe algum atalho?

O grupo de Beatriz Dias e Robert Koenig [16] desenvolveu uma maneira de dividir um estado mágico mais difícil de se simular em uma enorme soma de estados mágicos mais fáceis, ao mesmo tempo em que acompanhava onde esses estados mais fáceis se anulavam e onde se somavam. O resultado foi uma espécie de dicionário para “traduzir” algoritmos que simulam classicamente circuitos Clifford em circuitos matchgate. Com isso, não existe mais a necessidade de se reinventar todos os algoritmos Clifford usados na mágica, basta traduzi-los. 

O estudo de Reardon-Smith et al. [17], por sua vez, oferece um algoritmo traduzido com a técnica Dias-Koenig para simular em computadores clássicos circuitos com alguns Swap gates. Tal qual acontece com o emaranhamento e a mágica, algoritmos demoram exponencialmente mais tempo para rodar com a adição de cada porta proibida. Embora a inclusão de Swap gates aumente a possibilidade de erros de runtime, a efetiva tradução de um algoritmo Clifford para um matchgate, representa um avanço significativo.

Reardon-Smith e seus colaboradores estimam que seu algoritmo [17] pode simular um circuito com 10 Swap gates 3 milhões de vezes mais rápido que os métodos anteriores [13] [14]. Este resultado permite que os computadores clássicos avancem um pouco mais adentro do oceano quântico, reforçando nossa capacidade de confirmar o desempenho dos computadores quânticos e expandindo a região onde é possível se criar um app quântico.

Ainda não existe um nome oficial para o recurso gerador de “interatividade” produzida por Swap gates. Alguns continuam a chamar simplesmente de mágica, outros usam termos improvisados como “coisa não fermiônica”. Strelchuk, um dos autores do estudo [15], prefere “mágica fermiônica”. Esse é o nome que adotei para este texto.

E agora, o que temos no horizonte?

É cada vez mais confortável avaliar o grau de quantumness usando as três métricas, cada uma correspondendo a um dos três métodos de simulação. Se uma coleção de Qbits for amplamente desemaranhada, tiver pouca mágica ou simular grupos de férmions quase livres, então é possível simular seus resultados em um laptop. Qualquer circuito quântico com uma pontuação baixa em uma dessas três métricas, pode tranquilamente ser desconsiderado como o próximo algoritmo de Shor.

Quanto mais nos familiarizamos com essas três maneiras de se medir o quão quântico um grupo de Qbits pode ser, mais equivocado parece ser o sonho inicial de encontrar um único número que capture todos os aspectos quânticos possíveis. Em um sentido estritamente computacional, qualquer circuito deveria ter um único tempo mínimo necessário para simulá-lo usando o mais rápido de todos os algoritmos possíveis. No entanto, o emaranhamento, a mágica e a mágica fermiônica são tão diferentes entre si que a perspectiva de unificá-los sob uma grande métrica quântica para calcular o tempo de execução mais curto parece remota. 

Os três recursos quânticos mostrados neste texto são artefatos que usam linguagens matemáticas para comprimir a complexidade do mundo quântico em estruturas mais simples. O emaranhamento surge como um recurso quando se pratica a mecânica quântica da maneira descrita por Schrödinger, que usa sua equação para prever como a função de onda de uma partícula mudará no futuro. Esta é a versão clássica da mecânica quântica, mas não é a única.

Quando Gottesman desenvolveu seu método de simulação de circuitos Clifford [8], ele o baseou em uma variedade mais antiga da mecânica quântica desenvolvida por Werner Heisenberg. Na linguagem matemática de Heisenberg, o estado das partículas não muda. Em vez disso, são os “operadores”, ou seja, os objetos matemáticos que podemos usar para prever as probabilidades de alguma observação, que evoluem. Já restringir a visão aos férmions livres envolve ver a mecânica quântica através de outra lente matemática.

Cada linguagem matemática captura certos aspectos dos estados quânticos, embora o preço dessa captura seja distorcer alguma outra propriedade. Essas propriedades quânticas, desajeitadamente expressas, tornam-se então o recurso quântico nessa estrutura matemática. Foi o que aconteceu com o emaranhamento, a mágica e a mágica fermiônica.

A busca pela quarta métrica já está a todo vapor. Minha aposta são as fases da matéria quântica que produzem probabilidades negativas absurdas quando analisadas de maneira padrão, como indicado por Feynman [18]. Assim como a mágica, é possível que essa negatividade possa definir certas fases da matéria. 

Superar a limitação imposta pela distorção gerada pela formalização e identificar uma característica quântica para governar todas elas, exigiria aprender todas as linguagens matemáticas possíveis para expressar a mecânica quântica e procurar características universais que todas elas possam compartilhar. Seria viável? Não sabemos, mas é na dúvida que a humanidade caminha.

Referências

[1] Feynman, Richard P. “Simulating Physics with Computers”. International Journal of Theoretical Physics, vol. 21, no 6, june 1982, p. 467–88. Springer Link, https://doi.org/10.1007/BF02650179.

[2] Shor, Peter W. “Algorithms for quantum computation: discrete logarithms and factoring.” Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994.

[3] Bleicher, Ariel. “Quantum Computers Struggle Against Classical Algorithms”. Quanta Magazine, february 1st, 2018, https://www.quantamagazine.org/quantum-computers-struggle-against-classical-algorithms-20180201/.

[4] Brukner, Časlav; Żukowski, Marek; Zeilinger, Anton. “The essence of entanglement”. Quantum Arrangements: Contributions in Honor of Michael Horne (2021): 117-138.

[5] Stone, A. Douglas. “Einstein and the quantum: the quest of the valiant Swabian”. Princeton University Press, 2016.

[6] Jozsa, Richard; Linden, Noah. “On the role of entanglement in quantum computational speed-up”. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, vol. 459, no 2036, August 2003, p. 2011–32. arXiv.org, https://doi.org/10.1098/rspa.2002.1097.

[7] Ghosh, Soumik; Deshpande, Abhinav; Hangleiter, Dominik;  Gorshkov, Alexey V.; Fefferman, Bill. “Sharp complexity phase transitions generated by entanglement”. Physical Review Letters, vol. 131, no July 3rd, 2023, p. 030601. arXiv.org, https://doi.org/10.1103/PhysRevLett.131.030601.

[8] Gottesman, Daniel. “The Heisenberg Representation of Quantum Computers”. Expanded version of a plenary speech at the 1998 International Conference on Group Theoretic Methods in Physics. arXiv, July 1st, 1998. arXiv.org, https://doi.org/10.48550/arXiv.quant-ph/9807006.

[9] Bravyi, Sergey; Kitaev, Alexei. “Universal Quantum Computation with ideal Clifford gates and noisy ancillas”. Physical Review A, vol. 71, no February 2nd, 2005, p. 022316. arXiv.org, https://doi.org/10.1103/PhysRevA.71.022316.

[10] Bravyi, Sergey; Gosset, David. “Improved classical simulation of quantum circuits dominated by Clifford gates”. Physical Review Letters, vol. 116, no 25, June, 2016, p. 250501. arXiv.org, https://doi.org/10.1103/PhysRevLett.116.250501.

[11] Ellison, Tyler D; Kato, Kohtaro; Liu, Zi-Wen; Hsieh, Timothy H.  “Symmetry-Protected Sign Problem and Magic in Quantum Phases of Matter”. Quantum, vol. 5, December, 2021, p. 612. DOI.org (Crossref), https://doi.org/10.22331/q-2021-12-28-612.

[12] Oliviero, Salvatore F. E; Leone, Lorenzo; Lloyd, Seth; Hamma, Alioscia. “Unscrambling quantum information with Clifford decoders”. arXiv, October 14, 2023. arXiv.org, https://doi.org/10.48550/arXiv.2212.11337.

[13] Valiant, Leslie G. “Quantum computers that can be simulated classically in polynomial time.” Proceedings of the thirty-third annual ACM symposium on Theory of computing. 2001.

[14] Terhal, Barbara M; DiVincenzo, David P. “Classical simulation of noninteracting-fermion quantum circuits”. Physical Review A, vol. 65, no 3, March 2002, p. 032325. arXiv.org, https://doi.org/10.1103/PhysRevA.65.032325.

[15] Cudby, Joshua; Strelchuk, Sergii. “Gaussian decomposition of magic states for matchgate computations”. arXiv, July 25th, 2023. arXiv.org, https://doi.org/10.48550/arXiv.2307.12654.

[16] Dias, Beatriz; Koenig, Robert. “Classical simulation of non-Gaussian fermionic circuits”. arXiv, July 25th, 2023. arXiv.org, https://doi.org/10.48550/arXiv.2307.12912.

[17] Reardon-Smith, Oliver; Oszmaniec, Michał; Korzekwa, Kamil. “Improved simulation of quantum circuits dominated by free fermionic operations”. arXiv, July 25th, 2023. arXiv.org, https://doi.org/10.48550/arXiv.2307.12702.

[18] Feynman, Richard P. “Negative probability.” Quantum implications: essays in honour of David Bohm. p. 235-248. 1987.