⚛️ quantum physics

Function-like pseudorandom unitaries generate pseudorandom quantum processes

Este artigo introduz unidades de funções pseudorandom (PRFUs), uma primitiva criptográfica que gera eficientemente famílias de operações quânticas reutilizáveis e de aparência aleatória indexadas por rótulos públicos a partir de uma única chave curta, estendendo assim a pseudorandomidade quântica de unidades individuais para processos quânticos complexos de múltiplos tempos seguros contra consultas adaptativas.

Autores originais: Zitai Xu, Rahul Arvind, Kishor Bharti, Tobias Haug, Dax Enshan Koh, Wai-Keong Mok, Andrew Tanggara, Alexey V. Gorshkov

Publicado 2026-10-02

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Zitai Xu, Rahul Arvind, Kishor Bharti, Tobias Haug, Dax Enshan Koh, Wai-Keong Mok, Andrew Tanggara, Alexey V. Gorshkov

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

No mundo quântico, a aleatoriedade não é apenas uma falta de padrão; é um recurso fundamental. Quando os físicos precisam modelar como um sistema quântico complexo se comporta, eles frequentemente imaginam uma evolução "perfeitamente aleatória", um processo tão caótico e imprevisível que mimetiza o comportamento de um lançamento de moeda verdadeiramente aleatório repetido bilhões de vezes. Este estado ideal de aleatoriedade, conhecido como uma unitária de Haar-aleatória, serve como um padrão ouro para compreender tudo, desde como a informação se espalha dentro de buracos negros até como computadores quânticos poderão eventualmente quebrar a criptografia. No entanto, há um problema: descrever ou construir tal processo perfeitamente aleatório requer uma quantidade de informação que cresce exponencialmente com o tamanho do sistema. Para um número mesmo modesto de partículas, as instruções necessárias para criar essa aleatoriedade tornam-se tão vastas que nenhum computador conseguiria armazená-las, muito menos executá-las.

Para resolver isso, os cientistas têm dependido há muito tempo de alternativas "pseudorandomas". Estas são processos que parecem aleatórios para qualquer observador que não possua a receita secreta, embora sejam gerados por um conjunto simples e curto de instruções. Até agora, essas ferramentas pseudorandomas eram limitadas. Elas podiam gerar um único evento de aparência aleatória, mas se um cientista precisasse de uma família inteira de eventos aleatórios distintos — talvez um para cada segundo de um experimento, ou um para cada endereço de memória diferente em um computador — ele teria que gerar uma nova e enorme chave secreta para cada um. Gerenciar uma biblioteca de milhares dessas chaves gigantes é impraticável. A questão era: poderia uma única chave secreta minúscula gerar um universo inteiro de processos quânticos distintos e de aparência aleatória, cada um acessível por um rótulo público simples, sem nunca revelar o segredo?

Uma equipe de pesquisadores respondeu agora a esta questão introduzindo um novo objeto matemático chamado uma unitária semelhante a uma função pseudorandoma. Pense nisso como uma chave mestra que, quando combinada com um rótulo público como um nome ou um número, produz instantaneamente uma operação quântica que parece completamente aleatória. Se você usar o mesmo rótulo duas vezes, obterá exatamente a mesma operação, garantindo consistência. Se usar um rótulo diferente, obterá uma operação completamente diferente que é tão aleatória quanto a primeira. Os pesquisadores provaram que este sistema é seguro contra até mesmo os computadores quânticos mais poderosos, o que significa que nenhum observador pode distinguir diferença entre as operações geradas e as ideais, perfeitamente aleatórias, desde que não possuam a chave mestra.

A equipe desenvolveu duas versões distintas desta ferramenta para lidar com diferentes formas de interagir com o sistema. Na primeira versão, o rótulo é uma peça padrão de informação clássica, como um número digitado em um computador. Aqui, os pesquisadores mostraram que, ao combinar uma função pseudorandoma segura com uma unitária pseudorandoma, poderiam criar um sistema onde a chave mestra deriva uma semente única para cada rótulo. Esta construção é robusta o suficiente para resistir a um adversário que possa solicitar o resultado de qualquer rótulo, em qualquer ordem, e até mesmo manter uma memória quântica das respostas anteriores para ajudar a adivinhar a próxima.

