Conditioning-Free Non-Uniform Quantum Fourier and Chebyshev Transforms

Problema

O artigo aborda o desafio de computar eficientemente a Transformada de Chebyshev Não Uniforme (NUCT) em um computador quântico. A NUCT mapeia uma função $f$ definida em nós equiespaçados $x_k \in [-1, 1]$ para sua projeção sobre polinômios de Chebyshev $T_j(x)$.

• A Dificuldade: Embora a Transformada de Chebyshev Discreta clássica sobre nós de Chebyshev (que são não uniformes em $x$, mas uniformes no ângulo $\theta = \arccos x$) se reduza a uma DFT (Transformada Discreta de Fourier) padrão, a NUCT sobre nós $x$ equiespaçados corresponde a uma DFT em ângulos não uniformes $\theta_k = \arccos(x_k)$.
• Limitações Anteriores: Abordagens quânticas anteriores, como a Transformada de Fourier Quântica Não Uniforme (NUQFT) de [AKY26], dependem de uma fatoração de baixo posto da matriz de transformação. No entanto, os limites de erro dos métodos existentes dependem de um parâmetro dependente da geometria $\kappa$, definido como o máximo de $1/\sqrt{1-(y^*)^2}$, onde $y^*$ é um ponto intermediário no teorema do valor médio aplicado à função $\arccos$. Para nós próximos às fronteiras da grade (onde $y^* \to \pm 1$), $\kappa$ pode tornar-se arbitrariamente grande, potencialmente destruindo as garantias de eficiência do algoritmo. Além disso, trabalhos anteriores frequentemente assumiam a existência de "oráculos de acesso à linha" para as matrizes esparsas subjacentes sem construção explícita.

Metodologia

Os autores propõem uma NUQFT Livre de Condicionamento (Conditioning-Free NUQFT) e aplicam-na à NUCT através das seguintes etapas metodológicas:

1. Tratamento de Ponto Fixo Exato: Em vez de tratar os valores armazenados dos nós como aproximações ruidosas de números reais, o algoritmo trata as representações de ponto fixo de $m$ bits $\tau_k$ como os nós de entrada exatos para a transformação. A matriz de transformação $F_\tau$ é construída a partir desses valores armazenados exatos.
2. Decomposição de Erro: O erro total é dividido em dois componentes independentes:
   • Erro de Implementação: A diferença entre o circuito implementado e a transformação nos nós armazenados ($F_\tau$).
   • Erro de Nó: A diferença entre a transformação nos nós armazenados ($F_\tau$) e os nós reais alvo ($F_t$).
3. Remoção de $\kappa$:
   • Na análise do erro de implementação, o algoritmo computa $\arccos$ sobre o deslocamento (offset) exato armazenado $z_j$. Como a entrada para $\arccos$ é exata, o erro surge apenas do arredondamento do ângulo de saída. Isso evita que a derivada ilimitada de $\arccos$ em $\pm 1$ atue sobre um erro de entrada, eliminando assim a dependência de $\kappa$.
   • O erro de nó é limitado separadamente analisando a sensibilidade das fases de Fourier às perturbações dos nós, resultando em um limite proporcional a $\|t - \tau\|_\infty$ sem singularidades geométricas.
4. Fatoração de Baixo Posto & LCU: A matriz NUCT é reduzida à média de duas NUDFTs (Transformadas de Fourier Não Uniformes Discretas) do Tipo-II. Cada NUDFT é aproximada via uma expansão de Bessel-Chebyshev de baixo posto (posto $K$). Os autores implementam isso usando uma Combinação Linear de Unitárias (LCU) com um estado externo ponderado, o que melhora o fator de normalização em comparação com abordagens LCU uniformes.
5. Construção Explícita de Oráculo: O artigo fornece circuitos quânticos explícitos para:
   • Oráculo de Nó ($O_\tau$): Computa aproximações de $m$ bits de $\arccos(x_k)$ de forma reversível.
   • Oráculo de Acesso à Linha ($O_r$): Explora a estrutura específica dos nós da NUCT (onde no máximo 5 nós mapeiam para o mesmo ponto da grade e os índices são consecutivos) para fornecer acesso esparso à linha sem tabelas de consulta (lookup tables).
   • Preparação de Coeficientes: Constrói os coeficientes da função de Bessel classicamente e os carrega em estados quânticos, provando que estes são independentes da instância.

