Quantum Counting in the Rydberg Blockade

Resumo Técnico: Contagem Quântica no Bloqueio de Rydberg

Definição do Problema
Contar o número de soluções para problemas combinatórios, como a satisfatibilidade booleana (SAT), é uma tarefa fundamental na inteligência artificial, confiabilidade de redes e física estatística. No entanto, a contagem exata para instâncias difíceis pertence à classe de complexidade #P, que é considerada intratável para computadores clássicos. Embora a contagem aproximada via amostragem seja uma alternativa viável, ela requer a capacidade de amostrar soluções de forma quase uniforme. Métodos clássicos baseados em amostragem frequentemente lutam para alcançar essa uniformidade de maneira eficiente. Além disso, abordagens quânticas existentes, como as baseadas em iterações de Grover, exigem profundidades de circuito que crescem exponencialmente com o número de variáveis, tornando-as inacessíveis para os atuais processadores quânticos de escala intermediária ruidosa (NISQ).

Metodologia: RydCount
Os autores propõem o RydCount, um algoritmo de contagem aproximada baseado em amostragem projetado nativamente para computadores quânticos de átomos neutros (NAQCs). O algoritmo visa fórmulas de 2-satisfatibilidade (2SAT) plana.

1. Codificação Física: O algoritmo mapeia variáveis booleanas para registradores atômicos presos em pinças ópticas. As restrições de 2SAT são impostas via bloqueio de Rydberg. Especificamente, o sistema evolui sob um Hamiltoniano de Rydberg onde a excitação simultânea de átomos vizinhos próximos no estado de Rydberg é energeticamente proibida. Essa restrição física codifica naturalmente a fórmula 2SAT monótona $\phi_G(x) = \bigwedge_{(i,j) \in E} (\neg x_i \lor \neg x_j)$, onde o subespaço de baixa energia corresponde ao espaço de soluções da fórmula.
2. Protocolo de Amostragem: A sub-rotina central, RydSamp, envolve a preparação de um estado de base computacional inicial (tipicamente $|0\rangle^{\otimes n}$), a aplicação de um "quench" via um pulso de laser estático por um tempo de evolução aleatório $t \in [t_{min}, t_{max}]$, e a medição do estado resultante na base computacional.
3. Mecanismo de Feed-Forward (FF): Para melhorar a uniformidade da amostragem, o algoritmo utiliza um protocolo de feed-forward. Se uma string de bits medida for uma solução válida, ela é retroalimentada como o estado inicial para a próxima iteração. A análise teórica sugere que, para estados iniciais genéricos, a dinâmica caótica do Hamiltoniano de Rydberg espalha a amplitude do estado pelo espaço de Hilbert acessível, levando a uma distribuição quase uniforme sobre o conjunto de soluções após um número suficiente de passos de FF ($k$).
4. Contagem por Autorredução: O algoritmo segue o arcabouço de Jerrum-Valiant-Vazirani (JVV). Ele fixa iterativamente as variáveis para seu estado de máxima verossimilhança com base nas amostras coletadas, reduzindo o tamanho do problema a cada passo. A estimativa final é o produto dos recíprocos dessas probabilidades observadas.

Principais Contribuições e Resultados

• Viabilidade Teórica: Os autores demonstram que a representação do bloqueio de Rydberg preserva a autorredução necessária para a contagem JVV. Eles mostram que, embora o Hamiltoniano de Rydberg não produza uma distribuição perfeitamente uniforme devido ao bloqueio imperfeito e às caudas de interação de longo alcance, ele alcança uma amostragem "quase uniforme" ($n\eta \lesssim 1$) para instâncias com até $n \approx 10^4$ variáveis usando um número polinomial de passos de FF.

• Simulações Clássicas:

  • Grades 1D e 2D: Simulações em cadeias 1D e grades triangulares 2D mostram que a contagem estimada converge para um valor dentro de um fator multiplicativo constante do número exato conforme o número de amostras aumenta.
  • Análise de Viés: Os autores identificam um viés sistemático em grades 2D e grades pontuadas causado por interações de vizinho próximo-vizinho, que penalizam estados de alto peso de Hamming. Isso leva a uma subestimação da probabilidade de as variáveis estarem no estado $|1\rangle$, resultando em uma superestimação sistemática da contagem total. Consequentemente, o algoritmo atua como um limite superior eficaz sobre a contagem exata nesses cenários, em vez de uma estimativa precisa dentro de um fator multiplicativo.
  • Grades Pontuadas: Para grades 2D "pontuadas" aleatórias (onde sítios são removidos), o algoritmo converge para dentro de um fator de $1.1$ do número exato para baixas densidades de lacunas. Os autores observam que solvers clássicos como o GANAK exibem escalonamento de tempo exponencial para essas instâncias, sugerindo a existência de instâncias de #2SAT classicamente difíceis dentro deste conjunto de grafos, embora não aleguem que o RydCount seja mais rápido ou superior em tempo de execução.

• Demonstração Experimental: Os autores implementaram uma variante híbrida simplificada do RydCount no NAQC Pasqal Orion Alpha. Devido a limitações de hardware (falta de endereçabilidade seletiva de átomos), eles não puderam realizar a autorredução iterativa completa. Em vez disso, eles:

  1. Utilizaram uma amostragem de etapa única ($k=1$) a partir do estado fundamental.
  2. Pré-selecionaram um separador de grafo para decompor o problema de 81 variáveis em dois subproblemas menores.
  3. Resolveram os subproblemas classicamente e os combinaram com o fator multiplicativo derivado do quantum via o separador.
  4. Avaliaram dois caminhos de decimação (fixando as variáveis em 0 ou 1) para estabelecer limites superiores e inferiores.

  Resultos Experimentais: Para uma instância de grade planar de 81 variáveis, os shots brutos do hardware produziram estimativas dentro de um fator multiplicativo de 5 (para o caminho $x_c=1$) e 1.01 (para o caminho $x_c=0$) da contagem exata. A pós-seleção apenas de strings de bits de soluções válidas melhorou o caminho $x_c=0$ para dentro de um fator de $<1.25$. Os dois caminhos conseguiram delimitar a contagem exata.

Significância e Perspectivas
O artigo afirma que o RydCount representa uma abordagem viável de curto prazo para contagem aproximada em dispositivos NISQ. Sua significância reside em:

1. Implementação Nativa: Utiliza a física natural dos NAQCs (bloqueio de Rydberg) para impor restrições, evitando os circuitos profundos exigidos por algoritmos quânticos baseados em portas lógicas.
2. Escalabilidade: O protocolo mostra-se capaz de funcionar para tamanhos de problema ($n=81$) que são desafiadores para processadores quânticos atuais que não sejam de recozimento (annealing) e que se aproximam dos limites de solvers clássicos de última geração para conjuntos de grafos específicos.
3. Potencial Futuro: Os autores observam que, embora as taxas de clock atuais sejam baixas (<10 Hz), melhorias futuras para 100 Hz, combinadas com a capacidade de aprisionar milhares de átomos e implementar endereçabilidade seletiva (já demonstrada em laboratórios acadêmicos), poderiam posicionar o RydCount como uma alternativa competitiva para problemas #P-hard. O uso de cadeias de átomos para codificar grafos bipartidos 3-regulares planares sugere que o método poderia ser estendido para instâncias #P-completas.

Os autores mantêm-se modestos, reconhecendo que a demonstração experimental atual é uma variante híbrida simplificada e que vieses sistemáticos devido a interações de longo alcance devem ser mitigados (por exemplo, via melhor força de bloqueio ou endereçabilidade) para alcançar estimativas precisas em vez de apenas limites.