Pretty Good Measurements and HSP

我偶然在一把小刀上发现了异国的一粒微尘 —— 世界顿时又变得奇异万状，缭绕着五彩缤纷的氤氲。

$\newcommand{\bZ}{\mathbb{Z}}$

# Pretty Good Measurements

参考：Theory of Quantum Information

考虑这样一个 discriminate quantum states from an ensemble 的问题：

给定一个 ensemble $\eta:\Sigma\to \mathcal{D}(\mathcal{H})$，其中$\Sigma$ 是一个有限集合，$\eta$ 满足：

$$\sum_{a\in\Sigma}Tr(\eta(a))=1.$$

理解为：整个系统以一个$Tr(\eta(a))$ 的先验概率处于状态$\eta(a)$。
现在我们希望设计一个 POVM 测量$\mu:\Sigma\to Pos(\mathcal{H})$ 使得

$$\sum_{a\in\Sigma}\langle \mu(a),\eta(a)\rangle$$

尽量大。
理解为：我们希望设计一个测量，使得测量结果得到系统所处状态的概率尽量大。

换句话说，我们希望通过设计一个最 general 的测量，来大概率分辨一个以已知的先验概率处于已知的状态集合的系统，究竟处于哪个状态。

很显然，如果我们把 ensemble 嵌到一个更大的经典 - 量子混合状态：

