Trasformate quantistiche di Fourier e di Chebyshev non uniformi senza condizionamento

Abstract degli autori

Presentiamo un algoritmo quantistico efficiente per la trasformata di Chebyshev non uniforme. Questa è definita come la proiezione di una funzione sui polinomi di Chebyshev campionati in nodi assegnati, uniformi in $x\in[-1,1]$ e quindi non uniformi nell’angolo $θ=\arccos x$: una situazione che le trasformate quantistiche di Chebyshev basate sulla QFT non sono in grado di gestire. La nostra costruzione si basa sul miglioramento di una trasformata di Fourier quantistica non uniforme (NUQFT) esistente, attraverso la rimozione del condizionamento associato al campionamento non uniforme dei nodi. Di conseguenza, i limiti dell’errore sono indipendenti dal parametro $κ$ dipendente dalla geometria, presente nei lavori precedenti. Sfruttiamo il fatto che la matrice della trasformata di Chebyshev è la media di due DFT non uniformi di tipo II, che implementiamo con un unico circuito NUQFT controllato. Forniamo costruzioni esplicite degli oracoli, compreso l’oracolo di accesso alle righe, che in precedenza era stato lasciato come assunzione. La codifica a blocchi risultante, accurata entro $\varepsilon$, ha normalizzazione $O(1)$ e utilizza $O(L)$ qubit e $\widetilde O(L^2)$ gate, dove $L=\log N+\log(1/\varepsilon)$. Forniamo un’implementazione completa, dall’inizio alla fine, con un’analisi della complessità che include la probabilità di successo e l’errore dello stato di output.