Quantum Singular Value Transformation
In this section we present a self contained overview of the technique of Quantum Singular Value Transformation (QSVT) presented in GSLW2019, generalizing Quantum Signal Processing (QSP). We refer the reader to an excellent paper Grand Unification of Quantum Algorithms for a more complete overview of these techniques. QSP is a quantum algorithm to apply a \(d\)-degree bounded polynomial transformation with parity \(d \mod 2\) to an arbitrary quantum subsystem, using a quantum circuit \(U_{\Phi}\) consisting of only controlled single qubit rotations. This is achieved by interleaving what is called a signal rotation operator \(W\), which is an \(x\)-rotation by some fixed angle \(\theta\) and a signal processing operator \(S_{\phi}\), which is an \(z\)-rotation by a variable angle parameterized by some \(\phi \in [0, 2 \pi]\). Note that the choice of \(x\) and \(z\) axes is conventional, and other equivalent constructions exist. Conventionally, the signal rotation operator is defined as
\[W(x) := \begin{pmatrix} x & i \sqrt{1 - x^2} \\ i \sqrt{1 - x^2} & x \end{pmatrix},\]which is an \(x\)-rotation by an angle \(\theta = -2 \arccos(x)\), and the signal processing operator is defined as
\[S_{\phi} := e^{i \phi Z},\]which is a \(z\)-rotation by an angle \(- 2 \phi\). Fascinatingly, sandwiching them together for some \(\Phi := ( \phi_0, \phi_1, \ldots \phi_d ) \in \mathbb{R}^{d + 1}\), as shown above, gives us a matrix whose elements are polynomial transformations of \(x\),
\[U_{\Phi} := e^{i \phi_0 Z} \prod_{j = 1}^{j= d} \left( W(x) e^{ i \phi_j Z } \right) \\ = \begin{pmatrix} P(x) & i Q(x) \sqrt{1 - x^2} \\ i Q^*(x) \sqrt{1 - x^2} & P^*(x) \end{pmatrix},\]such that
- \(\deg P \leq d;\ \deg Q \leq d - 1\),
- $P(x) $ has a parity $d \mod 2 $,
- \(\| P(x) \|^2 + (1 - x^2) \| Q(x) \|^2 = 1 \quad \forall x \in [-1, 1]\).
Following the application of the quantum circuit $ U_{\Phi} $ for an appropriate \(\Phi\), one can project into the top left block of \(U_{\Phi}\) to recover the polynomial \(\bra{0} U_{\Phi} \ket{0} = P(x)\). Projecting to other basis allows the ability to perform more interesting polynomial transformations, which can be linear combinations of \(P(x), Q(x)\), and their complex conjugates. For example, projecting to \(\{ \ket{+}, \ket{-} \}\) basis gives us
\[\bra{+} U_{\Phi} \ket{+} = \real (P(x)) + i \real (Q(x)) \sqrt{1 - x^2} .\]This procedure can be naturally generalized to apply a similar polynomial transformation to each singular value of an arbitrary block of a unitary matrix. Suppose we have access to a matrix $ A $ which is block encoded into some unitary $ U_A $, and can be accessed by projectors $ \Pi, \widetilde{\Pi} $ as $ A := \widetilde{\Pi} U_A \Pi $. The singular value decomposition of $ A $ is given as
\[A := W \Sigma V^{\dagger} = \sum_j \sigma_j \ket{w_j} \bra{w_j},\]where $ W, V $ are unitary matrices, $ \Sigma $ is a diagonal matrix whose $j^{th}$ diagonal entry is $ \sigma_j $, the singular value of $ A $, and $ \ket{w_j}, \ket{v_j} $ are the corresponding singular vectors (the columns of $W$ and $V$ respectively.) Then one can interleave $ U_A $ and $ U_A^{\dagger} $ with a \emph{projector controlled phase shift} operator, $ \Pi_{\phi} := e^{i \phi ( 2 \Pi - I )}, \widetilde{\Pi}_{\phi} := e^{i \phi ( 2 \widetilde{\Pi} - I )} $, for a parameter $ \phi $. For a given phase angle sequence $ \Phi \in \mathbb{R}^{d} $, the QSVT sequence is given as
\[U_{\Phi} = \begin{cases} \widetilde{\Pi}_{\phi_1} U_A \left[ \prod_{k = 1}^{(d - 1) / 2} \Pi_{\phi_{2k}} U_A^{\dagger} \widetilde{\Pi}_{\phi_{2 k + 1}} U_A \right] & d \text{ is odd } \\ \left[ \prod_{k = 1}^{d/ 2} \Pi_{\phi_{2k - 1}} U_A^{\dagger} \widetilde{\Pi}_{\phi_{2 k}} U_A \right] & d \text{ is even}, \end{cases}\]where $ \phi_i $ is the $i^{th}$ element of $ \Phi $. Now projecting to $ \Pi, \widetilde{\Pi} $ gives us the polynomial transformation of $ A $ as
\[P^{SV} (A) = \begin{cases} \widetilde{\Pi} U_{\Phi} \Pi & d \text{ is odd} \\ \Pi U_{\Phi} \Pi & d \text{ is even}, \end{cases}\]where $ P^{SV} (A) $ is the polynomial transformation of the matrix $ A $ defined as
\[P^{SV} (A) := \begin{cases} \sum_j P(\sigma_j) \ket{w_j} \bra{v_j} & P \text{ is odd} \\ \sum_j P(\sigma_j) \ket{v_j} \bra{v_j} & P \text{ is even}, \end{cases}\]This gives us an extremely powerful primitive to design novel quantum algorithms. In this work we use QSVT for matrix inversion and square root decomposition of a matrix. In the remainder of this section, we shall formally lay out the theorems for these transformations.
Acknowledgement
I thank my advisor Shantanav Chakraborty and Anurudh Peduri for useful discussions when I was reading these papers.