Quantum Singular-Value Transformation

If $H_R=0$, then $A$ is the zero map and its operator norm is zero by [F4]. Otherwise take any unit $x\in H_R$. The decomposition $Ux={\mathrm{\Pi }}_{L}Ux+(I-{\mathrm{\Pi }}_L)Ux$ has orthogonal terms by [F1], so [F2] gives $\mathrm{\parallel }{\mathrm{\Pi }}_{L}Ux{\mathrm{\parallel }}^2\le \mathrm{\parallel }Ux{\mathrm{\parallel }}^2$. By [F3], $\mathrm{\parallel }Ux\mathrm{\parallel }=1$, hence $\mathrm{\parallel }Ax\mathrm{\parallel }\le 1$. Taking the maximum over unit $x$ proves $\mathrm{\parallel }A{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 1$.

In the square block-encoding case, $J_a$ is the isometric identification of the system with $H_R=H_L=\mathrm{ran}({\mathrm{\Pi }}_a)$. The definition of the projected block in [F7] is exactly $J_a^{\ast }U{J}_a$, and the exact case identifies it with the normalized target. Thus this is the stated special case.

Apply [F5] to the finite-dimensional map $A:H_R\to H_L$. For each positive singular pair, $A{v}_j={\sigma }_j{u}_j$ and $\mathrm{\parallel }{v}_j\mathrm{\parallel }=\mathrm{\parallel }{u}_j\mathrm{\parallel }=1$, so [F4] and step 1.1 give ${\sigma }_j=\mathrm{\parallel }A{v}_j\mathrm{\parallel }\le 1$. The rank-one terms in the SVD sum have the coordinate action fixed by [F6]. When $r=0$, the positive singular list and the displayed sum are empty; the kernel bases still exist by [F5].

For each $k\le r$ and every $x\in H_R$, the SVD formula, root-linear-first rank-one action [F6], and orthonormality of the $u_j$ give $⟨Ax,u_k⟩={\sigma }_k⟨x,v_k⟩$; for $k>r$ the same pairing is zero. By [F8]–[F9], $⟨Ax,u_k⟩=⟨x,A^{\ast }{u}_k⟩$, so positive definiteness [F11] gives $A^{\ast }{u}_k={\sigma }_k{v}_k$ for $k\le r$ and $A^{\ast }{u}_k=0$ for $k>r$. The SVD formula also gives $A{v}_k={\sigma }_k{u}_k$ for $k\le r$ and $A{v}_k=0$ for $k>r$. Since each singular list is a basis, expanding an arbitrary vector in those bases shows that $\ker A=\mathrm{span}\{v_{r+1},\dots ,v_n\}$ and $\ker A^{\ast }=\mathrm{span}\{u_{r+1},\dots ,u_m\}$: the positive-index coefficients must vanish because the corresponding singular values are positive and the other basis is orthonormal. The argument includes empty bases and sums.

By [F1], orthogonal decomposition gives $⟨{\mathrm{\Pi }}_{L}Ux,y⟩=⟨Ux,y⟩$ and $⟨x,{\mathrm{\Pi }}_R{U}^{\ast }y⟩=⟨x,U^{\ast }y⟩$ for $x\in H_R$ and $y\in H_L$. The adjoint rule [F8] for $U$ therefore gives $⟨Ax,y⟩=⟨x,{\mathrm{\Pi }}_R{U}^{\ast }y⟩$. Thus $y\mapsto {\mathrm{\Pi }}_R{U}^{\ast }y$ is an adjoint of $A$, and uniqueness [F9] yields $A^{\ast }={\mathrm{\Pi }}_R{U}^{\ast }{\mathrm{\mid }}_{H_L}$. Also, [F10] applies to the unitary $U$ and shows that $U^{\ast }=U^{-1}$ is unitary.

For $0<{\sigma }_i,{\sigma }_j<1$, [F1] gives ${\mathrm{\Pi }}_R{U}^{\ast }{u}_i={\sigma }_i{v}_i$. Since $U^{\ast }$ preserves inner products by [F1], orthogonal projection and [F6] give $⟨(I-{\mathrm{\Pi }}_R)U^{\ast }{u}_i,(I-{\mathrm{\Pi }}_R)U^{\ast }{u}_j⟩=⟨U^{\ast }{u}_i,U^{\ast }{u}_j⟩-⟨{\mathrm{\Pi }}_R{U}^{\ast }{u}_i,{\mathrm{\Pi }}_R{U}^{\ast }{u}_j⟩={\delta }_{ij}(1-{\sigma }_i^2)$. Dividing by the positive square roots shows that the $w_i$ are orthonormal and lie in $\ker {\mathrm{\Pi }}_R$. The same calculation, using ${\mathrm{\Pi }}_{L}U{v}_i={\sigma }_i{u}_i$, proves that the ${\tilde{w}}_i$ are orthonormal in $\ker {\mathrm{\Pi }}_L$.

If ${\sigma }_i=1$, then ${\mathrm{\Pi }}_R{U}^{\ast }{u}_i=v_i$ has norm one, as does $U^{\ast }{u}_i$. By the orthogonal decomposition in [F5] and Pythagoras [F6], its component in $\ker {\mathrm{\Pi }}_R$ is zero, so $U^{\ast }{u}_i=v_i$ and $U{v}_i=u_i$.

Decompose $U{v}_i={\mathrm{\Pi }}_{L}U{v}_i+(I-{\mathrm{\Pi }}_L)U{v}_i={\sigma }_i{u}_i+\sqrt{1-{\sigma }_i^2}{\tilde{w}}_i$. Also $\sqrt{1-{\sigma }_i^2}U{w}_i=U(I-{\mathrm{\Pi }}_R)U^{\ast }{u}_i=u_i-U{\mathrm{\Pi }}_R{U}^{\ast }{u}_i=u_i-{\sigma }_{i}U{v}_i$, where the middle equality uses $U{U}^{\ast }=I$ and the last uses [F1]. Substitution of the first equation yields $U{w}_i=\sqrt{1-{\sigma }_i^2}{u}_i-{\sigma }_i{\tilde{w}}_i$, which is the displayed matrix.

If $v\in \ker A\cap H_R$, then ${\mathrm{\Pi }}_{L}Uv=Av=0$, so $Uv\in \ker {\mathrm{\Pi }}_L$. If $u\in \ker A^{\ast }\cap H_L$, then ${\mathrm{\Pi }}_R{U}^{\ast }u=A^{\ast }u=0$, so $U^{\ast }u\in \ker {\mathrm{\Pi }}_R$. Every right singular vector lies in $H_R$ and is orthogonal to each $w_i$ and each $U^{\ast }u$ from the left kernel, since those vectors lie in $\ker {\mathrm{\Pi }}_R$. For a positive singular vector and a left-kernel vector, $⟨(I-{\mathrm{\Pi }}_R)U^{\ast }{u}_i,U^{\ast }{u}_k⟩=⟨U^{\ast }{u}_i,U^{\ast }{u}_k⟩-⟨{\mathrm{\Pi }}_R{U}^{\ast }{u}_i,{\mathrm{\Pi }}_R{U}^{\ast }{u}_k⟩=0-0=0$, because $u_i\perp u_k$ and ${\mathrm{\Pi }}_R{U}^{\ast }{u}_k=0$. Thus the listed source blocks are mutually orthogonal. Their orthogonal complement is contained in $\ker {\mathrm{\Pi }}_R$, because the right singular vectors, including a basis of $\ker A$, span $H_R$. Applying $U$ preserves orthogonality. The listed output blocks are also mutually orthogonal: the left singular vectors, including a basis of $\ker A^{\ast }$, span $H_L$; the vectors ${\tilde{w}}_i$ are orthonormal by step 1.1; and for $v\in \ker A$, $⟨{\tilde{w}}_i,Uv⟩=⟨U{v}_i,Uv⟩-⟨{\mathrm{\Pi }}_{L}U{v}_i,{\mathrm{\Pi }}_{L}Uv⟩=0$, since $v_i\perp v$ and $Av=0$. The remaining named output vectors $Uv$ lie in $\ker {\mathrm{\Pi }}_L$, so they are orthogonal to $H_L$. The output complement is therefore contained in $\ker {\mathrm{\Pi }}_L$. Since $U$ maps each listed source block onto its corresponding output block, it maps the source complement onto the output complement. These are ambient-space decompositions; the residual blocks are not part of $H_R$ or $H_L$. Each projector phase is scalar on the residual source and output blocks, so no residual component mixes into a projected singular-space block.

For each distinct positive singular value $\sigma$, define $E_{\sigma }=\ker (A^{\ast }A-{\sigma }^{2}I)$ in $H_R$ and $F_{\sigma }=\ker (A{A}^{\ast }-{\sigma }^{2}I)$ in $H_L$. The adjoint rule [F4] and adjoint algebra [F5] make $A^{\ast }A$ and $A{A}^{\ast }$ self-adjoint, and [F2]–[F3] identify these eigenspaces with the right and left singular subspaces. If $v\in E_{\sigma }$, then $Av\in F_{\sigma }$ because $A{A}^{\ast }Av=A(A^{\ast }Av)={\sigma }^{2}Av$. Also [F4] gives $\mathrm{\parallel }Av{\mathrm{\parallel }}^2=⟨v,A^{\ast }Av⟩={\sigma }^2\mathrm{\parallel }v{\mathrm{\parallel }}^2$. Thus $J_{\sigma }:=A\mathrm{/}\sigma$ is an isometry from $E_{\sigma }$ into $F_{\sigma }$. For $y\in F_{\sigma }$, [F5] gives $A^{\ast }y\in E_{\sigma }$, and $J_{\sigma }(A^{\ast }y\mathrm{/}\sigma )=y$; hence $J_{\sigma }$ maps $E_{\sigma }$ onto $F_{\sigma }$.

Group the positive singular terms in the odd transform by their common value $\sigma$. In any orthonormal basis $(v_j)$ of $E_{\sigma }$, the paired left vectors are $u_j=J_{\sigma }{v}_j$, so ${\sum }_{j:{\sigma }_j=\sigma }\mathrm{\mid }{u}_j⟩⟨v_j\mathrm{\mid }=J_{\sigma }{\mathrm{\Pi }}_{E_{\sigma }}$, where ${\mathrm{\Pi }}_{E_{\sigma }}$ is the unique projection from [F6]. The grouped term is therefore $p(\sigma )J_{\sigma }{\mathrm{\Pi }}_{E_{\sigma }}$, independent of the basis.

For the even right transform, grouping by positive singular value gives $p(\sigma ){\mathrm{\Pi }}_{E_{\sigma }}$, and the zero-singular part is $p(0){\mathrm{\Pi }}_{\ker A}$; both are canonical projections. For the even left transform the corresponding terms are $p(\sigma ){\mathrm{\Pi }}_{F_{\sigma }}$ and $p(0){\mathrm{\Pi }}_{\ker A^{\ast }}$. The zero right and left singular vectors may be chosen independently, but the even definitions use only these unique subspace projections, while the odd definition omits zero singular pairs. Thus all three transforms are independent of the SVD choices.

Define the ancilla-controlled bit flip $X_{\mathrm{\Pi }}:=H_{a}C(S_{\mathrm{\Pi }})H_a$, where $H_a=H\otimes I_H$. On $\mathrm{ran}\mathrm{\Pi }$, $S_{\mathrm{\Pi }}=-I$, so [L2] makes $C(S_{\mathrm{\Pi }})$ act as $Z_a$ on the ancilla; conjugating by $H_a$ gives $X_a$. On $\ker \mathrm{\Pi }$, $S_{\mathrm{\Pi }}=I$, so $C(S_{\mathrm{\Pi }})$ acts as $I$ and $X_{\mathrm{\Pi }}$ is the identity. Thus $X_{\mathrm{\Pi }}$ flips the ancilla exactly on the range of $\mathrm{\Pi }$. By [L3], each use of $C(S_{\mathrm{\Pi }})$ is one supplied call to $C(R_{\mathrm{\Pi }})$ plus one ancilla $Z_a$ gate.

Apply $X_{\mathrm{\Pi }}$, then $R_z(2\varphi )=e^{-i\varphi Z_a}$, then $X_{\mathrm{\Pi }}$ again. On $\mathrm{ran}\mathrm{\Pi }$, the ancilla operation is $X_a{e}^{-i\varphi Z_a}{X}_a=e^{i\varphi Z_a}$; on $\ker \mathrm{\Pi }$ it is $e^{-i\varphi Z_a}$. Acting on $\mathrm{\mid }0⟩$, these give phases $e^{i\varphi }$ and $e^{-i\varphi }$, respectively, and both branches return the ancilla to $\mathrm{\mid }0⟩$. The induced system operation is therefore $e^{i\varphi }(\mathrm{\Pi })+e^{-i\varphi }(I-\mathrm{\Pi })=e^{i\varphi (2\mathrm{\Pi }-I)}$.

The construction uses two occurrences of $X_{\mathrm{\Pi }}$, hence two controlled-reflection calls by step 1.1, and one variable $R_z(2\varphi )$ rotation. Its Hadamard and ancilla-$Z$ gates have constant count per phase slot. Applying the same construction with ${\mathrm{\Pi }}_R$ or ${\mathrm{\Pi }}_L$ gives the two projector-phase operations used by the QSVT sequence; no direct or controlled reflection cost is inferred from the matrix description alone.

Let $c$ be an external branch qubit. Replace the middle rotation by its controlled version, leaving both occurrences of $X_{\mathrm{\Pi }}$ unchanged. On branch $c=1$, step 2.1 gives $e^{i\varphi R_{\mathrm{\Pi }}}$. On branch $c=0$, the middle operation is identity and the two adjacent $X_{\mathrm{\Pi }}$ operations cancel because $X_{\mathrm{\Pi }}^2=I$; the system operation is identity. Thus this is the controlled projector phase. It uses the same two controlled-reflection calls as the uncontrolled construction and one separately supplied and charged branch-controlled rotation.

The loop in [F1] executes once for each integer $j=d-1,\dots ,0$, hence it makes exactly $d$ signal calls. The side starts at $R$, so the first call is $U$ and directions alternate; therefore the counts are $\lceil d\mathrm{/}2\rceil$ forward calls and $\lfloor d\mathrm{/}2\rfloor$ inverse calls. If $d=0$, the loop is empty.

For a controlled sequence against identity, use the externally controlled projector-phase implementation in [F2] at every phase slot. On the zero branch each phase is then the identity, so the alternating signal calls cancel in adjacent $U{U}^{\ast }$ or $U^{\ast }U$ pairs. If $d$ is even all signal calls pair and cancel; if $d$ is odd, one forward $U$ call remains, which is made controlled while the other signal calls pair and cancel. On the zero branch that controlled call is also identity, while the one branch executes the original sequence. Thus this variant requires zero extra controlled signal calls for even $d$ and one controlled $U$ call for odd $d$, whose availability is explicit by [F3].

For a branch selector between $\mathrm{\Phi }$ and $-\mathrm{\Phi }$, let control value $0$ select $\mathrm{\Phi }$ and value $1$ select $-\mathrm{\Phi }$. At a slot with phase $\varphi$ about $\mathrm{\Pi }$, use the clean-ancilla toggle $X_{\mathrm{\Pi }}$ from step 1.1 of [F2], then unconditional $R_z(2\varphi )$, then a control-one-controlled $R_z(-4\varphi )$, and then $X_{\mathrm{\Pi }}$ again. The middle rotation is $R_z(2\varphi )$ in branch $0$ and $R_z(-2\varphi )$ in branch $1$; because $X_{\mathrm{\Pi }}$ flips the ancilla on $\mathrm{ran}\mathrm{\Pi }$ and leaves it unchanged on $\ker \mathrm{\Pi }$, the system phases are respectively $e^{i\varphi (2\mathrm{\Pi }-I)}$ and $e^{-i\varphi (2\mathrm{\Pi }-I)}$. The same unconditioned signal call occurs between each pair of phase slots, so the signal list is shared and this selector adds no controlled signal query.

There is one phase at the initial $R$ side and one after each of the $d$ signal calls, for $d+1$ slots. Their sides alternate beginning at $R$, giving $\lceil (d+1)\mathrm{/}2\rceil$ right-projector slots and $\lfloor (d+1)\mathrm{/}2\rfloor$ left-projector slots.

Apply [F2] to each slot counted in step 2.2. The total controlled-reflection calls are $2\lceil (d+1)\mathrm{/}2\rceil$ for ${\mathrm{\Pi }}_R$ and $2\lfloor (d+1)\mathrm{/}2\rfloor$ for ${\mathrm{\Pi }}_L$, unchanged for the paired selector. A single unconditioned sequence has $d+1$ variable rotations; the $\mathrm{\Phi }\mathrm{/}-\mathrm{\Phi }$ selector instead uses $d+1$ unconditional rotations $R_z(2{\varphi }_j)$ and $d+1$ separately charged branch-controlled rotations $R_z(-4{\varphi }_j)$, with constant one-qubit overhead per slot.

The counts above describe only the listed operations. By [F4], the cost of supplied $U$, $U^{\ast }$, controlled calls, phase gates, ancilla wires, classical phase generation, and finite-gate compilation are recorded in their applicable separate coordinates; none is inferred from the matrix $A$ alone.

Fix $0<{\sigma }_j<1$. In the input basis $(v_j,w_j)$ and output basis $(u_j,{\tilde{w}}_j)$, [F2] says that $U$ is $W_R({\sigma }_j)$, and $U^{\ast }$ has the same matrix because it is real symmetric. The right-projector phase is $Z(\varphi )$ on the input basis since $2{\mathrm{\Pi }}_R-I$ has eigenvalues $+1,-1$ there; the left-projector phase is the same $Z(\varphi )$ on the output basis. Thus the alternating sequence multiplies in the fixed order $Z({\varphi }_0)W_R({\sigma }_j)Z({\varphi }_1)\cdots W_R({\sigma }_j)Z({\varphi }_d)=U_{\mathrm{\Phi }}({\sigma }_j)$, whose upper-left entry is $P_{\mathrm{\Phi }}({\sigma }_j)$ by [F3]–[F4].

If ${\sigma }_j=1$, [F2] gives $U{v}_j=u_j$ and the complementary component is zero; the surviving one-dimensional action is the first-coordinate action of $U_{\mathrm{\Phi }}(1)$, namely $P_{\mathrm{\Phi }}(1)$. For ${\sigma }_j=0$, $U{v}_j$ lies in $\ker {\mathrm{\Pi }}_L$ and $U^{\ast }(U{v}_j)=v_j$. The alternating calls therefore swap this right-kernel vector and its left-complement image exactly as $W_R(0)=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ does. If $d$ is odd the final vector lies in $\ker {\mathrm{\Pi }}_L$ and the left compression is zero, equal to $P_{\mathrm{\Phi }}(0)$ because [F4] makes $P_{\mathrm{\Phi }}$ odd. If $d$ is even it returns to $v_j$ with coefficient $P_{\mathrm{\Phi }}(0)$, the prescribed even-kernel term in [F5]. Left-kernel inputs and the residual complement contribute nothing to the stated compression by [F2].

The positive singular planes, the $\sigma =1$ lines, the right zero-kernel lines, and the residual blocks are orthogonal and exhaust the relevant projected spaces by [F2]. Summing the scalar coefficients from steps 1.1–1.2 therefore gives the displayed odd and even compressed-block formulas.

For real $p$ under the stated degree, parity, and interval bounds, [F7] gives an admissible pair $P,Q$ with $\mathrm{Re}P=p$, and [F8] supplies its exact phase list $\mathrm{\Phi }$. At each slot with phase ${\varphi }_j$ about $\mathrm{\Pi }$, use the clean-ancilla toggle $X_{\mathrm{\Pi }}$ from [F11], then apply unconditional $R_z(2{\varphi }_j)$, then a control-one-controlled $R_z(-4{\varphi }_j)$, and then $X_{\mathrm{\Pi }}$ again. In control branch $0$ the middle rotation is $R_z(2{\varphi }_j)$; in branch $1$ it is $R_z(-2{\varphi }_j)$. Since $X_{\mathrm{\Pi }}$ places the ancilla in $\mathrm{\mid }1⟩$ on $\mathrm{ran}\mathrm{\Pi }$ and in $\mathrm{\mid }0⟩$ on $\ker \mathrm{\Pi }$, the induced system phases are respectively $e^{i{\varphi }_j(2\mathrm{\Pi }-I)}$ and $e^{-i{\varphi }_j(2\mathrm{\Pi }-I)}$, and the ancilla returns to $\mathrm{\mid }0⟩$. The same unconditioned signal calls therefore give full branch operators $U_{\mathrm{\Phi }}$ and $U_{-\mathrm{\Phi }}$. Because $W_R(x)$ is real and $Z(-\varphi )=\overline{Z(\varphi )}$, entrywise conjugation gives $U_{-\mathrm{\Phi }}(x)=\overline{U_{\mathrm{\Phi }}(x)}$, and projection of the control from $\mathrm{\mid }+⟩$ to $\mathrm{\mid }+⟩$ has block $\frac{1}{2}(U_{\mathrm{\Phi }}+U_{-\mathrm{\Phi }})$. By step 2.1, its coefficient on each positive singular pair is $\frac{1}{2}(P_{\mathrm{\Phi }}({\sigma }_j)+\overline{P_{\mathrm{\Phi }}({\sigma }_j)})=\mathrm{Re}{P}_{\mathrm{\Phi }}({\sigma }_j)=p({\sigma }_j)$; for an even transform the same identity gives $p(0)$ on $\ker A$. Thus the compressed block is $p^{\mathrm{S}\mathrm{V}}(A)$. If the supplied scalar approximation satisfies ${\sup }_{x\in [-1,1]}\mathrm{\mid }\mathrm{Re}{P}_{\mathrm{\Phi }}(x)-p(x)\mathrm{\mid }\le \eta$, each singular coefficient changes by at most $\eta$, so orthonormality gives operator-norm error at most $\eta$. The proof stays in the reflected convention; [F10]'s scalar is not discarded if a circuit is translated to the SU(2) convention.