量子奇异值变换 | Codeboy's Blog

形式陈述

设一个酉 $U$ 与可相干实现的输入、输出投影 $\Pi,\widetilde\Pi$ 给出归一化矩阵

B=\widetilde\Pi U\Pi:\operatorname{im}\Pi\longrightarrow\operatorname{im}\widetilde\Pi, \qquad\|B\|\le1.

这是投影酉编码。算法同时需要 $U^\dagger$ 和关于两投影的相位门 $e^{i\phi(2\Pi-I)}$ 、 $e^{i\phi(2\widetilde\Pi-I)}$ ，不是只给出 $B$ 的经典条目表。

取奇异值分解 $B=\sum_i\sigma_i|u_i\rangle\langle v_i|$ 。对实多项式 $p$ ，若次数至多 $d\ge1$ 、奇偶性与 $d$ 一致，并满足

|p(x)|\le1\qquad(-1\le x\le1), \tag{1}

则QSVT可用 $d$ 次 $U/U^\dagger$ 调用及 $O(d)$ 个投影相位操作，实现以下算子的块编码：[1, Corollary 18]

p^{(\mathrm{SV})}(B)= \begin{cases} \displaystyle\sum_i p(\sigma_i)|u_i\rangle\langle v_i|,&p\text{ 奇},\\[2mm] \displaystyle\sum_i p(\sigma_i)|v_i\rangle\langle v_i|,&p\text{ 偶}. \end{cases} \tag{2}

偶情形求和覆盖整个输入空间，未配对的右零空间也按 $p(0)$ 作用；奇情形因 $p(0)=0$ ，零奇异值不引入基选择歧义。常数 $p$ 可另用已知辅助旋转实现，不需要查询 $U$ 。

一般实 $p$ 的实现允许增加一个辅助位提取实部。若声称完全不用这个辅助且完整矩阵元就是 $p$ ，还须满足QSP补多项式的更强条件，不能只凭式 (1)。

直觉

一个非Hermitian矩阵把右奇异向量送到左奇异向量，而逆门把方向送回来。因此信号处理不能一直乘同一个 $U$ ，需要让 $U$ 与 $U^\dagger$ 交替，把对应的左右二维空间对接起来。

奇数次跨越后，算子从右空间到左空间；偶数次跨越后，回到右空间。奇偶性因此不只是多项式的一项形式限制，它还决定了输出所在的空间。

非对称矩阵A把右基向量0以0.8送到左基向量1，把右基向量1以0.3送到左基向量0；三次奇异值响应把两系数改为0.512和0.027，而普通A立方得到不同系数。

例子与边界

左右二维空间怎样出现

对 $0<\sigma_i<1$ ，令 $s_i=\sqrt{1-\sigma_i^2}$ 。由块条件，

U|v_i\rangle=\sigma_i|u_i\rangle+s_i|u_i^\perp\rangle,

其中 $u_i^\perp$ 位于输出投影外。再定义

|v_i^\perp\rangle= \frac{U^\dagger|u_i\rangle-\sigma_i|v_i\rangle}{s_i}.

它位于输入投影外；直接作用 $U$ 得

U|v_i^\perp\rangle=s_i|u_i\rangle-\sigma_i|u_i^\perp\rangle.

所以 $U$ 从右平面基 $(v_i,v_i^\perp)$ 到左平面基 $(u_i,u_i^\perp)$ 的矩阵为

R(\sigma_i)=\begin{pmatrix}\sigma_i&s_i\\s_i&-\sigma_i\end{pmatrix}.

两投影相位门在各自平面上都是 $\operatorname{diag}(e^{i\phi},e^{-i\phi})$ 。因此交替调用把高维电路化成同一套二维反射信号处理，只是每个平面代入不同 $\sigma_i$ 。端点0、1的退化空间按式 (2) 单独接上，不能在分母为零时继续使用这些基公式。[1, Lemma 14]

序列和额外实部辅助具体指什么

记 $D_\Pi(\phi)=e^{i\phi(2\Pi-I)}$ 。奇数 $d$ 可用序列

U_\Phi=D_{\widetilde\Pi}(\phi_1)U \prod_{j=1}^{(d-1)/2} \left[D_\Pi(\phi_{2j})U^\dagger D_{\widetilde\Pi}(\phi_{2j+1})U\right]. \tag{3}

偶数 $d$ 则用

U_\Phi=\prod_{j=1}^{d/2} \left[D_\Pi(\phi_{2j-1})U^\dagger D_{\widetilde\Pi}(\phi_{2j})U\right]. \tag{4}

相位按反射信号 $R(x)$ 的QSP约定合成，不能把旋转信号 $W(x)$ 的相位未经转换直接复制过来。[1, Corollary 8与Definition 15]

一般先完成一个复多项式 $P$ ，使 $\operatorname{Re}P=p$ 。用额外位的张量积寄存器构造

\mathcal V=|0\rangle\langle0|\otimes U_\Phi+ |1\rangle\langle1|\otimes U_{-\Phi}.

