Product Decomposition of Periodic Functions in Quantum Signal Processing

We consider an algorithm to approximate complex-valued periodic functions $f(e^{i\theta })$ as a matrix element of a product of $SU(2)$-valued functions, which underlies so-called quantum signal processing. We prove that the algorithm runs in time $\mathcal{O}(N^3\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(N\mathrm{/}ϵ))$ under the random-access memory model of computation where $N$ is the degree of the polynomial that approximates $f$ with accuracy $ϵ$; previous efficiency claim assumed a strong arithmetic model of computation and lacked numerical stability analysis.