Quantum signal processing

Quantum Signal Processing is a Hamiltonian simulation algorithm with optimal lower bounds in query complexity. It linearizes the operator of a quantum walk using eigenvalue transformation. The quantum walk takes a constant number of queries. So quantum signal processing's cost depends on the constant number of calls to the quantum walk operator, number of single qubit quantum gates that aid in the eigenvalue transformation and an ancilla qubit.

Eigenvalue transformation

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

Algorithm

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

Output: [math]\displaystyle{ e^{iHt} }[/math]

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