polarnova - Station 971

“Central to many recent quantum algorithms is the ability to reduce high-dimensional operators to SU(2) building blocks, manipulate them with phase rotations, and then lift the resulting polynomial back to the original space.”

1 Prelude: Why these three ideas?

Cosine–sine decomposition (CSD) gives an explicit, numerically stable way to factor a unitary (or a tall orthonormal) matrix into 2 × 2 blocks.
Qubitization leverages CSD to embed a (possibly non-unitary) operator into a larger unitary whose action on carefully chosen ancilla|system subspaces is a direct sum of those 2 × 2 blocks.
Quantum Signal Processing (QSP) shows how alternating single-qubit rotations inside each block implement polynomial transformations of the operator’s singular (or eigen-) values.

Together they supply a unifying algebraic template for Hamiltonian simulation, linear-system inversion, ground-state preparation, and more.

2 Cosine–Sine Decomposition revisited

2.1 Rectangular CSD (orthonormal columns)

Theorem 2.2.1 Let $U\in\mathbb{C}^{(p+q)\times p}$ satisfy $U^{\dagger}U=I_p$ with $q\ge p$ . Then there exist unitaries $W_1\in\mathbb{C}^{p\times p}$ , $W_2\in\mathbb{C}^{q\times q}$ , $V\in\mathbb{C}^{p\times p}$ and diagonal $C=\operatorname{diag}(c_1,\dots,c_p)$ , $S=\operatorname{diag}(s_1,\dots,s_p)$ (with $c_j^2+s_j^2=1$ ) such that

U=\begin{pmatrix}W_1&0\\0&W_2\end{pmatrix} \begin{pmatrix}C\\S\\\end{pmatrix}V^{\dagger}.

Sketch. Partition $U=\begin{pmatrix}U_1 \ U_2\end{pmatrix}$ .

SVD of $U_1$ → $U_1=W_1CV^{\dagger}$ .
QR of $U_2V$ → $U_2=W_2R$ .
Orthogonality $U^{\dagger}U=I$ forces $R^{\dagger}R=I-C^2$ ⇒ $R=S$ is diagonal.

Hence the block-diagonal/diagonal factorization above.

2.2 Unitary CSD

Theorem 2.2.2 For $U\in\mathbb{C}^{(p+q)\times(p+q)}$ unitary and $q\ge p$ ,

U=\begin{pmatrix} W_1&0\\0&W_2 \end{pmatrix} \begin{pmatrix} C&S&0\\ -S&C&0\\ 0&0&I_{q-p} \end{pmatrix} \begin{pmatrix} V_1^{\dagger}&0\\0&V_2^{\dagger} \end{pmatrix},

with the same diagonal $C,S$ (now $p\times p$ ) and unitaries $ W{1,2},V{1,2} $.

This version pairs each $c_j$ – $s_j$ into a 2 × 2 rotation block—exactly the structure a quantum computer loves.

3 Qubitization: from blocks to oracles

3.1 Block encoding

Given an $n$ -qubit operator $A$ we say $U_A$ is an $m$ -qubit block encoding if

\langle 0^{\otimes m}|\,U_A\,|0^{\otimes m}\rangle = A .

3.2 Applying CSD inside the block

Using Theorem 2.2.2 on $U_A$ (after permuting qubits) we obtain

U_A \;\xrightarrow{\text{permute}}\; \bigoplus_{j=1}^{N} \begin{pmatrix} \sigma_j & \sqrt{1-\sigma_j^2}\\[2pt] -\sqrt{1-\sigma_j^2} & \sigma_j \end{pmatrix} \;\;\oplus I, \tag{1}

where ${\sigma_j}$ are the singular values of $A$ . This direct sum of SU(2) blocks is what the literature dubs qubitization.

Formally, By conjugating with a permutation matrix K we can express the middle matrix in Theorem 2.2.2:

\begin{aligned} \left(\begin{array}{ccc} \Sigma & S & 0 \\ -S & \Sigma & 0 \\ 0 & 0 & I_{N(M-2)} \end{array}\right) & =K \bigoplus_{j \in[N]}\left(\begin{array}{cc} \sigma_j & \sqrt{1-\sigma_j^2} \\ -\sqrt{1-\sigma_j^2} & \sigma_j \end{array}\right) \bigoplus I_{N(M-2)} K^{\dagger} \\ & =K \bigoplus_{j \in[N]} e^{-\frac{1}{4} Z} e^{i \arccos \left(\sigma_j\right) X} e^{\frac{1}{4} Z} \bigoplus I_{N(M-2)} K^{\dagger} \end{aligned}

The ancilla workspace “decouples” the big matrix into many identical two-level problems—one per singular value.

4 Quantum Signal Processing (QSP)

4.1 Alternating Phase Modulation

Define a single-qubit “signal” matrix

W(x)=e^{i\arccos(x)X}= \begin{pmatrix} x & i\sqrt{1-x^{2}}\\ i\sqrt{1-x^{2}} & x \end{pmatrix}.

With phase list $\Phi=(\varphi_0,\dots,\varphi_d)\in\mathbb{R}^{d+1}$ ,

U(x,\Phi)=e^{i\varphi_0 Z}\; \prod_{j=1}^{d} W(x)\,e^{i\varphi_j Z}.

4.2 Polynomial magic

Theorem 2.3.3 There exist polynomials $P,Q$ with $\deg P\le d,\; \deg Q\le d-1,$ $|P(x)|^2+(1-x^2)|Q(x)|^2=1$ on $[-1,1]$ such that

U(x,\Phi)= \begin{pmatrix} P(x) & iQ(x)\sqrt{1-x^{2}}\\ iQ^{*}(x)\sqrt{1-x^{2}} & P^{*}(x) \end{pmatrix}.

Consequently, within each 2-level block in (1) the sequence

$$-Z(φ_0)-W(σ_0)-Z(φ1)- ... -W(σ{d-1})-Z(φ_d)-$$

implements the singular-value transformation

\sigma_j \;\longmapsto\; P(\sigma_j).

For Hermitian $A$ , this is an eigenvalue transformation; the system’s states never leave the physical subspace.

4.3 Design recipe

Pick a real target polynomial $f(x)$ (bounded by 1 on $[-1,1]$ ).
Use constructive algorithms (e.g. iterative symmetric QSP solvers) to find a phase list $\Phi$ with $\text{Re}\,P=f$ .
Insert the resulting alternating-phase circuit in front of your block-encoded oracle.

5 Putting it all together

Stage	Linear-algebra viewpoint	Circuit ingredient
CSD	Factor arbitrary $U$ into $2 × 2$ rotations	Compile large operators into small blocks
Qubitization	Embed $A$ as a block of $U_A$ ; apply CSD	Ancilla qubits + permutation wiring
QSP	Alternate $Z$ – $X$ rotations inside each block	Phase list → polynomial $P$

The synergy is powerful:

Hamiltonian simulation: take $f(x)=e^{itx}$ .
Linear-system solving: take $f(x)=1/x$ .
Ground-state prep: take Chebyshev filters, $f(x)=T_d(x)$ .

All boil down to finding phases.

6 Further reading

Y. Dong, Quantum Signal Processing Algorithm and Its Applications (PhD thesis, 2023) – Chapter 2.
G. H. Low & I. L. Chuang, “Hamiltonian Simulation by Qubitization,” Quantum 3, 163 (2019).

Author: polarnova

Can all NP problems be efficiently solved in quantum polynomial time?

Quantum Information Processing