⚛️ quantum physics

On Certified Randomness from Fourier Sampling or Random Circuit Sampling

Este artigo propõe um protocolo de aleatoriedade certificada publicamente no modelo de oráculo quântico (QROM) utilizando amostragem de Fourier, alcançando segurança de caixa-preta sem pressupostos computacionais e fornecendo suporte teórico às conjecturas de Aaronson para amostragem de circuitos aleatórios.

Autores originais: Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, Avishay Tal

Publicado 2026-02-11

📖 4 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Roozbeh Bassirian, Adam Bouland, Bill Fefferman, Sam Gunn, Avishay Tal

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

O Mistério do Dado Quântico: Como Provar que algo é Realmente Aleatório?

Imagine que você está jogando um jogo de dados online com um estranho. Você quer ter certeza de que o dado que ele está jogando é um dado honesto e não um "dado viciado" (um dado que ele controla para sempre tirar o número que ele quer). O problema é: como você pode provar que o resultado foi puramente sorte, sem precisar confiar no estranho ou no computador dele?

Este artigo científico trata exatamente disso, mas no mundo da Computação Quântica.

1. O Problema: O "Truque do Mágico"

Na computação quântica, existem experimentos chamados "Amostragem de Circuitos Aleatórios". Eles são tão complexos que nem os supercomputadores mais potentes do mundo conseguem simular o que acontece. Para um cientista, se um computador quântico consegue fazer algo que nenhum computador clássico consegue, isso é um sinal de "vantagem quântica".

O problema é que um "mágico" (um computador malicioso) poderia tentar fingir que está fazendo esse experimento complexo, mas na verdade ele está apenas entregando números que ele mesmo escolheu. O artigo busca criar um "Certificado de Aleatoriedade": um método para você olhar para o resultado e dizer: "Eu não confio em você, mas os números que você me deu são tão estranhos e complexos que é impossível você tê-los inventado. Portanto, eles devem ser aleatórios."

2. A Solução: O "Teste do Som de uma Multidão" (Fourier Sampling)

Os autores propõem um novo método de teste usando algo chamado Amostragem de Fourier.

Imagine que você está em um estádio de futebol lotado. Se todos os torcedores estiverem gritando coisas aleatórias, o som será um "ruído branco" constante e bagunçado. Mas, se alguém começar a bater um tambor num ritmo específico, você vai ouvir um padrão surgindo no meio da bagunça.

O método de Fourier funciona como um "ouvido super apurado". Ele consegue detectar se os números que o computador quântico está entregando têm "ritmos" (padrões) escondidos.

Se o computador for honesto, ele vai entregar uma "bagunça" que segue as leis da física quântica (um tipo específico de ruído).
Se o computador for um trapaceiro tentando inventar números, ele vai acabar criando padrões que o "ouvido de Fourier" consegue detectar imediatamente.

3. A Grande Descoberta: A Prova Matemática

O que os pesquisadores fizeram de especial foi provar matematicamente duas coisas importantes:

O Teste é Infalível (no modelo de caixa preta): Eles provaram que, se um dispositivo passar no teste de Fourier, ele tem que ter gerado uma quantidade enorme de "entropia" (que é o nome chique para aleatoriedade pura). Não tem como o trapaceiro "fingir" que passou no teste sem realmente ser aleatório.
Apoio ao "Mestre" (Aaronson): Um cientista famoso chamado Scott Aaronson sugeriu uma ideia parecida antes, mas a ideia dele dependia de suposições muito difíceis de provar. Este grupo de pesquisadores conseguiu dar um "empurrãozinho" matemático, provando que a ideia de Aaronson faz sentido e é muito robusta, mesmo em cenários onde as regras são mais rigorosas.

4. Por que isso importa para você?

Pode parecer abstrato, mas isso é a base para o futuro da segurança digital. No futuro, poderemos usar isso para:

Loterias Públicas Invioláveis: Garantir que o vencedor de um prêmio foi escolhido pela sorte pura, e não por um hacker.
Criptografia: Criar chaves de segurança que são impossíveis de quebrar porque são geradas por uma aleatoriedade que ninguém consegue prever ou simular.
Sorteios de Criptomoedas: Garantir que a criação de novas moedas digitais seja justa.

Resumo da Ópera

Os autores criaram uma "régua" matemática para medir a honestidade de um computador quântico. Eles mostraram que, através de um teste de "ritmo" (Fourier), podemos certificar que os números gerados são verdadeiramente aleatórios, transformando a computação quântica de uma "caixa preta misteriosa" em uma ferramenta de confiança para o mundo real.

