Approximate simulation of complex quantum circuits using sparse tensors

Resumo Técnico: Simulação Aproximada de Circuitos Quânticos Complexos Usando Tensores Esparsos

Declaração do Problema
A simulação de circuitos quânticos em computadores clássicos é essencial para definir o limite da vantagem quântica verificável, resolver problemas de muitos corpos quânticos e guiar o desenvolvimento de hardware. Embora os métodos de redes de tensores (ex: Estados de Produto de Matrizes, DMRG) tenham se tornado o estado da arte para simular circuitos complexos, eles frequentemente dependem de simetrias subjacentes ou baixa dimensionalidade para alcançar eficiência. Além disso, a simulação clássica geral é limitada pela teoria da complexidade ($P \neq NP$), impedindo simuladores universais de tempo polinomial. Os autores identificam a necessidade de ferramentas de simulação que possam aproximar estados quânticos sem exigir decomposição em valores singulares (SVD), simetrias subjacentes ou baixa dimensionalidade, visando especificamente circuitos onde as redes de tensores tradicionais podem enfrentar dificuldades.

Metodologia: Simulação de Tensor Esparso Truncado (TruSTS)
O artigo introduz o TruSTS, um método para simular aproximadamente circuitos quânticos usando tensores esparsamente povoados. A abordagem central envolve representar um estado quântico de $N$ qubits $|\psi\rangle$ como um estado esparso $|\phi\rangle$, que é uma combinação linear de $k$ estados de base ($k \le 2^N$).

• Estrutura de Dados: O estado esparso é armazenado usando dois arrays de comprimento fixo de tamanho $k$:
  1. $x[x_i]$: Um array de coordenadas inteiras representando as strings binárias dos estados de base.
  2. $\alpha[\alpha_i]$: Um array de amplitudes de probabilidade complexas correspondentes a esses estados de base.
  3. Um ponteiro inteiro nnz rastreia o número de elementos atualmente preenchidos.
• Algoritmo de Contração Bitwise: Para aplicar uma porta quântica (representada por um tensor $\hat{U}$), o algoritmo emprega uma estratégia de ordenação bitwise inspirada na multiplicação de matrizes de Linha de CSR (Compressed Sparse Row):
  1. Uma máscara de bits é definida para selecionar os qubits acoplados pela porta.
  2. O array do estado é ordenado com base nos bits "não acoplados" (o complemento da máscara). Isso agrupa estados de base em sub-arrays computacionalmente independentes onde a porta atua de forma idêntica.
  3. A porta é aplicada via contrações de matriz $4\times4$ independentes para cada sub-array.
  4. Este processo pode aumentar o número de termos não nulos (nnz) em um fator de até quatro por aplicação de porta.
• Truncamento: Para evitar o crescimento exponencial de nnz, o algoritmo trunca o estado de volta ao tamanho $k$ após cada porta. O artigo compara duas estratégias de truncamento:
  • Top-k: Retém os $k$ termos com as maiores amplitudes de probabilidade.
  • Random-k: Retém $k$ termos escolhidos aleatoriamente.
  • Um fator de renormalização $\gamma$ é aplicado a $|\phi\rangle$ para contabilizar a massa de probabilidade perdida durante o truncamento.

Contribuições Principais e Derivações Teóricas
Os autores derivam relações entre o parâmetro de renormalização $\gamma$ e a fidelidade de simulação $f = |\langle \psi | \phi \rangle|^2$.

• Limites de Fidelidade: Eles estabelecem que, para circuitos quânticos aleatórios, a fidelidade esperada $\bar{f}$ é aproximadamente $\gamma^2$ (a massa de probabilidade retida), com um leve desvio positivo devido a termos de interferência.
• Limites Superiores e Inferiores:
  • Um limite inferior $\bar{f}_{min} \approx 1/2^N$ é derivado para o caso em que o estado é truncado para um único estado de base aleatório.
  • Um limite superior $f_{max}$ é derivado assumindo que a distribuição de saída segue uma distribuição de Porter-Thomas. Este limite representa a melhor fidelidade possível se fosse possível identificar e manter as $k$ strings de bits mais prováveis após a execução do circuito, em vez de truncar no meio do circuito. O artigo nota que $f_{max} \approx d(1 - \ln d)$, onde $d = k/2^N$ é a fração de truncamento.

Resultados
Os autores testaram o TruSTS em circuitos quânticos aleatórios consistindo de unitárias de dois qubits de Haar-aleatórias organizadas em camadas.

• Fidelidade vs. Truncamento: Simulações em $N=24$ qubits mostram que a fidelidade do estado aproximado escala aproximadamente com o quadrado do fator de renormalização $\gamma^2$. O truncamento Top-k consistentemente supera o truncamento Random-k ao concentrar a probabilidade nos termos retidos.
• Escalonamento de Tempo de Execução:
  • Versus $k$: O tempo de execução por porta escala linearmente com o número de termos mantidos $k$.
  • Versus $N$: Para $k \ll 2^N$, o tempo de execução por porta é aproximadamente constante em relação ao número de qubits $N$ (testado até $N=64$). Isso indica que o algoritmo não introduz overhead dependente do tamanho total do espaço de Hilbert, desde que o estado permaneça esparso.
  • Memória: O método evita alocar a memória total de $2^N$, armazenando apenas $k$ termos.
• Comparação com MPS: Uma comparação preliminar com Estados de Produto de Matrizes (MPS) usando a biblioteca quimb em $N=24$ qubits (5 camadas) mostra que, para os parâmetros testados, o MPS oferece um tradeoff de tempo de execução-fidelidade mais favorável sobre a maior parte do intervalo de dados, mantendo uma fidelidade mais alta para tempos de execução comparáveis. No entanto, o TruSTS demonstra um decaimento constante e previsível na fidelidade conforme o tempo de execução aumenta, atingindo um limite inferior próximo a $f \sim 10^{-8}$.

Significância e Alegações
O artigo posiciona o TruSTS como uma ferramenta para estender as capacidades dos simuladores baseados em redes de tensores, particularmente para cenários onde:

1. A simetria está ausente: O método não depende de simetrias subjacentes ou baixa dimensionalidade.
2. SVD é evitado: Ele alcança o truncamento sem o custo computacional da Decomposição de Valores Singulares.
3. Existe esparsidade inerente: É atraente para estados quânticos que são inerentemente esparsos.

Os autores alegam que o TruSTS fornece um tradeoff útil entre fidelidade e tempo de execução, podendo encontrar aplicação imediata em circuitos onde a alta fidelidade não é estritamente necessária. Eles enfatizam que este trabalho serve como uma base para pesquisas futuras sobre a otimização de redes de tensores esparsos e para combinar o TruSTS com estratégias de otimização da ordem de contração de redes de tensores para expandir ainda mais o limite da simulação clássica para sistemas quânticos complexos. Os autores permanecem modestos, observando que comparações rigorosas com métodos alternativos e investigações usando quantidades mensuráveis (como fidelidade de entropia cruzada) são áreas importantes para trabalhos futuros.