Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm

Resumo Técnico: Redução Algébrica para Melhorar um Algoritmo de Preparação de Estados Quânticos Otimamente Limitado

Enunciado do Problema
A Preparação de Estado Quântico (QSP) é um sub-rotina fundamental necessária para numerosos algoritmos quânticos, incluindo solucionadores de sistemas lineares, simulação de Hamiltoniana, química quântica e aprendizado de máquina. O principal desafio reside em minimizar a complexidade do circuito (profundidade, contagem de portas e contagem de CNOT) do operador unitário $U$ que mapeia o estado inicial $|0\rangle^{\otimes n}$ para um estado alvo desejado $|\psi\rangle = \sum c_i |i\rangle$. Embora o algoritmo de Sun et al. (SUN) seja conhecido por ser otimamente limitado em relação ao compromisso espaço-tempo assintótico (utilizando qubits ancilares para reduzir a profundidade), sua implementação envolve uma decomposição que utiliza três operadores do tipo $\Lambda$ para cada Porta Controlada Uniformemente (UCG). Este artigo aborda a oportunidade de reduzir a profundidade do circuito e as contagens de portas do algoritmo SUN através de uma decomposição algébrica mais eficiente, particularmente na faixa paramétrica onde o número de qubits ancilares $m$ satisfaz $2^n \leq m \leq 2^n/n$.

Metodologia
Os autores propõem um novo algoritmo de QSP, denominado OSUN, que introduz uma decomposição algébrica mais simples do operador unitário. A mudança metodológica central envolve a separação da preparação do estado desejado em dois blocos unitários distintos:

1. Parte Real ($U_{mod}$): Uma unitária responsável por preparar os módulos reais (amplitudes) dos coeficientes do estado alvo.
2. Parte Complexa ($D_{ph}$): Uma unitária diagonal responsável por aplicar as fases complexas necessárias.

No framework tradicional do SUN, cada UCG na estrutura de escada é decomposta em três operadores do tipo $\Lambda$ (lidando com deslocamentos de fase diagonais para componentes reais e complexos separadamente). O algoritmo OSUN proposto explora o fato de que $U_{mod}$ requer apenas a preparação de amplitudes reais. Ao restringir as UCGs neste bloco para matrizes bloco-diagonais $R_y$ e utilizando uma mudança específica de conjunto de portas ($R_y(\gamma) \equiv SH \cdot R_z(\gamma) \cdot HS^\dagger$), os autores demonstram que cada UCG na preparação da parte real pode ser implementada usando um único operador do tipo $\Lambda$ em vez de três. A informação de fase complexa é então aplicada ao final do circuito via um único operador $\Lambda$ de dimensão máxima.

Esta decomposição permite a paralelização das operações no registro ancilar usando o mesmo método de soma no espaço de Fourier de 5 estágios estabelecido em implementações anteriores do SUN, mas com um número reduzido de construtores $\Lambda$ por nível.

Principais Contribções
O artigo descreve seis contribuições específicas:

1. Otimização do SUN: Um novo algoritmo de QSP que melhora o algoritmo SUN em termos de profundidade e contagem de portas em toda a primeira faixa do compromisso espaço-tempo otimal definido em Sun et al. [40, Teorema 1].
2. Decomposição Algébrica: Uma derivação mostrando que a separação das partes real e complexa permite que cada UCG seja implementada com um único construtor do tipo $\Lambda$, reduzindo a contagem de três para um por nível de porta.
3. Limites Assintóticos Mais Estreitos: Uma análise formal fornecendo limites otimais assintóticos mais estreitos para o compromisso espaço-tempo na faixa paramétrica especificada.
4. Implementação: A implementação completa do algoritmo OSUN usando a biblioteca PennyLane, disponibilizada no GitHub.
5. Verificação Extensiva: Uma bateria abrangente de testes executados no sistema HPC da Universidade de Parma, cobrindo estados densos e esparsos, coeficientes aleatórios (reais positivos, reais negativos, complexos) e estados fisicamente relevantes (Bell, GHZ, W, Dicke) para contagens de qubits até 10.
6. Análise Comparativa: Uma comparação direta de desempenho com o algoritmo de Möttönen et al. (o padrão para QSP sem ancilas) e a implementação original do SUN, avaliando métricas como profundidade, total de portas, contagem de CNOT e tipos de portas.

Resultados
Os resultados de simulação indicam que o algoritmo OSUN alcança uma redução sistemática na profundidade do circuito em comparação com a implementação original do SUN.

• Análise de Complexidade: A análise teórica confirma que, embora a classe de complexidade assintótica permaneça $O(n^2 + 2^n/m)$, os prefatores dos termos dominantes são significativamente reduzidos. Especificamente, o termo log-linear ($n \log m$) mostra uma melhoria de fator 3, e o termo exponencial ($2^n/m$) mostra uma melhoria de fator 2.
• Métricas de Simulação: Para estados aleatórios com coeficientes complexos, o OSUN demonstra uma profundidade menor começando de 6 qubits em comparação tanto com o SUN original quanto com o algoritmo de Möttönen. A curva de crescimento da profundidade é mais suave que a da versão original.
• Contagem de Portas: Embora o OSUN reduza a profundidade, o número total de portas e CNOTs não apresenta redução em comparação ao algoritmo de Möttönen. No entanto, os autores observam uma mudança na composição do conjunto de portas: a abordagem de Möttönen utiliza CNOTs e rotações, enquanto o OSUN utiliza CNETs e deslocamentos de fase (operadores diagonais).
• Fidelidade: O algoritmo mantém alta fidelidade (próxima de 1) e baixa distância de traço em todos os tipos de estados e contagens de qubits testados (2 a 10).

Significância e Alegações
O artigo afirma que a redução algébrica proposta oferece uma melhoria prática ao algoritmo SUN de estado da arte sem alterar sua classe de complexidade assintótica fundamental. Ao reduzir os fatores constantes na profundidade e na contagem de portas, o OSUN fornece um circuito mais eficiente para a preparação de estados no regime onde qubits ancilares estão disponíveis ($m \geq 2^n$). Os autores posicionam este trabalho como um refinamento do compromisso espaço-tempo otimal, destacando que a redução no número de operadores $\Lambda$ (de 3 para 1 por UCG) é o principal motor do ganho de desempenho.

Os autores declaram explicitamente que esta otimização se aplica a toda a primeira faixa paramétrica do compromisso otimal. Eles sugerem que trabalhos futuros poderiam estender esses benefícios para outros pontos do domínio onde os registros ancilares crescem exponencialmente. O artigo conclui observando que, embora o OSUN melhore a profundidade, investigações futuras devem abordar a conectividade de qubits em hardware real e a tradução desses circuitos para o conjunto de portas Clifford+T para avaliar totalmente sua complexidade em contextos de tolerância a falhas. O trabalho não pretende resolver o problema geral de QSP para todas as restrições de hardware, mas oferece uma melhoria específica e verificada ao framework SUN usando estratégias de ancila existentes.