Station 971

Quantum Information Processing

Written by

polarnova

in

“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?

  1. Cosine–sine decomposition (CSD) gives an explicit, numerically stable way to factor a unitary (or a tall orthonormal) matrix into 2 × 2 blocks.
  2. 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.
  3. 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.1Let $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}$.

  1. SVD of $U_1$ → $U_1=W_1CV^{\dagger}$.
  2. QR of $U_2V$ → $U_2=W_2R$.
  3. 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.2For $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.3There 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

  1. Pick a real target polynomial $f(x)$ (bounded by 1 on $[-1,1]$).
  2. Use constructive algorithms (e.g. iterative symmetric QSP solvers) to find a phase list $\Phi$ with $\text{Re}\,P=f$.
  3. 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).

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

More posts