Resumo Técnico: Sobre Aleatoriedade Certificada via Amostragem de Fourier ou Amostragem de Circuitos Aleatórios

Este artigo aborda o problema da aleatoriedade certificada (certified randomness), um processo onde um dispositivo (que não é confiável) produz números que podem ser provados como aleatórios para um observador escéptico. O foco central é investigar a viabilidade de protocolos de aleatoriedade certificada pública utilizando dispositivos únicos de computação quântica de curto prazo (NISQ).

1. O Problema

A aleatoriedade certificada é crucial para aplicações como loterias públicas e criptografia. Recentemente, Scott Aaronson propôs um protocolo baseado em Amostragem de Circuitos Aleatórios (RCS). No entanto, a segurança desse protocolo depende de uma conjectura de complexidade não padronizada chamada Long List Quantum Supremacy Verification (LLQSV).

O desafio reside em determinar se é possível gerar aleatoriedade certificada sem depender de conjecturas customizadas e pesadas, ou se existem provas de que experimentos de "supremacia quântica" (como RCS ou Amostragem de Fourier) realmente geram entropia suficiente para ser certificada.

2. Metodologia

Os autores utilizam o Modelo de Oráculo Quântico Aleatório (QROM) para estudar o problema de forma "black-box" (caixa-preta). A metodologia divide-se em duas frentes principais:

Amostragem de Fourier (Fourier Sampling): Em vez de circuitos complexos, eles utilizam a amostragem do espectro de Fourier de funções booleanas aleatórias. Eles analisam a distribuição dos coeficientes de Fourier (que segue uma distribuição tipo Porter-Thomas) para verificar se os resultados obtidos são "pesados" (heavy) ou "leves" (light).
Análise de Complexidade e Separação de Classes: Para fornecer evidências para a conjectura de Aaronson, os autores utilizam técnicas de separação de classes de complexidade, especificamente tentando provar que certos problemas de distinção estão fora de BQP (computação quântica eficiente) e do PH (Hierarquia Polinomial). Eles estendem o trabalho de Raz e Tal sobre a separação de BQP vs PH.

3. Principais Contribuições e Resultados

O trabalho apresenta três contribuições fundamentais:

A. Protocolo de Aleatoriedade Certificada via Amostragem de Fourier:

Eles provam que qualquer dispositivo quântico que passe em um teste estatístico baseado em Amostragem de Fourier deve gerar uma quantidade linear de min-entropia.
Diferente de protocolos anteriores (como o de Yamakawa e Zhandry), o protocolo proposto pelos autores não depende de suposições computacionais para sua segurança no modelo QROM, embora a verificação clássica exija tempo exponencial.

B. Evidência Black-Box para a Conjectura LLQSV:

Os autores provam que o problema Black-Box LLQSV (distinguir se uma lista de amostras é aleatória ou provém de circuitos quânticos) não pode ser resolvido por algoritmos em BQP ou PH.
Isso fornece um suporte teórico robusto para a proposta de Aaronson, mostrando que, mesmo em um modelo simplificado, a tarefa de "trapacear" na geração de aleatoriedade é computacionalmente intratável para computadores clássicos e quânticos eficientes.

C. Introdução do Problema SquaredForrelation:

Eles introduzem um novo problema de separação de oráculo chamado SquaredForrelation. Este problema é mais fácil de implementar do que o clássico Forrelation, pois permite que uma parte do algoritmo seja clássica (consultando um oráculo $g$ de forma não sobreposta), o que o torna mais próximo de implementações experimentais reais. Eles provam que este problema também está fora do PH.

4. Significância

A importância deste trabalho reside em três pilares:

Fundamentação Teórica: Ele transforma uma conjectura "customizada" (LLQSV) em um problema de complexidade bem fundamentado, fornecendo evidências de que a vantagem quântica pode ser usada para gerar entropia real.
Viabilidade Experimental: Ao conectar a Amostragem de Fourier (um primitivo bem estudado) com a aleatoriedade certificada, o artigo abre caminho para que experimentos de supremacia quântica em dispositivos NISQ tenham utilidade prática imediata (como geradores de números aleatórios certificados).
Ponte entre Modelos: O trabalho preenche a lacuna entre o modelo de "caixa-preta" (teórico/oráculo) e o modelo de "caixa-branca" (implementação real de circuitos), sugerindo que a segurança observada em modelos matemáticos simplificados se traduzirá para sistemas físicos reais.

Resumo em uma frase: O artigo prova que a amostragem de Fourier pode gerar aleatoriedade certificada sem suposições computacionais no modelo QROM e fornece provas de complexidade que sustentam a validade de protocolos de supremacia quântica para fins de geração de entropia.