Quantum signal processing

Given a unitary ${\displaystyle W|u_{i}\rangle =e^{i\theta _{i}}|u_{i}\rangle }$, calculate ${\displaystyle A=f(W)=\sum _{i}e^{if(\theta _{i})}\left|u_{i}\right\rangle \langle u_{i}|}$. For example, if ${\displaystyle W={\begin{bmatrix}e^{i\theta _{1}}&0&0\\0&e^{i\theta _{2}}&0\\0&0&e^{i\theta _{3}}\end{bmatrix}}}$, ${\displaystyle A={\begin{bmatrix}e^{if(\theta _{1})}&0&0\\0&e^{if(\theta _{2})}&0\\0&0&e^{if(\theta _{3})}\end{bmatrix}}}$. [1]

Input: Given a Hamiltonian ${\displaystyle H}$, define a quantum walk operator ${\displaystyle W}$ using 2 d-sparse oracles ${\displaystyle O_{H}}$ and ${\displaystyle O_{F}}$. ${\displaystyle O_{H}}$ accepts inputs ${\displaystyle j}$ and ${\displaystyle k}$ (${\displaystyle j}$ is the row of the Hamiltonian and ${\displaystyle k}$ is the column) and outputs ${\displaystyle \langle j|H\left|k\right\rangle }$, so querying ${\displaystyle O_{H}=|j\rangle |k\rangle |l\rangle =|j\rangle |k\rangle |l\oplus H_{j,k}\rangle }$. ${\displaystyle O_{F}}$ accepts inputs ${\displaystyle j}$ and ${\displaystyle l}$ and computes the ${\displaystyle l^{\text{th}}}$ non-zero element in the ${\displaystyle j^{\text{th}}}$ row of ${\displaystyle H}$. [2]

Output: ${\displaystyle e^{iHt}}$

1. Create an input state ${\displaystyle \theta }$
2. Define a controlled-gate, ${\displaystyle c-W}$
3. Repeatedly apply single qubit gates to the ancilla followed applications of ${\displaystyle c-W}$ to the register that contains ${\displaystyle \theta }$ ${\displaystyle O(td||H||_{\text{max}}+{\frac {\log {\frac {1}{\epsilon }}}{\log \log {\frac {1}{\epsilon }}}})}$ times.