Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

Resumo Técnico: Limites Inferiores de Consulta Estritos para Amostragem Quântica, com uma Aplicação para Aleatoriedade Certificada

Enunciado do Problema
Experimentos de amostragem de circuitos aleatórios são as principais demonstrações de vantagem computacional quântica, tipicamente verificadas usando o benchmark de cross-entropia linear (XEB). O escore XEB mede o quão bem a distribuição de saída de um dispositivo se alinha com a distribuição ideal $p$ calculando a média de $N p(z)$ para as strings $z$ retornadas, onde $N=2^n$. Embora um escore alto sugira vantagem quântica, ele não certifica inerentemente que o dispositivo amostrou de $p$ ou que a saída é aleatória. Um dispositivo poderia alcançar um escore alto ao produzir deterministicamente a string mais provável (que um adversário poderia conhecer), falhando assim em produzir aleatoriedade certificada.

Este artigo aborda duas questões fundamentais no modelo de consulta quântica:

1. Limites de Escore: Quão alto um dispositivo quântico eficiente pode pontuar em relação ao escore ideal? Especificamente, um dispositivo eficiente pode exceder o escore ideal por uma constante?
2. Certificação de Aleatoriedade: Se um dispositivo atinge um escore próximo ao ideal, quanta entropia mínima suave (aleatoriedade certificada) sua saída contém, mesmo contra um adversário (Eve) que pode estar emaranhado com o dispositivo e aprende o oráculo (o circuito ou função) posteriormente?

Metodologia
Os autores trabalham no modelo de consulta, onde o circuito é substituado por um oráculo extraído de um conjunto conhecido. Eles analisam dois conjuntos específicos:

• Amostragem de Fourier: O oráculo é uma função aleatória uniforme $f: \{0,1\}^n \to \{\pm 1\}$. O amostrador honesto pontua aproximadamente 3.
• Estados Aleatórios de Haar: O oráculo esconde um vetor unitário uniformemente aleatório $|\phi\rangle$ (acessado via um oráculo de preparação de estado canônico ou acesso a uma unitária aleatória de Haar). O amostrador honesto pontua aproximadamente 2.

A metodologia central envolve a definição de uma medida de progresso $\lambda$ que quantifica o desvio do estado de um dispositivo em relação ao estado "honesto" (que realiza uma única consulta). A análise segue um framework de três etapas:

1. Limite de Escore: O escore esperado $B(A)$ é limitado em termos da medida de progresso: $B(A) \leq \text{Escore Ideal} + O(\lambda + \lambda^2)$.
2. Limite de Crescimento: Demonstra-se que cada consulta aumenta $\lambda$ em apenas $O(\sqrt{(t+1)/N})$, onde $t$ é o número de consultas anteriores. Consequentemente, após $q$ consultas, $\lambda = O(q^{3/2}/\sqrt{N})$.
3. Extração de Aleatoriedade: Para dispositivos com escores próximos ao ideal (pequeno déficit $\delta$), a prova do limite de escore é refinada para mostrar que os ramos de saída do dispositivo estão próximos de vetores auxiliares específicos. Esses vetores são gerados por operadores que atuam apenas no dispositivo, com normas limitadas por $\text{poly}(q)\sqrt{p(z)}$. Esta estrutura implica que a capacidade de Eve de adivinhar a saída é limitada, mesmo que ela conheça o oráculo.

Contribuições Principais e Resultados

1. Limites Inferiores Estritos para Exceder o Escore Ideal
O artigo estabelece que o escore ideal atua como um "limite de Tsirelson" para dispositivos quânticos eficientes nestas tarefas de amostragem.

• Complexidade de Consulta: Um algoritmo quântico para exceder o escore ideal por uma constante $\epsilon$ requer $\Omega(N^{1/3})$ consultas.
  • Para amostragem de Fourier, um escore esperado de $3 + \epsilon$ requer $q \geq \Omega(N^{1/3})$.
  • Para estados aleatórios de Haar, um esscore esperado de $2 + \epsilon$ requer $q \geq \Omega(N^{1/3})$.
