Sparse quantum state preparation with improved Toffoli cost

Resumo Técnico: Preparação de Estados Quânticos Esparsos com Custo de Toffoli Aperfeiçoado

Enunciado do Problema
A preparação de estados quânticos é um primitivo fundamental na computação quântica, essencial para aplicações que variam desde resolvedores de sistemas lineares e aprendizado de máquina quântico até simulação quântica. Embora a preparação de estados genéricos tenha sido amplamente estudada, os estados quânticos esparsos — estados em $n$ qubits contendo apenas $s \ll 2^n$ estados de base computacional não nulos — requerem algoritmos especializados e eficientes.

Na computação quântica tolerante a falhas, a métrica de recurso primária é frequentemente o número de portas Toffoli (e portas T), pois estas operações não-Clifford são significativamente mais custosas de implementar do que as portas Clifford devido ao overhead da destilação de estados mágicos. As abordagens existentes para a preparação de estados esparsos geralmente se dividem em duas categorias:

1. Construção iterativa: Construir o estado em $s$ etapas, cada uma preparando um único estado de base. Isso normalmente incorre em um custo de Toffoli superior a $s \lceil \log(s) \rceil$.
2. Abordagem de duas etapas (Preparação Densa + Isometria): Primeiro prepara um estado denso em um sub-registrador de $\lceil \log(s) \rceil$ qubits, depois mapeia para o estado esparso alvo via uma isometria. A preparação de estados densos é bem otimizada (ex: via algoritmos de Grover-Rudolph), mas a etapa de isometria tem sido historicamente o gargalo. A arte anterior, como o método de Malvetti et al., exige um custo de Toffoli de pior caso de $s(\lceil \log(s) \rceil - 1)$ para a isometria, o que domina o custo total do algoritmo.

Metodologia
Os autores propõem um framework refinado de duas etapas (ilustrado na Figura 1) que otimiza a etapa de isometria e a integra com a preparação de estado denso:

1. Construção de Isometria em Lotes (Batched):
   A inovação central é um novo algoritmo clássico para construir o circuito de isometria. Em vez de aplicar portas multi-controladas-X individuais para zerar os qubits fora do subespaço para cada um dos $s$ estados (como feito por Malvetti et al.), os autores agrupam os estados em lotes de tamanho $m$, onde $m$ é a maior potência de dois que cabe no registrador disponível fora do subespaço ($m \le n - \lceil \log(s) \rceil$).

   • Para cada lote, o algoritmo transforma os estados em uma forma onde o registrador fora do subespaço contém um único $|1\rangle$ em posições distintas (ex: $|k\rangle_s |e_0\rangle_r, \dots, |k+m-1\rangle_s |e_{m-1}\rangle_r$).
   • Um circuito de Iteração Unária Parcial (PUI) é então aplicado para zerar simultaneamente os registros fora do subespaço para todo o lote.

2. Circuitos de Iteração Unária Parcial (PUI):
   Os autores introduzem duas variantes de circuitos PUI, que iteram sobre um intervalo específico $[l, r]$ de um registrador de endereço em vez do espaço total:

   • PUI Restrita: Garante que as unitárias sejam aplicadas apenas aos estados dentro do intervalo alvo $[l, r]$.
   • PUI Irrestrita: Permite que o circuito aplique unitárias não triviais a estados com valores de endereço maiores que $r$. Esta relaxação reduz significativamente a contagem de Toffoli. Os efeitos "indesejados" em valores de endereço superiores são rastreados classicamente e corrigidos em etapas ou lotes subsequentes.

3. Otimização Conjunta com Preparação de Estado Denso:
   Os autores analisam o compromisso entre o custo de isometria e o custo de preparação de estado denso. Eles propõem "terceirizar" certas subtarefas da preparação densa para o circuito de isometria:

   • Correções de Sinal: Em vez de descomputar o registrador de ângulos após a preparação densa (o que exige Toffolis adicionais para correção de sinal), a informação de sinal é codificada diretamente na isometria usando PUIs restritas.
   • Estados Reais: Para estados alvo com coeficientes puramente reais, a etapa de codificação de fase da preparação densa é inteiramente removida e tratada dentro da isometria, o que pode reduzir o custo de Toffoli da preparação densa em até um fator de três.

