Random-Oracle Unitary Synthesis is Impossible

No mundo quântico, as leis fundamentais da física permitem uma variedade quase infinita de transformações. Imagine uma máquina que pode pegar uma peça de informação e torcê-la em qualquer forma, não importa quão complexa ou estranha. Essas transformações, conhecidas como unitárias, são os blocos de construção da computação quântica. No entanto, o fato de a natureza permitir uma transformação não significa que um computador possa construí-la. Existe um abismo vasto entre as unitárias que são fáceis de construir e aquelas que são efetivamente impossíveis de criar com a tecnologia atual. Por décadas, cientistas se perguntaram se esse abismo é real ou se é apenas uma lacuna em nosso entendimento. Especificamente, eles perguntaram se toda transformação difícil poderia ser construída simplesmente sabendo como computar uma função clássica específica e difícil. Se a resposta fosse sim, significaria que os problemas mais difíceis na computação quântica seriam tão difíceis quanto os problemas mais difíceis na computação clássica, ligando os dois mundos estreitamente. Se a resposta fosse não, sugeriria que a mecânica quântica detém segredos que a lógica clássica não pode desbloquear, potencialmente exigindo uma teoria de complexidade inteiramente nova.

Uma equipe de pesquisadores investigou agora essa questão mudando levemente as regras do jogo. Em vez de perguntar se um computador pode construir uma transformação específica usando uma função específica e complicada, eles perguntaram se um computador poderia construir uma transformação completamente aleatória e imprevisível usando apenas uma função aleatória e sem estrutura. Essa mudança permitiu que eles testassem os limites do que é possível quando os dados de entrada não possuem padrões ocultos para explorar. Suas descobertas são definitivas: é impossível sintetizar eficientemente uma transformação quântica verdadeiramente aleatória usando apenas uma função aleatória. Eles provaram que, não importa quão inteligente seja o algoritmo, se ele depender de uma função que foi escolhida ao acaso, ele falhará em criar o estado quântico desejado, a menos que faça um número astronômico de perguntas. Este resultado encerra um debate de longa data ao mostrar que a habilidade de construir estados quânticos complexos depende inteiramente da estrutura da informação fornecida. Sem essa estrutura, a tarefa permanece fora de alcance.

Os pesquisadores também exploraram um conceito relacionado usado na criptografia quântica chamado unitárias pseudorandom (pseudonaleatórias). Estas são transformações quânticas que parecem aleatórias para qualquer pessoa que não conheça a chave secreta usada para criá-las, embora tenham sido construídas por um processo simples e eficiente. Durante anos, os melhores métodos conhecidos para criar essas transformações aleatórias "falsas" foram limitados; eles só conseguiam enganar um observador que fizesse um número relativamente pequeno de perguntas. Os pesquisadores queriam saber se esse limite era um obstáculo técnico temporário ou uma lei fundamental da natureza. Eles construíram um novo método que cria com sucesso essas transformações de uma forma que permanece segura mesmo contra um observador fazendo um número muito maior de perguntas, especificamente até um número proporcional ao tamanho total do sistema. Isso é uma melhoria significativa em relação aos métodos anteriores, que só conseguiam lidar com um número de perguntas proporcional à raiz quadrada do tamanho do sistema.

No entanto, o trabalho deles também revelou um teto rígido. Embora pudessem levar a segurança dessas transformações aleatórias falsas muito mais longe do que antes, eles provaram que é impossível levá-la até o máximo teórico sem tornar o processo ineficiente. Eles demonstraram que, se um método for exigido como eficiente em termos do número de etapas que ele leva, ele não pode permanecer seguro contra um observador fazendo um número muito grande de perguntas. Isso cria uma fronteira precisa: você pode ter um método que é eficiente e seguro contra um número moderado de perguntas, ou pode ter um método que é seguro contra um número massivo de perguntas, mas não pode ter ambos ao mesmo tempo. Essa descoberta sugere que as limitações atuais na criptografia quântica não são apenas uma questão de esperar por melhores algoritmos; elas são provavelmente uma restrição fundamental do universo.

O estudo também abordou a questão mais ampla de se podemos algum dia construir uma máquina universal que possa sintetizar qualquer transformação quântica dado as instruções clássicas corretas. Ao mostrar que entradas aleatórias falham em produzir saídas aleatórias, os pesquisadores forneceram evidências fortes de que a estrutura da entrada é essencial. Não basta ter um computador poderoso e uma função aleatória; a função em si deve ser cuidadosamente projetada para guiar o computador em direção ao resultado desejado. Isso implica que a dificuldade de criar certos estados quânticos não é apenas uma questão de poder computacional, mas é intrínseca à natureza da informação necessária para descrevê-los. O trabalho efetivamente fecha a porta para a ideia de que um simples oráculo aleatório poderia servir como uma chave universal para desbloquear todas as possibilidades quânticas.

No fim, o artigo pinta um quadro de uma paisagem quântica onde eficiência e aleatoriedade estão em tensão. Os pesquisadores mostraram que, embora possamos criar imitações muito convincentes de aleatoriedade, existe um limite rígido para o quão boas essas imitações podem ser se quisermos manter o processo rápido. Eles também mostraram que a esperança de usar uma função aleatória simples para construir qualquer transformação quântica é infundada. Os resultados não oferecem apenas um novo algoritmo ou uma nova limitação; eles redefinem as fronteiras do que é possível no reino quântico. Eles nos dizem que a complexidade do mundo quântico não é uma ilusão que pode ser contornada por um truque inteligente, mas uma característica real que requer informações específicas e estruturadas para ser navegada. Para aqueles que constroem o futuro da tecnologia quântica, isso significa que o caminho a seguir exige não apenas mais poder, mas um design mais preciso. O universo, ao que parece, exige que saibamos exatamente o que estamos pedindo antes que ele nos dê a resposta.