Um estudo comprovando a dificuldade de simular circuitos quânticos aleatórios para computadores clássicos

Os computadores quânticos, tecnologias que realizam cálculos que aproveitam os fenômenos da mecânica quântica, poderiam eventualmente superar os computadores clássicos em muitos problemas complexos de computação e otimização. Embora alguns computadores quânticos tenham alcançado resultados notáveis ​​em algumas tarefas, sua superioridade sobre os computadores clássicos ainda não foi comprovada de forma conclusiva e consistente.

O pesquisador do Google Quantum AI, Ramis Movassagh, que anteriormente trabalhou na IBM Quantum, conduziu recentemente um estudo teórico com o objetivo de demonstrar matematicamente as notáveis ​​vantagens dos computadores quânticos. Seu artigo publicado em Física da naturezamostra matematicamente que simular circuitos quânticos aleatórios e estimar suas saídas é chamado de #P-hard para computadores clássicos (ou seja, extremamente difícil).

“Uma questão chave no campo da computação quântica é: os computadores quânticos são significativamente mais poderosos do que os computadores clássicos?” Ramis Movassagh, que conduziu o estudo, disse ao Phys.org. “A conjectura da supremacia quântica (que renomeamos como conjectura da supremacia quântica) diz que sim. No entanto, matematicamente, era um grande problema em aberto que precisava ser rigorosamente comprovado.”

Recentemente, pesquisadores têm tentado comprovar as vantagens dos computadores quânticos sobre os computadores clássicos de diversas maneiras, tanto por meio de estudos teóricos quanto experimentais. A chave para provar isso matematicamente é provar que é difícil para os computadores clássicos alcançarem os resultados dos computadores quânticos com alta precisão e uma pequena margem de erro.

“Em 2018, um colega deu uma palestra no MIT, na época, sobre um resultado recente que tentava fornecer evidências da robustez da amostragem de circuito aleatório (RCS)”, explicou Movasagh. “RCS é uma tarefa que coleta amostras das saídas de um circuito quântico arbitrário e acaba de ser sugerida pelo Google como a principal candidata para provar a primazia quântica. Eu estava na plateia e nunca havia trabalhado com complexidade quântica antes; na verdade, lembro-me disso como estudante de pós-graduação, jurei que nunca trabalharia nessa área!”

A prova matemática apresentada pelo colega de Movasag no MIT em 2018 não resolveu de forma conclusiva o antigo problema de demonstrar a prioridade quântica, mas mesmo assim representou um progresso significativo em direção a esse objetivo. A prova é obtida por meio de uma série de aproximações e do chamado truncamento de série; Assim, foi um tanto indireto e introduziu erros desnecessários.

“Gosto de conectar a matemática para resolver problemas grandes e abertos, especialmente se a matemática for simples, menos conhecida pelos especialistas na área e bonita”, disse Movasagh. “Nesse caso, senti que talvez pudesse encontrar uma pista melhor e ingenuamente pensei que, se resolvesse o problema da maneira certa, poderia ser capaz de resolver o grande problema em aberto. Então, comecei a trabalhar nisso. ”

A prova matemática apresentada por Movasagh difere significativamente daquela apresentada até agora. Baseia-se num novo conjunto de técnicas matemáticas que mostram colectivamente que as probabilidades de saída de um caso médio (ou seja, um circuito quântico aleatório) são tão difíceis como o pior caso (ou seja, o mais planeado).

“A ideia é que você possa usar o caminho de Cayley proposto no artigo para interpolar entre quaisquer dois circuitos arbitrários, que neste caso está entre o pior caso e o caso médio”, disse Movasagh. “Um caminho de Cayley é uma função algébrica de ordem inferior. Como o pior caso é conhecido por ser #P difícil (ou seja, um problema muito difícil), usando um caminho de Cayley pode-se interpolar o caso médio e mostrar que os circuitos estocásticos são essencialmente tão difíceis como o pior caso com alta probabilidade.”

Em contraste com outras provas matemáticas derivadas no passado, a prova de Movasagh não envolve quaisquer aproximações e é bastante simples. Isto significa que permite aos investigadores relacionar explicitamente os erros em questão e medir a sua robustez (ou seja, quão tolerantes a falhas são).

Desde que Movassagh apresentou as primeiras evidências, o seu grupo de investigação e outras equipas têm-nas testado e melhorado a sua robustez. Em breve poderá fornecer informações adicionais para estudos destinados a melhorar as evidências ou utilizá-las para destacar o potencial dos computadores quânticos.

“Percebemos evidências diretas da dificuldade de estimar as probabilidades de saída de circuitos quânticos, “Movassagh disse.” Isso fornece barreiras computacionais para simulações clássicas de circuitos quânticos.” Novas técnicas, como o caminho de Cayley e a versão da função racional de Berlekemp-Welsh “são de interesse independente para criptografia quântica, computação, complexidade e teoria criptográfica.” . Atualmente, este é o caminho mais promissor para refutar a Tese Estendida de Church Turing, que é um objetivo inevitável da teoria da complexidade quântica.”

O trabalho recente de Movasagh é em grande parte uma contribuição importante para os esforços de pesquisa em andamento para explorar as vantagens dos computadores quânticos sobre os computadores clássicos. Em seus estudos futuros, ele planeja desenvolver suas provas existentes para provar matematicamente o enorme potencial dos computadores quânticos para resolver problemas específicos.

“No meu próximo estudo, espero conectar este trabalho à dificuldade de outras tarefas, a fim de mapear melhor a tratabilidade dos sistemas quânticos”, acrescentou Movasagh. “Estou investigando aplicações deste trabalho em criptografia quântica, entre outras coisas. E por último, mas não menos importante, espero provar a conjectura da primazia quântica e provar que a tese estendida de Church-Turing é falsa!”