Efficient classical algorithm for estimating linear statistics of Boson Sampling

Enunciado do Problema
O Amostragem de Bósons (Boson Sampling) é um forte candidato para demonstrar vantagem computacional quântica; no entanto, sua utilidade prática é dificultada pelo tamanho exponencial do espaço de resultados e pelas propriedades de anti-concentração da distribuição. Para utilizar a Amostragem de Bósons para estimar observáveis físicos ou realizar tarefas computacionais, deve-se "granular" (coarse grain) a distribuição de resultados. Embora as probabilidades de resultados individuais sejam #P-difíceis de calcular exatamente, muitas aplicações propostas exigem apenas a estimativa de observáveis físicos específicos ou probabilidades agrupadas dentro de um erro aditivo. Uma questão aberta crítica permanece: quais tipos de distribuições granuladas podem ser simulados eficientemente de forma clássica, e quais retêm a dureza quântica? Especificamente, o artigo aborda a complexidade de estimar estatísticas lineares — distribuições de probabilidade derivadas de funções lineares dos números de ocupação de fótons de saída — e investiga se estas podem ser aproximadas eficientemente de forma clássica, potencialmente minando certas propostas criptográficas ou unificando algoritmos existentes inspirados em computação quântica.

Metodologia
Os autores desenvolvem um algoritmo clássico eficiente baseado na decomposição de Fourier de probabilidades de grupo. A metodologia central envolve as seguintes etapas:

1. Definição de Estatísticas Lineares: O artigo define uma estatística linear como a distribuição de probabilidade de valores $k = \omega \cdot s$, onde $s$ é o vetor de ocupação de fótons de saída e $\omega$ é um vetor de pesos de inteiros não negativos. Os resultados são agrupados em compartimentos (bins) $B_j$ baseados em intervalos contíguos desses valores.
2. Conexão com a Função Característica: Os autores relacionam a função característica das estatísticas lineares, $\chi_\omega(\theta) = \mathbb{E}[e^{i\theta f_\omega(s)}]$, à amplitude de transição de um circuito de óptica linear. Especificamente, mostra-se que $\chi_\omega(\theta)$ é igual ao valor esperado $\langle t | \hat{V}_{\Omega, \theta} | t \rangle$, onde $\hat{V}_{\Omega, \theta}$ é um operador de interferômetro linear associado à unitária $V_{\Omega, \theta} = U^\dagger e^{i\theta \Omega} U$.
3. Estimativa de Fourier: Usando a transformada de Fourier discreta, a função de distribuição cumulativa (CDF) $S(x) = \Pr[f_\omega(s) \leq x]$ é expressa como uma expectativa sobre um conjunto discreto de valores da função característica.
4. Amostragem por Importância: Para estimar a CDF eficientemente, os autores empregam uma distribuição de amostragem por importância $q(k)$ que escala como $1/k$. Isso garante que o intervalo do estimador permaneça polinomialmente limitado ($O(\log N)$), permitindo a estimativa clássica eficiente da CDF para um erro aditivo inverso-polinomial.
5. Extensão para Entradas Gerais: O framework depende da capacidade de computar ou aproximar eficientemente a função característica. Os autores demonstram que isso é possível para várias entradas de estados, incluindo estados de Fock, estados Gaussianos (vácuos espremidos deslocados) e fótons parcialmente distinguíveis, ao aproveitar algoritmos existentes para amplitudes de transição (por exemplo, baseados em permanentes de matrizes ou Hafnians).

Contribuições Principais e Resultados

• Algoritmo Clássico Eficiente: O artigo apresenta um algoritmo clássico randomized que estima a distribuição cumulativa de estatísticas lineares para Amostragem de Bósons com $n$ fótons e $m$ modos em tempo esperado polinomial em $m$, $\epsilon^{-1}$ e $\log(1/\delta)$. Isso se aplica a uma ampla classe de estados de entrada, incluindo estados de Fock e estados espremidos (squeezed states).
• Unificação de Resultados Existentes: O algoritmo unifica resultados recentes sobre simulações clássicas eficientes de espectros vibrônicos moleculares e aproximações eficientes de distribuições granuladas baseadas em binning de detectores sob um único framework de estatísticas lineares.
• Implicações Criptográficas: Os autores aplicam seu algoritmo ao problema do "compartimento mais provável" (most probable bin), um componente central de uma proposta de função de via única baseada em Amostragem de Bósons. Eles demonstram que este problema específico pode ser avaliado classicamente com a mesma eficiência de executar o experimento, mostrando assim que esta proposta criptográfica específica não oferece uma vantagem quântica sobre a simulação clássica.
• Robustez ao Ruído: O framework incorpora naturalmente imperfeições experimentais, como perda de fótons e distinguibilidade parcial, modificando a função característica sem aumentar a complexidade computacional da simulação.
• Limitações e Questões Abertas: O artigo afirma explicitamente que suas técnicas não se aplicam a estatísticas não lineares ou estratégias de binning que envolvam permutações ou pós-processamento não linear (por exemplo, tratar eventos livres de colisões de forma diferente). Eles conectam a simulação de estatísticas não lineares (especificamente funções quadráticas) ao problema aberto de computar amplitudes de transição em circuitos de óptica linear com uma única camada de interações fóton-fóton (interações Kerr).

Significância
O artigo estabelece um limite claro para a simulabilidade clássica de aplicações de Amostragem de Bósons. Demonstra que uma ampla classe de problemas granulados, definidos por funções lineares da saída, não fornece vantagem quântica, pois podem ser aproximados eficientemente de forma clássica. Este resultado desafia a viabilidade de certas propostas criptográficas baseadas em Amostragem de Bósons, enquanto simultaneamente valida a eficiência de algoritmos inspirados em computação quântica para espectroscopia molecular e validação de dispositivos. O trabalho deixa em aberto a questão da simulabilidade clássica para estatísticas não lineares, sugerindo que a dureza desses problemas pode estar intrinsecamente ligada à complexidade de simular interações ópticas não lineares de camada única. Os autores enfatizam que, embora seu método exija assintoticamente mais amostras do que um experimento ideal para certos parâmetros, o tempo de execução clássico para experimentos de tamanho finito pode ser significativamente menor do que o tempo necessário para obter amostras suficientes do hardware quântico ruidoso atual.