$$A=\sum_{a\in\Sigma}|a\rangle\langle a|\otimes \eta(a)\in \mathcal{D}(\mathcal{H}'\otimes\mathcal{H}),$$

其中$\mathcal{H}'$ 就是经典部分的系统

那么原问题可以转化为一个规划问题：

$$\begin{aligned} & \text{maximize} && \langle A,X\rangle\\ & \text{subject to}&& Tr_{\mathcal{H}'}(X)=I,\\ & && X\in Pos(\mathcal{H}'\otimes\mathcal{H}).\\ \end{aligned}$$

注意，这里把一个测量嵌到了一个经典 - 量子混合状态。

$$X=\sum_{a\in\Sigma}|a\rangle\langle a|\otimes \mu(a)$$

在这个规划问题中，我们并没有强行要求$X$ 是上面的形式。实际上，对于所有满足$Tr_{\mathcal{H}'}(X)=I$ 的$X$，都可以找到一组对应的测量：

$$E_a=(\langle a|\otimes I) X (|a\rangle\otimes I).$$

我们把这个问题和它的对偶问题放在一起看

$$\begin{aligned} & && \text{Primal Problem}\\ & \text{maximize} && \langle A,X\rangle\\ & \text{subject to}&& Tr_{\mathcal{H}'}(X)=I,\\ & && X\in Pos(\mathcal{H}'\otimes\mathcal{H}).\\ \end{aligned} \qquad \qquad \begin{aligned} & && \text{Dual Problem} \\ & \text{minimize} && Tr(Y)\\ & \text{subject to}&& I\otimes Y\geq A,\\ & && X\in Herm(\mathcal{H}).\\ \end{aligned}$$

那么 strong duality 实际上存在：

$$X=\frac{1}{|\Sigma|}I\otimes I,\qquad Y=\gamma I$$

根据 strong duality 和 slater’s theorem 我们知道这两个问题可以取到最优解且最优解是相等的。

但是往往我们很难把最优解的$X$ 写成一个关于$A$ 的 analytic description。
所以 Pretty Good Measurement 就是在一个能够显式构造出 measurement 的情况下，给出一个近似的最优解。

我们定义 PGM 测量：

$$\mu(a)=\rho^{-1/2}\eta(a)\rho^{-1/2},\qquad\text{其中 } \rho=\sum_{a\in\Sigma}\eta(a).$$

如果$\rho$ 不可逆，那我们需要采用 Moore–Penrose pseudo-inverse:

$$\mu(a)=\sqrt{\rho^+}\eta(a)\sqrt{\rho^+}+\frac{1}{|\Sigma|}\Pi_{\ker\rho},$$

其中$\Pi_{\ker\rho}$ 是$\rho$ 缺少的 eigenspace 部分的投影算子。
我们可以证明

Proof: 因为$supp(\eta(a))\subseteq supp(\rho),im(\eta(a))\subseteq im(\rho)$，我们知道 pseudo-inverse 在它的像空间中就起到了 inverse 的作用（即$\rho\rho^+=\Pi_{im(\rho)},\rho^+\rho=\Pi_{supp(\rho)}$），所以对于一个测量$\nu$，我们有

$$\begin{aligned} \langle\rho^{1/4}\nu(a)\rho^{1/4},(\rho^+)^{1/4}\eta(a)(\rho^+)^{1/4}\rangle &= Tr(\nu(a)\Pi_{im(\rho)}\eta(a)\Pi_{supp(\rho)})\\ &=Tr(\nu(a)\eta(a))\\ &=\langle \nu(a),\eta(a)\rangle.\\ \end{aligned}$$

根据 Cauchy–Schwarz 不等式，

$$\langle \nu(a),\eta(a)\rangle\leq \left \|\rho^{1/4}\nu(a)\rho^{1/4} \right \|_2\left \|(\rho^+)^{1/4}\eta(a)(\rho^+)^{1/4} \right \|_2.$$

再用一次 Cauchy–Schwarz 不等式，

$$\sum_{a\in\Sigma}\langle \nu(a),\eta(a)\rangle\leq \sqrt{\sum_{a\in\Sigma}\left \|\rho^{1/4}\nu(a)\rho^{1/4} \right \|_2^2}\sqrt{\sum_{a\in\Sigma}\left \|(\rho^+)^{1/4}\eta(a)(\rho^+)^{1/4} \right \|_2^2}.$$

其中左侧根号的值不会超过 1，因为

$$\left \|\rho^{1/4}\nu(a)\rho^{1/4} \right \|_2^2=\langle \rho^{1/4}\nu(a)\rho^{1/4},\rho^{1/4}\nu(a)\rho^{1/4}\rangle=\langle \nu(a),\sqrt{\rho}\nu(a)\sqrt{\rho}\rangle\leq Tr(\sqrt{\rho}\nu(a)\sqrt{\rho})=Tr(\nu(a)\rho).$$

所以 sum over 所有$a\in\Sigma$ 后，就不会大于$\sum_{a\in\Sigma}Tr(\nu(a)\rho)=Tr(\rho)=1$。

同样地，对于右侧根号，我们知道

$$\left \| (\rho^+)^{1/4}\eta(a)(\rho^+)^{1/4}\right \|_2^2=\langle \sqrt{\rho^+}\eta(a)\sqrt{\rho^+},\eta(a)\rangle\leq \langle \mu(a),\eta(a)\rangle.$$

所以

$$\sum_{a\in\Sigma}\left \| (\rho^+)^{1/4}\eta(a)(\rho^+)^{1/4}\right \|_2^2\leq \sum_{a\in\Sigma}\langle \mu(a),\eta(a)\rangle.$$

因此，我们得到了

$$\left (\sum_{a\in\Sigma}\langle \nu(a),\eta(a)\rangle\right )^2\leq \sum_{a\in\Sigma}\langle \mu(a),\eta(a)\rangle.$$

这对所有的测量$\nu$ 都成立，所以 PGM $\mu$ 至少是一个平方近似比。
$\square$

我们补充一个判断一个测量是否是 optimal 的办法：

此外，我们知道，如果$\eta$ 每个状态之间比较 “不相似”，那么 PGM 的成功概率会更高。

换句话说，如果两两状态之间的 fidelity 比较小（不相似），那么 PGM 的成功概率会更高。

# PGM for Dihedral Hidden Subgroup Problem

参考：OPTIMAL MEASUREMENTS FOR THE DIHEDRAL HIDDEN SUBGROUP PROBLEM

在之前的一篇 Blog Kuperberg’s algorithm for the dihedral Hidden Subgroup Problem 中，我们讨论过 Dihedral group 其实是$\mathbb{Z}_N\rtimes\mathbb{Z}_2$，以及不失一般性地我们可以假设隐含子群为$H=\{(0,0),(d,1)\}$，其中$d\in \mathbb{Z}_N$。
然后通过 Fourier 变化，我们可以以相同的概率得到某个$x\in \mathbb{Z}_N$ 和状态

$$|\psi_{x,d}\rangle=\frac{1}{\sqrt{2}}|x\rangle(|0\rangle+\omega^{xd}_N|1\rangle).$$

或者说，我们得到了 hidden subgroup states

$$\rho_d=\frac{1}{N}\sum_{x\in\mathbb{Z}_N}|\psi_{x,d}\rangle\langle \psi_{x,d}|=\frac{1}{2N}\sum_{x\in\mathbb{Z}_N}\sum_{a,b\in\mathbb{Z}_2}\omega_N^{xd(a-b)}|x,a\rangle\langle x,b|.$$

我们复制$k$ copies，就得到

$$\rho_d^{\otimes k}=\frac{1}{(2N)^k}\sum_{x\in\mathbb{Z}_N^k}\sum_{a,b\in \mathbb{Z}_2^k}\omega_N^{((a-b)\cdot x)d}|x,a\rangle\langle x,b|,$$

其中$(a-b)\cdot x$ 是按位点乘。

进一步地，令

$$S_r^x=\{b\in\mathbb{Z}_2^k:b\cdot x=r\mod N\},\qquad \eta^x_r=|S_r^x|,$$

和状态

$$|S_r^x\rangle=\frac{1}{\sqrt{\eta_r^x}}\sum_{b\in S_r^x}|b\rangle.$$

特别地，如果$|\eta^x_r|=0$，那么默认$|S^x_r\rangle=|0\rangle$。

然后$k$-copies of hidden subgroup states 可以写成

$$\rho_d^{\otimes k}=\frac{1}{(2N)^k}\sum_{x\in\mathbb{Z}_N^k}\sum_{p,q\in\mathbb{Z}_N}\omega^{d(p-q)}\sqrt{\eta_p^x\eta_q^x}|x,S_p^x\rangle\langle x,S_q^x|.$$

即我们把前面相位相同的$a,b$ 那部分放在一起作一个均匀叠加态。

此时相当于我们有了个 ensemble，以$\frac{1}{N}$ 的先验概率处于状态$\rho_d^{\otimes k}$，那么可以用 PGM 来以一定概率得到$d$。

具体地，令

$$\begin{aligned} G&:=\sum_{d\in\mathbb{Z}_N}\rho_d^{\otimes k}\\ &=\frac{1}{(2N)^k}\sum_{x\in\mathbb{Z}_N^k}\sum_{p,q\in\mathbb{Z}_N}\left (\sum_{d\in\mathbb{Z}_N}\omega^{d(p-q)}\right )\sqrt{\eta_p^x\eta_q^x}|x,S_p^x\rangle\langle x,S_q^x|\\ &=\frac{N}{(2N)^k}\sum_{x\in\mathbb{Z}_N^k}\sum_{r\in\mathbb{Z}_N}\eta_r^x|x,S_r^x\rangle\langle x,S_r^x|. \end{aligned}$$

这里实际上用到了特征标的正交性。虽然在 dihedral group 里具体到了单位根，但是实际上对于一般的特征标也成立。
这也是我理解为什么需要先做一次 Fourier 变化的原因，可以通过特征标使得$G$ 直接就是对角的。

那么我们构造 PGM 为

$$\begin{aligned} E_d&=G^{-1/2}\rho_d^{\otimes k}G^{-1/2}\\ &=\frac{1}{N}\sum_{x_1,x_2,y\in\mathbb{Z}_N^k}\sum_{r_1,r_2\in\mathbb{Z}_N}\sum_{p,q\in\mathbb{Z}_N}\frac{\omega^{d(p-q)}\sqrt{\eta_p^y\eta_q^y}}{\sqrt{\eta_{r_1}^{x_1}\eta_{r_2}^{x_2}}}|x_1,S_{r_1}^{x_1}\rangle\langle x_1,S_{r_1}^{x_1}|y,S_p^y\rangle\langle y,S_q^y|x_2,S_{r_2}^{x_2}\rangle\langle x_2,S_{r_2}^{x_2}|\\ &=\frac{1}{N}\sum_{x\in\mathbb{Z}_N^k}\sum_{p,q\in\mathbb{Z}_N}\omega^{d(p-q)}|x,S_p^x\rangle\langle x,S_q^x|.\\ \end{aligned}$$

我们可以利用之前的 Holevo–Yuen–Kennedy–Lax 定理来说明，这个测量是 optimal 的（用于区分$\rho_d^{\otimes k}$）。
注意到

$$\begin{aligned} Y&=\sum_{d\in\mathbb{Z}_N}\rho_d^{\otimes k}E_d\\ &=\frac{1}{N(2N)^k}\sum_{d\in\mathbb{Z}_N}\sum_{x,y\in\mathbb{Z}_N^k}\sum_{p,q,p',q'\in\mathbb{Z}_N}\omega^{d(p-q+p'-q')}\sqrt{\eta_p^x\eta_q^x}|x,S_p^x\rangle\langle x,S_q^x|y,S_{p'}^y\rangle\langle y,S_{q'}^y|\\ (q=p',x=y)&=\frac{1}{N(2N)^k}\sum_{x\in\mathbb{Z}_N^k}\sum_{p,q,q'\in\mathbb{Z}_N}\sum_{d\in\mathbb{Z}_N}\omega^{d(p-q')}\sqrt{\eta_p^x\eta_q^x}|x,S_p^x\rangle\langle x,S^x_{q'}|\\ (p=q')&=\frac{1}{(2N)^k}\sum_{x\in\mathbb{Z}_N^k}\sum_{p,q\in\mathbb{Z}_N}\sqrt{\eta_p^x\eta_q^x}|x,S_p^x\rangle\langle x,S_p^x|.\\ \end{aligned}$$

那么很显然$Y$ 是 Hermitian 的，并且我们重写$\rho^{\otimes k}_d$ 为

$$\rho_d^{\otimes k}=\sum_{x\in\mathbb{Z}_N^k}|x,\rho_d^x\rangle\langle x, \rho_d^x|,\qquad \text{其中 }|\rho_d^x\rangle=\frac{1}{(2N)^{k/2}}\sum_{p\in\mathbb{Z}_N}\omega^{dp}\sqrt{\eta_p^x}|S_p^x\rangle.$$

换句话说，$\rho_d^{\otimes k}$ 是分块对角的，每个对角元素是一个 rank 1 的矩阵。

那么可以验证

$$\langle x,\rho_d^x|Y|x,\rho_d^x\rangle=\frac{1}{(2N)^k}\sum_{p,q\in\mathbb{Z}_N}\eta_p^x\sqrt{\eta_p^x\eta_q^x}\geq \frac{1}{(2N)^k}\sum_{q\in\mathbb{Z}_N}\eta_p^x=\langle x,\rho_d^x|\rho_d^{\otimes k}|x,\rho_d^x\rangle.$$

也就是说，$Y\geq \rho_d^{\otimes k}$。

注意到$\sum_dE_d<I$ 并没有张满整个空间，那么我们单独引入一个$E_e=I-\sum_{d\in\mathbb{Z}_N}E_d$ 来表示得到这个测量结果时，输出 trivial hidden subgroup $\{(0,0)\}$。

接下来我们分析成功概率。对于一个 hidden subgroup $H=\{(0,0),(d,1)\}$，我们会发现成功概率其实和$d$ 无关（这里小心点计算，类似计算$Y$ 的第二步，实际上有$p=q'$ 然后$\omega^{d(p-q')}=1$）：

$$p=Tr(E_d\rho_d^{\otimes k})=\frac{1}{N(2N)^k}\sum_{x\in\mathbb{Z}_N^k}\sum_{p,q\in\mathbb{Z}_N}\sqrt{\eta_p^x\eta_q^x}=\frac{1}{2^{k+1}N^k}\sum_{x\in\mathbb{Z}_N^k}\left (\sum_{r\in\mathbb{Z}_N}\sqrt{\eta_r^x}\right )^2.$$

令$\nu=k/\log N$，Childs et al. 做了个结果：

我们首先引入一个 lemma。其实可以注意到$x\cdot b\equiv r\mod N$ 本质上是一个 subset-sum 问题，$b\in\mathbb{Z}_2^k$ 决定了$x$ 中哪些元素被选中。

Proof: 考虑对于每个$b\in\mathbb{Z}_2^k,b\neq 0$，定义一个随机变量$X_b$ 为：

$$X_b=\begin{cases} 1, & \text{if }b\cdot x=r\mod N;\\ 0, & \text{otherwise}. \end{cases}$$

那么实际上有

$$\eta_r^x\geq\sum_{0\neq b\in\mathbb{Z}_2^k}X_b.$$

因为我们没有考虑$b=0$ 的情况，后面会告诉为什么。

下面我们用 Chebyshev 不等式分析一下右侧随机变量的和。

$$\mathop{\mathbb{E}}_{x}\left [\sum_{0\neq b\in\mathbb{Z}_2^k}X_b\right ]=\sum_{0\neq b\in\mathbb{Z}_2^k}\mathbb{E}_x[X_b]=\sum_{0\neq b\in\mathbb{Z}_2^k}\Pr_{x}(b\cdot x=r)=\frac{2^k-1}{N}.$$

注意，固定了$0\neq b\in\mathbb{Z}_2^k,r\in\mathbb{Z}_N$，然后均匀随机选取$x\in\mathbb{Z}_N^k$ 的话，$b\cdot x$ 是均匀分布在$\mathbb{Z}_N$ 上的。
但是如果$b=0$，那么$b\cdot x$ 就不是均匀分布在$\mathbb{Z}_N$ 上了，而是恒等于 0。

所以$\Pr_x(b\cdot x=r)=1/N$，如果$b\neq 0$。

令$\mu=\mathbb{E}(\sum_bX_b)\sigma^2=Var(\sum_bX_b)$，根据 Chebyshev 不等式我们知道

$$\Pr_x\left ( \sum_bX_b\leq \frac{1}{2}\mu\right )\leq\frac{4\sigma^2}{\mu^2}.$$

接下来，我们可以证明，$X_b$ 之间是相互独立的。不妨考虑两个不同的$b,b'\in\mathbb{Z}_2^k$，其中不失一般性地$b_1=1, b_1'=0$（第一位），那么有

$$\begin{aligned} \Pr_x[X_b=1\wedge X_{b'}=1]&=\mathbb{E}_{x_2,...,x_k}[\Pr_{x_1}(X_b=1\wedge X_{b'}=1)]\\ &=\mathbb{E}_{x_2,...,x_k}[1/N\cdot \delta_{X_{b'},1}]\\ &=\frac{1}{N}\Pr_{x_2,...,x_k}(X_{b'}=1)\\ &=\Pr_x(X_b=1)\Pr_x(X_{b'}=1).\\ \end{aligned}$$

其中，第二个等式是因为，$X_{b'}$ 和$x_1$ 无关，但是给定$x_2,...,x_k$ 后，$X_b=1$ 的概率是$1/N$。
所以

$$\sigma^2=Var\left (\sum_bX_b\right )=\sum_bVar(X_b)=\frac{(2^k-1)(N-1)}{N^2}\leq \frac{2^k-1}{N}.$$

因此，

$$\Pr_x\left (\eta_r^x\leq \frac{2^k-1}{2N}\right )\leq \Pr_x\left (\sum_{0\neq b\in\mathbb{Z}_2^k}X_b\leq \frac{2^k-1}{2N}\right )\leq \frac{4N}{2^k-1}.$$

$\square$

接下来，我们可以证明之前的定理。
Proof: 注意到利用 Cauchy 不等式，成功的概率为

$$p=\frac{1}{N(2N)^k}\sum_{x\in\mathbb{Z}_N^k}\left (\sum_{r\in\mathbb{Z}_N}\sqrt{\eta_r^x}\right )^2\geq\frac{1}{2^kN}\left (\frac{1}{N^k}\sum_{x\in\mathbb{Z}_N^k}\sum_{r\in\mathbb{Z}_N}\sqrt{\eta_r^x}\right )^2,$$

此外，根据之前的 lemma，

$$\frac{1}{N^k}\sum_{x\in\mathbb{Z}_N^k}\sqrt{\eta_r^x}\geq \sqrt{\frac{2^k-1}{2N}}\Pr_x\left (\eta_r^x\geq \frac{2^k-1}{2N}\right )\geq \sqrt{\frac{2^k-1}{2N}}-\sqrt{\frac{8N}{2^k-1}}.$$

因此，注意到$k>\log N+4$，

$$\begin{aligned} p&\geq \frac{N}{2^k}\left (\sqrt{\frac{2^k-1}{2N}}-\sqrt{\frac{8N}{2^k-1}}\right )^2\\ &\geq \frac{N}{2^k}\left (\frac{2^k-1}{2N}-4\right )\\ &=\frac{1}{2}-\frac{1}{2^{k+1}}-\frac{4N}{2^k}\\ &\geq\frac{1}{8}.\\ \end{aligned}$$

对于上界，我们有

$$p\leq \frac{1}{2^kN^{k+1}}\sum_{x\in\mathbb{Z}_N^k}\left (\sum_{r\in\mathbb{Z}_N}\eta_r^x\right )^2=\frac{2^k}{N}.$$

$\square$

# PGM 的实现

还是接上文讨论。我们考虑，如何实现 PGM 测量。
换句话说，我们希望有一个酉变换$U$，使得对于一个状态$\rho$，我们执行 POVM 测量$\{E_d:d\in\mathbb{Z}_N\}$ 等价于在状态$U\rho U^\dagger$ 下进行 computational basis 的测量（PVM）。

我们考虑之前的 POVM 表达式，交换一下第一第二寄存器，

$$E_d=\frac{1}{N}\sum_{x\in\mathbb{Z}_N^k}\sum_{p,q\in\mathbb{Z}_N}\omega^{d(p-q)}|x,S_p^x\rangle\langle x,S_q^x|=\sum_{x\in\mathbb{Z}_N^k}E_d^x\otimes |x\rangle\langle x|,$$

其中

$$E_d^x=\frac{1}{N}\sum_{p,q\in\mathbb{Z}_N}\omega^{d(p-q)}|S_p^x\rangle\langle S_q^x|.$$

那么，直接进行 POVM $\{E_d:d\in\mathbb{Z}_N\}$ 得到$d$ 的概率，就等价于先测量第二寄存器$x$，然后基于$x$ 测量第一寄存器$E_d^x$ 得到$d$。直觉上：

$$p(d)=\sum_x p(d\mid x)p(x).$$

形式化地，

$$Tr(E_d\rho)=\sum_{x\in\mathbb{Z}_N^k}Tr\left (E_d^x\cdot \frac{\langle x|\rho|x\rangle}{Tr(\langle x|\rho|x\rangle)}\right )Tr(\langle x|\rho|x\rangle),$$

其中，$\frac{\langle x|\rho|x\rangle}{Tr(\langle x|\rho|x\rangle)}$ 是测量第二寄存器后，得到$x$ 时第一寄存器坍塌进入的状态。

下面问题是，给定$x\in\mathbb{Z}_N^k$，我们需要实现测量$\{E_d^x:d\in\mathbb{Z}_N\}$。
根据 Neumark 定理，我们总是可以通过扩大空间，使得 POVM 被转化成更大空间上的一个 PVM。具体地，可以构造一个 block-encoding unitary operator

$$U^x=\begin{pmatrix} V^x & A^x\\ B^x & C^x \end{pmatrix}$$

其中$V^x=\frac{1}{\sqrt{N}}\sum_{j,q\in\mathbb{Z}_N}\omega^{-jq}|j\rangle\langle S_q^x|$，其他$A^x,B^x,C^x$ 是为了保证 unitary。

这样对一个状态$\rho$ 进行$\{E_d^x:d\in\mathbb{Z}_N\}$ 的 POVM 测量就等价于，对$U^x(|0\rangle\langle 0|\otimes \rho)(U^x)^\dagger$ 进行$\{|0\rangle\langle 0|\otimes |j\rangle\langle j|:j\in \mathbb{Z}_N\}$ 的测量。
这是因为：

$$\langle j|V^x\rho (V^x)^\dagger |j\rangle=Tr(E_j^x\rho).$$

所以我们要想办法实现$U^x$。进一步地，我们尝试实现$FU^x$，其中$F$ 是空心 controlled QFT 算子。即

$$\begin{aligned} FU^x&=F(|0\rangle\langle 0|\otimes V^x+|0\rangle\langle 1|\otimes A^x+|1\rangle\langle 0|\otimes B^x+|1\rangle\langle 1|\otimes C^x)\\ &=|0\rangle\langle 0|\otimes \tilde{V}^x+|0\rangle\langle 1|\otimes \tilde{A}^x+|1\rangle\langle 0|\otimes B^x+|1\rangle\langle 1|\otimes C^x, \end{aligned}$$

其中

$$\tilde{V}^x=\frac{1}{N}\sum_{j,p,q\in\mathbb{Z}_N}\omega^{j(p-q)}|p\rangle\langle S_q^x|=\sum_{p\in\mathbb{Z}_N}|p\rangle\langle S_p^x|.$$

所以如果我们能实现 unitary transformation

$$|p,x\rangle\mapsto\begin{cases} |S_p^x,x\rangle, & \text{if }S_p^x\neq \emptyset;\\ |\psi_p^x\rangle, & \text{otherwise}, \end{cases}$$

这部分有点糙，位数都对不上。不过自己算着玩一下就会发现，想要从 computational basis 的测量到$E_d$，需要能够制备$|S_p^x\rangle$ 状态。

其中$|\psi_p^x\rangle$ 可以是任意一个状态满足 unitary 的限制，那么我们就可以实现$FU^x$。

注意，这里我觉得要求变强了。本来可以测量到$x$ 后，根据$x$ hard-code 一个线路，但是这边却要求了一个 coherent 的实现。

如果对于任意的$x$ 我们都可以高效实现$FU^x$，那么 subset sum problem 就量子可解了。
因为对于$(x,t)\in\mathbb{Z}_N^k\times \mathbb{Z}_N$，我们想求解一个$b\in\mathbb{Z}_2^k$ 使得$x\cdot b\equiv t\mod N$ 时，只需要作用$(FU^x)^\dagger$ 得到

$$(FU^\dagger)(|0\rangle\langle 0|\otimes |t\rangle\langle t|)(FU^x)=|0\rangle\langle 0|\otimes |S_t^x\rangle\langle S_t^x|+...$$

那么就可以得到一个满足条件$b$ 的均匀叠加态。

总之，PGM 的高效实现几乎等价于 subset sum problem 的高效量子算法。

着应该并不简单，但是好的是我们只需要考虑$\nu=k/\log N>1$ 的情况，这里$\nu$ 会被称为 density
在 subset sum problem 的研究中，$\nu\sim 1$ 是个非常重要的分界线。对于足够大或足够小的$\nu$，subset sum problem 会更 tractable 一些。
譬如当$\nu<0.941$ 时，可以规约到 SVP 问题上，然而 SVP 也很困难。当$\nu$ 特别小时，$k<c\sqrt{\log N}$ 对于某个常数$c$，那么 subset sum problem 是可以多项式时间求解的。

对于很大的$\nu$ 时，$k>cN$ 的情况时 subset sum problem 也是可以求解的，但这时对于量子算法并不高效（指数级别了）。其次就只有一些 sub exponential 的算法了（譬如 Kuperberg）。

原文还有一个 comment，就是虽然直接 measure $x$ 是一个自然的办法，但不一定是唯一的做法。有可能可以不通过 measure $x$，然后就不用求解 subset sum problem 来实现这个 measurement。