Principais Contribuições

1. NUQFT Livre de Condicionamento: A principal contribuição teórica é um algoritmo NUQFT modificado (Teorema 4.7) onde os limites de erro e os requisitos de recursos são independentes do parâmetro geométrico $\kappa$. O erro depende apenas do número de bits por nó ($m$), da precisão alvo ($\epsilon$) e da esparsidade da linha ($d_r$).
2. Melhoria da Normalização: Ao utilizar um LCU externo ponderado e limites mais estreitos para o peso total de Bessel ($\Lambda < 24$), os autores alcançam uma normalização de codificação de bloco de $O(\sqrt{d_r})$. Para a NUCT, onde $d_r \le 5$, isso resulta em uma normalização $O(1)$, uma melhoria significativa em relação à escala $O(K^2\sqrt{d_r})$ ou $O(K\sqrt{d_r})$ de métodos anteriores.
3. Construções de Oráculo Explícitas: O artigo remove a suposição de oráculos pré-existentes ao fornecer circuitos quânticos explícitos e eficientes para geração de nós e acesso à linha, especificamente adaptados para o cenário de Chebyshev equiespaçado.
4. Algoritmo NUCT de Ponta a Ponta: Os autores apresentam um circuito quântico completo (Algoritmo 2) para a NUCT, incluindo uma análise rigorosa de complexidade cobrindo contagem de qubits, profundidade de porta e probabilidade de sucesso.

Resultos

O artigo estabelece os seguintes resultados de complexidade para a NUCT com $N=2^q$ nós e precisão alvo $\epsilon$:

• Complexidade de Qubits: $O(L)$ qubits, onde $L = q + \log(1/\epsilon)$.
• Complexidade de Portas: $\tilde{O}(L^2)$ portas lógicas (aritmética reversível, Clifford, Toffoli, rotações controladas). Quando sintetizado em portas Clifford+T, a complexidade é $\tilde{O}(L^3)$.
• Normalização: $O(1)$ (especificamente limitado por $24\sqrt{5}$).
• Precisão: O algoritmo produz uma codificação de bloco $\epsilon$-precisa da matriz NUCT.
• Estado de Saída: Dado um estado de entrada $|f\rangle$, o algoritmo prepara um estado que aproxima o estado normalizado $C_N|f\rangle / \|C_N|f\rangle\|$ com erro $O(\epsilon / (r-\epsilon))$, onde $r = \|C_N|f\rangle\|$. O número de rodadas de amplificação de amplitude necessárias é $O(1/(r-\epsilon))$.

Significância e Alegações

Os autores afirmam que este trabalho fornece o primeiro algoritmo quântico eficiente e livre de condicionamento para a transformada de Chebyshev não uniforme em nós equiespaçados.

• Aceleração Exponencial: O algoritmo clássico para esta transformada (por Driscoll, Healy e Rockmore [DHR97]) requer $O(N \log^2 N)$ operações. O algoritmo quântico proposto é polilogarítmico em $N$ ($\tilde{O}(\log^2 N)$), oferecendo uma aceleração exponencial para a própria transformada.
• Fundação para Transformadas Gerais: Os autores posicionam a NUCT como um bloco de construção crítico para implementar o pipeline completo de [DHR97], que computa transformadas polinomiais discretas para famílias gerais de polinômios ortogonais usando uma abordagem de divisão e conquista baseada em recorrências de três termos.
• Robustez: Ao remover a dependência de $\kappa$, o algoritmo é robusto para qualquer distribuição de nós, incluindo casos onde os nós estão arbitrariamente próximos das fronteiras da grade, um cenário onde métodos anteriores falhariam ou exigiriam suposições não comprovadas sobre o posicionamento dos nós.

O artigo conclui observando que, embora a transformação em si seja exponencialmente mais rápida, a aceleração de ponta a ponta para aplicações práticas depende do custo da preparação do estado de entrada, da norma da saída e do número de coeficientes de saída necessários. Trabalhos futuros visam estender estas técnicas para famílias gerais de polinômios ortogonais.