Station 971

Tag: Computer Science

  • Quantum Information Processing

    “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).