Resource-Efficient Synthesis of Sparse Quantum States

Resumo Técnico: Síntese de Estados Quânticos Esparsos com Eficiência de Recursos

Problema
A preparação de estados quânticos é uma sub-rotina fundamental para inúmeros algoritmos quânticos, incluindo simulação de Hamiltoniana, solvers lineares e aprendizado de máquina. No entanto, preparar um estado arbitrário de $n$ qubits geralmente requer um tamanho de circuito de $\Omega(2^n)$, tornando-o ineficiente em termos de recursos para sistemas grandes. Embora muitas aplicações práticas exijam apenas estados esparsos (vetores com poucos entradas não nulas), os métodos de síntese existentes frequentemente falham em otimizar métricas críticas para a computação quântica tolerante a falhas (FTQC). Especificamente, na FTQC, portas não-Clifford (como portas T) são significativamente mais caras de implementar do que portas Clifford. Os métodos atuais para síntese de estados esparsos costumam apresentar contagens elevadas de portas não-Clifford ou profundidade de circuito excessiva, e poucos enfoques minimizaram explicitamente os recursos não-Clifford mantendo uma profundidade linear.

Metodologia
Os autores propõem uma nova metodologia que decompõe a síntese de um estado de $n$ qubits e $s$-esparso em duas tarefas distintas e otimizadas:

1. Geração de Estado W Pesado: A primeira etapa envolve a preparação de um estado W generalizado, $|W(\vec{\alpha})\rangle = \sum \alpha_i |e_i\rangle$, que codifica as amplitudes do estado esparso. O artigo apresenta duas estratégias de construção:

   • Construção Baseada em Árvore: Um método exato, sem ancilas, baseado em uma definição indutiva usando uma estrutura de árvore binária. Esta abordagem utiliza portas $RY(\theta)$ e alcança tamanho $O(n)$ e profundidade $O(\log n)$. Os autores analisam as condições sob as quais essas rotações podem ser compiladas para o conjunto Clifford+T, observando que estados W uniformes permitem reduções significativas de portas T.
   • Construção de Estado Completo: Uma abordagem alternativa que prepara um estado completo em $\lceil \log_2 n \rceil$ qubits e mapeia estados de base para a base do estado W. Este método aproveita resultados ótimos recentes para preparação de estado completo (Gosset et al.) para alcançar melhores contagens de T no regime tolerante a falhas, embora com requisitos de ancilas mais elevados.

2. Permutação via Circuitos Reversíveis Clássicos: A segunda etapa mapeia os estados de base $|e_i\rangle$ do estado W para os estados de base específicos do vetor alvo. Isso é modelado como um problema de permutação em strings binárias.

   • Eles reduzem isso à diagonalização de uma matriz binária $M_\chi$ usando operações elementares de linha correspondentes a portas reversíveis clássicas (X, CX, CCX).
   • Eles introduzem uma nova variante da eliminação de Gauss-Jordan que utiliza etapas de eliminação paralelas para minimizar a profundidade do circuito.
   • Uma otimização fundamental envolve o uso de circuitos Clifford adaptativos (envolvendo medições e portas controladas classicamente) para substituir portas Toffoli (CCX) caras quando o qubit alvo é garantidamente $|0\rangle$ após a operação. Isso permite que o circuito de permutação seja implementado com uma contagem T de $O(s)$ (ou contagem T zero com medições) e profundidade $O(s+n)$.

Principais Contribuições e Resultados

• Eficiência de Recursos: O algoritmo proposto sintetiza estados esparsos com uma contagem não-Clifford linear em relação à esparsidade $s$ ($O(s)$) e profundidade de circuito linear tanto na esparsidade quanto no número de qubits ($O(s+n)$). Isso melhora os métodos de estado da arte onde a profundidade é frequentemente $O(sn)$ ou as contagens não-Clifford são superlineares.
• Compilação Tolerante a Falhas: Ao serem compilados para o conjunto de portas Clifford+T, os autores fornecem três construções que oferecem trocas (trade-offs) entre contagem T, profundidade e contagem de ancilas.
  • A construção mais otimizada para T alcança uma contagem T de $O(\sqrt{s \log_2(1/\epsilon)} + \log_2(1/\epsilon))$. Os autores observam que isso coincide com os limites de otimalidade para preparação de estado completo por Gosset et al., sugerindo que a construção é provavelmente ótima para estados esparsos também.
• Otimização de Caso Especial: Para estados esparsos "T-uniformes" (onde as entradas não nulas estão no conjunto $\{e^{ik\pi/4}\}$), os autores demonstram uma síntese exata usando apenas $O(\sqrt{s})$ portas T com uma probabilidade de sucesso $> 1/2$, utilizando ancilas sujas (dirty ancillae).
• Técnica de Diagonalização de Matriz: O artigo contribui com um algoritmo específico para diagonalizar matrizes binárias usando operações paralelas de CX e CCX, que serve como o motor central para o circuito de permutação.

Significância
O artigo reivindica significância principalmente ao abordar o gargalo de recursos das portas não-Clifford na computação quântica tolerante a falhas. Ao desacoplar a preparação de amplitude (estado W) da permutação de base, os autores alcançam um método de síntese onde os recursos não-Clifford caros escalam linearmente com a esparsidade, em vez do número total de qubits. A profundidade do circuito também é melhorada para ser aditiva em $s$ e $n$, uma melhoria substancial sobre as dependências multiplicativas de trabalhos anteriores.

Os autores observam modestamente que, embora seu método seja altamente eficiente em contagem T e profundidade, ele pode exigir um número maior de qubits ancila em comparação com algumas abordagens existentes (especificamente $\max(s, n) - n$). Eles identificam a otimização de estruturas de árvore para maximizar operações amigáveis ao Clifford como um problema NP-difícil clássico (relacionado ao problema da partição) e sugerem que trabalhos futuros poderiam explorar a adaptação da lógica de circuitos reversíveis para restrições específicas de conectividade de hardware ou generalizar a abordagem para estados de Dicke.