A segunda versão é mais sofisticada e lida com rótulos "coerentes". Neste cenário, o próprio rótulo pode existir em uma superposição quântica, o que significa que o sistema pode ser solicitado a aplicar uma operação aleatória a um rótulo que é simultaneamente "A" e "B" ao mesmo tempo. Este é um desafio muito mais difícil porque a interferência quântica entre esses diferentes rótulos poderia potencialmente revelar o segredo. Para resolver isso, os pesquisadores utilizaram uma técnica chamada registro de caminho indexado. Este método permite que eles rastreiem o histórico de cada consulta através de todos os possíveis rótulos simultaneamente, provando que, mesmo com essas consultas quânticas complexas, o sistema permanece indistinguível da verdadeira aleatoriedade.

As implicações deste trabalho estendem-se muito além da geração de números aleatórios. Os pesquisadores demonstraram que estas novas ferramentas podem ser usadas para construir canais quânticos pseudorandomos e "pentes quânticos" (quantum combs). Um pente quântico é uma forma de descrever uma sequência de eventos onde um sistema interage com seu ambiente ao longo do tempo, retendo uma memória privada entre os passos. Ao utilizar a sua nova ferramenta, a equipe mostrou que uma única chave pode gerar uma família inteira destes processos que evoluem no tempo. Isto significa que um sistema quântico pode simular um experimento complexo de múltiplos passos, onde as regras mudam a cada passo, tudo impulsionado por um único segredo curto.

Esta capacidade abre as portas para diversas aplicações práticas. Por exemplo, permite uma forma de autenticação quântica, onde uma mensagem é protegida por um código único que muda com base em um "nonce" ou número público. Se um atacante tentar reutilizar um número antigo, o sistema pode detectar e rejeitar a mensagem, garantindo que cada comunicação seja nova e segura. Também permite um novo tipo de acesso à memória quântica, onde dados podem ser recuperados de um banco de dados em uma superposição de endereços, mas a informação recuperada é mascarada por uma operação aleatória que depende do endereço. Isto esconde o conteúdo do banco de dados de qualquer pessoa que não possua a chave mestra, mesmo enquanto ela está realizando consultas em um estado quântico.

Além disso, os pesquisadores mostraram que esta abordagem de chave única pode gerar unitárias aleatórias para registradores de tamanhos variáveis. Em muitos algoritmos quânticos, o tamanho dos dados sendo processados pode mudar, mas anteriormente, uma nova chave era necessária para cada novo tamanho. Com este novo método, a mesma chave mestra pode gerar operações aleatórias para um registrador pequeno, um médio ou um grande, simplesmente alterando o rótulo público. Esta flexibilidade é crucial para construir sistemas quânticos escaláveis que precisam se adaptar a diferentes tarefas sem o overhead de gerenciar uma biblioteca massiva de chaves.

O trabalho também esclarece a relação entre diferentes tipos de aleatoriedade quântica. Embora já fosse conhecido como criar uma única unitária aleatória, e como criar uma família de estados quânticos aleatórios, criar uma família de unitárias aleatórias era uma peça faltante. Os pesquisadores preencheram esta lacuna, mostrando que a transição de uma única operação aleatória para uma família delas é possível, mas requer suposições criptográficas específicas que diferem dependendo se os rótulos são clássicos ou quânticos. Eles não apenas propuseram uma ideia teórica; eles forneceram construções matemáticas concretas e provas rigorosas de que estes sistemas funcionam sob as condições mais exigentes, incluindo ataques adaptativos onde um adversário aprende com cada interação.

Em última análise, esta pesquisa altera o paradigma de como pensamos na geração de aleatoriedade em sistemas quânticos. Em vez de tratar cada evento aleatório como um recurso separado e caro, trata a aleatoriedade como uma função que pode ser chamada repetidamente com diferentes entradas. Esta eficiência é vital para o futuro da criptografia e simulação quântica, onde a capacidade de gerar vastas quantidades de dinâmicas de aparência aleatória e reproduzíveis a partir de um único segredo é um pré-requisito para comunicações seguras e modelagem complexa. Os pesquisadores construíram efetivamente uma máquina que transforma uma única chave em um suprimento infinito de comportamentos quânticos únicos e aleatórios, seguros o suficiente para enganar até mesmo os observadores quânticos mais avançados.

Resumo Técnico: Unidades Pseudorandomas do tipo Função geram Processos Quânticos Pseudorandomas

Declaração do Problema