• Limites Superiores: Os autores confirmam que $O(N^{1/3})$ consultas são suficientes para exceder o escore ideal por uma constante usando um "algoritmo de quadratura" (uma variante do algoritmo de busca de colisões). Este algoritmo armazena $m \approx N^{1/3}$ amostras ideais e usa amplificação de amplitude para enviesar a saída em direção ao quadrado da distribuição ideal, $p(z)^2$.
• Estreiteza (Tightness): Estes limites são estritos; a lacuna entre o amostrador honesto (1 consulta) e a capacidade de exceder significativamente o escore ideal é caracterizada exatamente pelo limiar de $N^{1/3}$.

2. Aleatoriedade Certificada no Escore Ideal
O artigo prova que um dispositivo que realiza um número polinomial de consultas e atinge um escore dentro de $o(1)$ do ideal produz uma saída com aleatoriedade quase máxima.

• Entropia Mínima: Para amostragem de Fourier e estados aleatórios de Haar (via oráculo canônico), a saída $Z$ possui entropia mínima suave $H_{\min}^\eta(Z | RE) \geq n - O(\log n)$, onde $R$ é o oráculo e $E$ é o registro de Eve.
• Modelo Adversarial: Isso se mantém mesmo se Eve estiver emaranhada com o dispositivo e aprender a descrição completa do oráculo (a função $f$ ou o vetor $\phi$) após o dispositivo gerar $Z$.
• Parâmetros: O parâmetro de suavização $\eta$ escala como $O(\sqrt{\delta} + q^{3/4}N^{-1/4})$. Se o déficit $\delta$ for desprezível e $q$ for polinomial em $n$, a suavização é desprezível, certificando $n - O(\log n)$ bits de aleatoriedade.
• Otimalidade: A perda de $O(\log n)$ é mostrada como sendo quase ótima. O artigo constrói dispositivos usando amplificação de amplitude que alcançam escores próximos ao ideal, mas restringem a saída a um conjunto conhecido de tamanho $N/q^2$, limitando a entropia mínima a $n - 2\log q$.

3. Resultados Adicionais

• Distribuição de Colisão: O artigo mostra que amostrar a distribuição de colisão (proporcional a $p(z)^2$) tem uma complexidade de consulta de $\Theta(N^{1/3})$.
• Produtos de Hadamard Quânticos: Um algoritmo de quadratura coerente é apresentado para preparar o produto de Hadamard quântico de dois estados com magnitudes de amplitude uniformes. Este algoritmo atinge um erro de distância de traço de $O(N^{-1/6})$ usando $O(N^{1/3})$ consultas, melhorando sobre as $\sqrt{N}$ consultas exigidas pela amplificação de amplitude padrão.

Significância e Alegações
O artigo afirma fornecer garantias incondicionais e de informação teórica para tarefas de amostragem quântica, resolvendo questões abertas sobre a "desigualdade de Tsirelson da supremacia quântica".

• Analogia com CHSH: Os resultados traçam um paralelo direto com o jogo CHSH. Assim como o limite de Tsirelson ($\cos^2(\pi/8)$) limita a probabilidade de vitória de estratégias quânticas e certifica a aleatoriedade nesse limite, o escore XEB ideal limita o desempenho de amostradores quânticos eficientes e certifica a aleatoriedade próximo a esse escore.
• Segurança Incondicional: Diferente de resultados anteriores que dependiam de suposições de dureza computacional ou de um conhecimento restrito do adversário (ex: não aprender o oráculo completo), este trabalho fornece limites incondicionais contra um adversário que aprende o oráculo e detém emaranhamento arbitrário.
• Limitações: Os autores observam que seus resultados se aplicam ao modelo de oráculo. Para dispositivos do mundo real (como os de [AAB+19]), os escores atuais estão longe do ideal (ex: 1.002 vs 2), o que significa que as garantias atuais para aleatoriedade certificada em configurações experimentais dependem de outras suposições mais fracas (ex: [AH23]). Além disso, para estados aleatórios de Haar, o resultado requer o oráculo de preparação de estado canônico em vez de acesso a uma unitária completa, pois um adversário que aprenda uma unitária de Haar completa poderia potencialmente correlacionar as saídas com as colunas da unitária.

Em resumo, o artigo define rigorosamente os limites da amostragem quântica eficiente, provando que o escore ideal é uma barreira difícil para dispositivos eficientes e que aproximar-se dessa barreira certifica quase toda a aleatoriedade, mesmo contra adversários quânticos poderosos.