把该位输入、输出都取 $|+\rangle$ ，就得到 $P$ 与 $P^*$ 的平均。奇数时同时取输入 $\Pi$ 、输出 $\widetilde\Pi$ ；偶数时两侧都取 $\Pi$ ，正好给式 (2)。两分支的 $U/U^\dagger$ 顺序相同，只有相位符号不同，因此可以共享查询骨架，只控制相位门。

x立方的三查询非对称例子

令

A=\begin{pmatrix}0&3/10\\4/5&0\end{pmatrix} =X\begin{pmatrix}4/5&0\\0&3/10\end{pmatrix}I.

右奇异向量依次为 $|0\rangle,|1\rangle$ ，左奇异向量依次为 $|1\rangle,|0\rangle$ 。对 $p(x)=x^3$ ，

p^{(\mathrm{SV})}(A)= \begin{pmatrix}0&27/1000\\64/125&0\end{pmatrix} =AA^\dagger A.

而 $A^2=(6/25)I$ ，所以

A^3=\begin{pmatrix}0&9/125\\24/125&0\end{pmatrix}.

两者不同。QSVT保持左右奇异向量并改写奇异值，不是一般意义下把同一非正规矩阵连乘三次。

这个 $x^3$ 目标还可直接用完整矩阵元实现，不需实部辅助：在式 (3) 取反射约定的相位

(\phi_1,\phi_2,\phi_3)=(\pi,-\pi/6,-5\pi/6).

对任意标量 $x$ ， $Z(\phi_1)R(x)Z(\phi_2)R(x)Z(\phi_3)R(x)$ 的左上元素就是 $x^3$ 。这与旋转QSP的 $(0,\pi/3,-\pi/3,0)$ 是换约定后的两种序列。

推论与应用

原矩阵尺度、逼近误差和实现误差

若输入编码的是 $B=A/\alpha$ ，输出首先是 $p^{(\mathrm{SV})}(A/\alpha)$ 。例如 $p=x^3$ 给 $AA^\dagger A/\alpha^3$ ，不是自动得到未缩放结果。把输出进一步当作态使用，还需计成功概率 $\|p^{(\mathrm{SV})}(B)|\psi\rangle\|^2$ 。

如果标量目标 $f$ 与 $p$ 在所有相关奇异值上误差至多 $\eta$ ，并采用同样的左右空间约定，则SVD直接给算子误差至多 $\eta$ 。这与每次 $U$ 门实现误差不同：按逐门误差预算，后者若为 $\delta_U$ ， $d$ 次调用的逐门误差至多 $d\delta_U$ ，还要加投影相位门的误差。

若只知道编码块 $B$ 与目标收缩 $C$ 满足 $\|B-C\|\le\delta$ ，不能未经证明就把它当作整个 $U$ 的误差。在同型收缩矩阵的算子范数下，一个直接可验的多项式界是：写 $p(x)=\sum_\ell c_\ell x^\ell$ ，则

\|p^{(\mathrm{SV})}(B)-p^{(\mathrm{SV})}(C)\| \le\delta\sum_\ell\ell|c_\ell|. \tag{5}

对偶次项，使用 $(B^\dagger B)^k$ ，且 $\|B^\dagger B-C^\dagger C\|\le2\delta$ ；逐幂替换给 $2k\delta$ 。对奇次项，再乘左侧的 $B$ ，额外增加 $\delta$ ，得到 $(2k+1)\delta$ ，求和即为式 (5)。这个系数界可能不紧，但明确区分了块误差与门误差。

逆、滤波与适用边界

取奇多项式逼近某个缩放倒数 $c/x$ 时，必须避开零奇异值的谱隙，并让多项式在整个 $[-1,1]$ 上保持有界；只在目标谱点拟合得好而区间中间爆掉，并不满足式 (1)。

还有一个方向细节：非Hermitian $A=U_A\Sigma V_A^\dagger$ 的伪逆为 $V_A\Sigma^+U_A^\dagger$ ，所以应对 $A^\dagger$ 的奇异值施倒数变换，才能得到从左空间回到右空间的伪逆。直接对 $A$ 改成倒数奇异值，左右方向仍与伪逆相反。

不满足固定奇偶性的实目标可以拆成奇、偶两部分，再通过额外线性组合与归一化实现；这会改变辅助和尺度，不能直接冒充式 (3) 或 (4) 的一次序列。复目标也需分开处理实、虚部分。QSVT统一了很多构造，但并没有删除输入、归一化、后选择和读出成本。

参考资料

[1] András Gilyén, Yuan Su, Guang Hao Low and Nathan Wiebe, Quantum Singular Value Transformation and Beyond, 2018作者版，§3.1 Corollary 8，§3.2 Lemma 14、Definitions 15–16、Theorem 17、Corollary 18与Lemma 19：反射信号约定、交替序列、左右空间及实多项式辅助实现；§3.3讨论更精细的稳健性。本页式 (5) 为独立展开的系数级保守界。

形式陈述 ​

左右二维空间怎样出现 ​

序列和额外实部辅助具体指什么 ​

x立方的三查询非对称例子 ​

原矩阵尺度、逼近误差和实现误差 ​