Unitárias de Haar-aleatórias servem como o modelo canônico para a evolução quântica aleatória genérica, fundamentando fenôios como desacoplamento, dispersão de informação (information scrambling) e criptografia quântica. No entanto, uma unitária de Haar-aleatória típica possui descrição e complexidade de circuito exponenciais, tornando-as inviáveis para implementação prática. Embora as unitárias pseudorandomas (PRUs) ofereçam um substituto eficiente para uma única evolução com aparência de aleatória, muitas tarefas criptográficas e físicas exigem uma família de operações independentemente aleatórias indexadas por um contexto público (ex: nonces, larguras de registrador ou passos de tempo).

Abordagens existentes para gerar tais famílias, como a amostragem de chaves PRU independentes para cada contexto, são impraticáveis devido ao overhead de gerenciamento de um conjunto de chaves secretas grande e dinamicamente crescente. Além disso, as PRUs padrão não fornecem inerentemente segurança contra consultas quânticas adaptativas onde um adversário interage com múltiplas instâncias da família. O artigo aborda a necessidade de um primitivo que gere uma família inteira de unitárias pseudorandomas adaptativamente endereçáveis a partir de uma única chave mestra curta, mantendo a segurança contra adversários que podem consultar a família de forma adaptativa e coerente.

Metodologia

Os autores introduzem as Unitárias do tipo Função Pseudorandoma (PRFUs), uma família chaveada $\{G_k(x)\}_{x \in \mathcal{X}_\lambda}$ onde uma única chave $k$ e um rótulo público $x$ determinam uma unitária eficientemente implementável. O objetivo de segurança é a indistinguibilidade computacional de uma família do tipo função de Haar-aleatória, onde cada rótulo $x$ mapeia para uma unitária de Haar-aleatória amostrada independentemente $H_x$ .

O artigo distingue dois modelos de acesso para o rótulo $x$ :

Acesso por rótulo clássico: O rótulo é fornecido como uma string de bits clássica. Os dados e os registradores de referência permanecem quânticos.
Acesso por rótulo coerente: O rótulo é fornecido em um registrador quântico $L$ , potencialmente em superposição ou emaranhado com outros registradores. O oráculo aplica uma unitária controlada $W_k = \sum_x |x\rangle\langle x|_L \otimes G_k(x)$ .

Construções

1. Construção de Rótulo Clássico:
Os autores propõem uma construção genérica combinando uma função pseudorandoma (PRF) pós-quântica $F_k$ e uma família de PRU de avanço adaptativo $\{V_a\}$ . A construção é definida como:
$G_k(x) := V_{F_k(x)}$
Aqui, a PRF deriva a semente $a = F_k(x)$ para a PRU interna. A prova de segurança utiliza um argumento de híbrido de "tabela diferida" (deferred table), processando os rótulos na ordem de sua primeira aparição. Um componente crítico é o uso de um proxy de Haar eficientemente implementável (derivado de designs de Permutação-Função-Clifford (PFC) de erro relativo amplificado) para simular híbridos intermediários. Isso permite que a redução limite a vantagem de distinção sem exigir que a PRU interna seja um proxy de Haar completo para todas as consultas possíveis, apenas para o número limitado de consultas feitas pelo adversário.

2. Construção de Rótulo Coerente:
Para o acesso coerente, os autores constroem uma PRFU diretamente usando um ensemble PFC indexado. Em vez de derivar chaves via uma PRF externa, o rótulo $x$ é incorporado diretamente nas primitivas de fase e permutação. A construção usa:

Uma função pseudorandoma quântica (qPRF) $g_{k_\Phi}(x, z)$ para a camada de fase.
Uma permutação pseudorandoma no lugar (in-place) ajustável (tweakable) $\Pi_{k_P}(x, z)$ para a camada de permutação.
Um 2-design unitário compartilhado $C$ .
A unitária resultante é $W_k^{coh} = \hat{P}_{\Pi} \hat{\Phi}_{g} (I_L \otimes C)$ .
A segurança é estabelecida usando uma técnica de registro de caminho indexado (indexed path-recording). Este método rastreia históricos de consulta envolvendo superposições de rótulos para analisar a interferência. A prova demonstra que o ensemble PFC indexado ideal é estatisticamente indistinguível de unitárias de Haar independentes até um limite de $2q(q-1)/(N+1)$ , onde $q$ é a contagem de consultas e $N=2^n$ . A segurança computacional segue ao substituir as primitivas aleatórias por suas contrapartes quânticamente seguras.

