Quantum singular value transformation

Quantum singular value transformation is a quantum algorithm primitive that unifies all existing quantum algorithms into a single framework thus simplifying quantum algorithm design and implementation. It applies polynomial functions to the singular values of matrices.

Algorithm

Input: A matrix $A$ whose Singular value decomposition is $A=W\Sigma V^{\dagger }$ where $\Sigma$ are the singular values of A

Input: A polynomial $P$

Output: A unitary where $P$ has been applied to the singular values of $A$: ${\begin{bmatrix}WP(\Sigma )V^{\dagger }&.\\.&.\end{bmatrix}}$

1. Prepare a unitary $U$ that encodes $A$ on the top left side of $U$, that is $U={\begin{bmatrix}A&.\\.&.\end{bmatrix}}$
2. Initialize an $n$ qubit state $|0\rangle ^{\otimes n}$
3. If the polynomial is odd, first apply ${\tilde {\Pi }}_{\phi _{1}}U$ and then $\prod _{k=1}^{\frac {d-1}{2}}\Pi _{\phi _{2k}}U^{\dagger }{\tilde {\Pi }}_{\phi _{2k+1}}U$ to $|0\rangle ^{\otimes n}$
4. If the polynomial is even apply $\prod _{k=1}^{\frac {d}{2}}\Pi _{\phi _{2k}-1}U^{\dagger }{\tilde {\Pi }}_{\phi _{2k}}U$ to $|0\rangle ^{\otimes n}$

See also

• Quantum signal processing