Quantum singular value transformation

The basic primitive of quantum singular value transformation is the block-encoding. A quantum circuit is a block-encoding of a matrix A if it implements a unitary matrix U such that U contains A in a specified sub-matrix. For example, if ${\displaystyle (\langle 0|\otimes I)U(|0\rangle |\phi \rangle )=A|\phi \rangle }$, then U is a block-encoding of A.

The fundamental algorithm of QSVT is one that converts a block-encoding of A to a block-encoding of ${\displaystyle p(A,A^{\dagger })}$, where p is a polynomial of degree d and ${\displaystyle A^{\dagger }}$ denotes the conjugate transpose, with only d applications of the circuit and one ancilla qubit. This can be done for a large class of polynomials p which correspond to applying a polynomial to the singular values of A, giving a "singular value transformation".

A variant of this algorithm can also be performed when A is Hermitian, corresponding to an "eigenvalue transformation". That is, given a block-encoding of A with eigendecomposition of a matrix ${\displaystyle A=\sum \lambda _{i}u_{i}u_{i}^{\dagger }}$, one can get a block-encoding for ${\displaystyle \sum p(\lambda _{i})u_{i}u_{i}^{\dagger }}$, provided p is bounded.^[4]

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

Input: A polynomial ${\displaystyle P}$

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

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

^[2]

• Quantum algorithm
• HHL algorithm
• Quantum machine learning
• Digital signal processing