Principais Contribuições

• Algoritmo de Isometria Melhorado: Um novo algoritmo clássico (Algoritmo 1) que constrói circuitos de isometria com um custo de Toffoli de pior caso limitado por:
  $$\left\lceil \frac{s}{m} \right\rceil \left( 2m + \frac{\log(\tilde{s}/m)}{2} - 3 \right) + \log(\tilde{s}^2/m)$$
  onde $\tilde{s} = 2^{\lceil \log(s) \rceil}$. Isso representa uma melhoria de aproximadamente $\log(s)/2$ sobre o método de estado da arte de Malvetti et al.
• Variantes de PUI: A definição e análise de custo de circuitos de iteração unária parcial restritos e irrestritos. A versão irrestrita alcança contagens de Toffoli menores ao permitir "vazamento" de operações para valores de endereço superiores, o que é gerenciável no contexto da construção de isometria em lotes.
• Análise de Compromisso de Recursos: Uma análise abrangente (Tabela 1) dos custos combinados de Toffoli e qubits para a preparação de estado esparso, demonstrando como a otimização da isometria permite uma melhor utilização de qubits auxiliares (ancillas) para reduzir o custo da preparação densa, particularmente para estados de valor real.
• Implementação: Os circuitos são implementados no framework Qualtran, com o algoritmo clássico de busca de isometria otimizado usando código Rust acelerado por SIMD.

Resultados

• Limites Teóricos: O custo de Toffoli de pior caso para a isometria é reduzido de $O(s \log s)$ para aproximadamente $O(s)$ para $n$ suficientemente grande. Especificamente, o custo aproxima-se de $s$ em benchmarks numéricos em estados aleatórios, comparado ao melhor anterior de aproximadamente $s \log s$.
• Benchmarks Numéricos:
  • Para estados $s$-esparsos aleatórios, o número de Toffolis por $s$ aproxima-se de 1 conforme $n$ aumenta (Figura 2, direita).
    • Para estados puramente reais, a otimização conjunta reduz significativamente a contagem total de Toffolis em comparação com estados complexos genéricos (Figura 9).
  • O algoritmo clássico executa eficientemente, encontrando isometrias para $s=10^7$ estados em cerca de 10–20 minutos em hardware de CPU padrão.
• Comparação: O método proposto supera a literatura existente (ex: [4, 14, 20, 21]) em termos de contagem de Toffoli, mantendo um overhead de qubits comparável ou inferior.

Significância e Alegações
O artigo afirma apresentar os circuitos de preparação de estado esparso mais eficientes da literatura em termos de contagem de Toffoli e qubits. A significância reside em:

1. Remoção do Gargalo: Ao reduzir o custo da isometria de um fator dominante para um nível comparável à preparação densa, o algoritmo geral torna-se mais eficiente.
2. Escalabilidade: A abordagem escala favoravelmente com o número de qubits $n$, tornando-a adequada para algoritmos quânticos de larga escala onde $s$ é grande, mas $s \ll 2^n$.
3. Praticidade: O método é compatível com frameworks de estimativa de recursos de computação tolerante a falhas existentes (focando em contagens de Toffoli) e é implementado em um framework de software modular (Qualtran).

Os autores mantêm-se modestos quanto às implicações futuras, observando que, embora a contagem de Toffoli seja a métrica padrão atual, avanços na geração de estados mágicos (cultivo/destilação) podem deslocar o foco para métricas de tempo de execução no futuro. Eles também deixam em aberto a questão de se custos de Toffoli sublineares em $s$ são alcançáveis com recursos limitados de ancilla.