Extensões para Processos Quânticos

O artigo estende as PRFUs para gerar canais quânticos pseudorandomos e combos quânticos (processos com memória interna).

Canais: Ao aplicar uma PRFU dentro de uma dilatação de Stinespring e descartar o ambiente, os autores geram canais do tipo função pseudorandoma (PRFCs).
Combos: Ao atribuir rótulos distintos de PRFU aos sucessivos "dentes" (operações) de um combo quântico, os autores constroem combos pseudorandomos. Isso permite a emulação de dinâmicas multi-tempo com memória inacessível, segura contra intervenções adaptativas e sessões concorrentes.

Principais Contribuições

Definição de PRFUs: A formalização de unitárias do tipo função pseudorandomas, que geram uma família de unitárias com aparência de aleatórias indexadas por rótulos públicos a partir de uma única chave.
Construção e Segurança de Rótulo Clássico: Uma construção genérica a partir de PRFs pós-quânticas e PRUs, provada segura sob consultas de rótulo clássico adaptativas usando um argumento de híbrido e proxies de Haar.
Construção e Segurança de Rótulo Coerente: Uma construção específica baseada em ensembles PFC indexados usando qPRFs e qPRPs no lugar e ajustáveis. A segurança é provada via registro de caminho indexado para lidar com superposições de rótulos e interferência.
Elevação de Processo (Process Lifting): Demonstrações de que as PRFUs podem ser elevadas para gerar canais quânticos e combos quânticos pseudorandomos, protegendo processos com memória privada contra interações adaptativas e concorrentes.
PRUs de Largura Variável: Um método combinando PRFUs com colagem unitária (unitary gluing) para criar uma família de uma única chave de PRUs onde a largura do registrador pode ser escolhida adaptativamente após a geração da chave.
Aplicações: O artigo delineia aplicações específicas incluindo:
- Autenticação quântica com resolução de nonce.
- Consultas de QRAM mascaradas coerentemente (escondendo o conteúdo do banco de dados de observadores de acesso direto).
- Emulação eficiente de dinâmicas multi-tempo aleatórias.

Resultados

Limites de Segurança: Para rótulos clássicos, a vantagem de distinção é limitada pela soma da vantagem da PRF, a vantagem da PRU e um termo dependente do erro do proxy de Haar ( $2q\eta$ ). Para rótulos coerentes, a distância estatística para a família de Haar ideal é limitada por $2q(q-1)/(N+1)$ , com a segurança computacional dependendo da dureza da qPRF e qPRP subjacentes.
Eficiência: As construções são eficientes, exigindo apenas tempo polinomial e tamanho de circuito relativo ao parâmetro de segurança $\lambda$ e ao número de consultas.
Larguras Variáveis: A construção de colagem gera com sucesso unitárias pseudorandomas para larguras de registrador polinomialmente limitadas escolhidas após a geração, com a segurança preservada através das diferentes larguras.

Significância e Alegações

O artigo afirma estender o conceito de pseudorandomicidade quântica de operações individuais para famílias de dinâmicas quânticas com aparência de aleatórias geradas eficientemente. Ao introduzir as PRFUs, os autores preenchem a lacuna entre as PRUs de instância única e a necessidade de evoluções dependentes de contexto e reproduzíveis, necessárias em protocolos quânticos avançados.

O trabalho destaca que:

Paradigma de Chave Única: É possível derivar uma família inteira de unitárias pseudorandomas adaptativamente endereçáveis a partir de uma única chave mestra curta, evitando os problemas de gerenciamento de chaves da amostragem independente de PRUs.
Segurança Coerente: A segurança pode ser mantida mesmo quando os rótulos são consultados em superposição, um requisito mais forte do que a segurança de rótulo clássico, alcançado através de técnicas específicas de registro de caminho indexado.
Segurança de Processo: O framework se estende naturalmente para processos quânticos complexos (canais e combos) com memória interna, fornecendo segurança contra adversários que podem intervir entre os passos ou executar sessões concorrentes.

Os autores observam que, embora a relação entre as PRUs e as PRFUs seja clara para rótulos clássicos (via levantamento de PRF), a relação para rótulos coerentes permanece uma questão aberta, pois sua construção depende de primitivas específicas em vez de uma transformação geral a partir de uma PRU de instância única. Adicionalmente, a construção da qPRP no lugar e ajustável necessária a partir de suposições padrão permanece um problema concreto aberto para instanciação futura.