Search with Wildcard Problem

Posted on Edited on

Abstract.

问题背景

本文考虑 search with wildcard 问题：

问题 1.1（search with wildcard）. 有一个长度为 $N$ 的隐藏的字符串 $\boldsymbol{b}\in \{0, 1\}^N$。给定 $b$ 的如下 oracle 访问：给定 $S\subseteq [N]$ 和字符串 $\boldsymbol{y}\in \{0, 1\}^{|S|}$，有

$$
\mathrm{O}_{\boldsymbol{b}} |S\rangle|\boldsymbol{y}\rangle|z\rangle = |S\rangle|\boldsymbol{y}\rangle|z \oplus \mathbf{1}\{\boldsymbol{b}_S = \boldsymbol{y}\}\rangle
$$

求 $\boldsymbol{b}$。

关于这个问题，已知：

  • 有一个 Information Theoretic Argument 证明经典算法询问复杂度下界是 $\Omega(n)$。
  • 如果 oracle 限制 $|S| = 1$，也就是你只能问一位，那么量子有 $n / 2 + \Omega(\sqrt n)$ 的询问复杂度下界，也有 $n / 2 + O(\sqrt n)$ 的算法。
  • 如果你问的问题是 $\boldsymbol{y}$ 是否是 $\boldsymbol{x}$ 的子串？那么有 $\Omega(n / \log^2 n)$ 的 Quantum Lowerbound。

$O(\sqrt n\log n)$ 算法

这个问题的量子加速，主要依赖于以下这个引理：

引理 2.1. 对于 $n\geq 1$，$k = n - O(\sqrt n)$。如果我们能制备这个态：

$$
|\psi_x^k\rangle := \frac{1}{\binom nk^{1/2}}\sum_{S\subseteq [n], |S| = k}|S\rangle|x_S\rangle
$$

则存在一个对 $|\psi_x^k\rangle$ 的正算子值测度下的测量（POVM Measurement），输出 $\widetilde{x}$，其中 $\mathbb{E}[d(x, \tilde{x})] = O(1)$。$d(\cdot, \cdot)$ 是 Hamming Distance。

也就是说，如果叠加地丢了 $O(\sqrt n)$ 位信息，量子算法仍然能够把原信息还原出来。注意，拿到了一个期望 Hamming distance 与原来差不多的串，可以用期望 $O(\log n)$ 次询问来彻底修复它。做法是进行 $O(1)$ 次二分。

有了这个引理之后，算法就非常显然了。我们取一列 $n_1, …, n_l$，其中 $n_1 = O(1), n_l = n$，且 $n_{i - 1} = n_i - O(\sqrt n_i)$。记

$$
|\psi_x^i\rangle = \frac{1}{\binom{n}{n_i}^{1/2}}\sum_{S\subseteq [n], |S| = k} |S\rangle|x_S\rangle
$$

我们的目标是 $|\psi_x^l\rangle$。显然有 $|\psi_x^1\rangle$ 是很好制备的。从 $|\psi_x^{i - 1}\rangle$ 制备 $|\psi_x^i\rangle$ 无非是一次 POVM 然后进行修复。

Remark 1. 容易证明这个序列的长度是 $\Theta(\sqrt n)$。考虑这个迭代 $f(n) = n - \sqrt n$，它套 $O(\sqrt n)$ 次之后可以让 $n$ 除以一个常数，再等比数列求和立即得证。

Remark 2. 可以看到这个算法成立是因为问题满足以下两个要点：

  1. 可以 $O(1)$ 获取 $O(1)$ 位信息的叠加态；
  2. 可以 $O(\log n)$ 纠错一位。

State Discrimination Problem

欲证明的引理 2.1 是一个态区分问题：我们希望知道我们制备的 $|\psi_{\color{orange} x}\rangle$ 究竟是哪个 ${\color{orange} x}$ 对应的。然而，我们熟知这个事情是不能精确做到的（根据 Indistinguishability Theorem）。现在我们来准备一些工具。

正算子值测度

接下来引入所谓的正算子值测度，以及这种测度下面的测量如何实现。首先我们回顾一下我们熟悉的测量使用的投影值测度。

定义 3.1（投影值测度，PVM）. 给定希尔伯特空间 $\mathcal{H}$ 和 Borel 集 $X$，其上的 $\sigma$-代数记作 $M$。$\mathcal{H}$ 上一个关于 $X$ 的投影值测度是一个 $X\rightarrow \mathscr{P}(\mathcal{H})$（此处 $\mathscr{P}(\mathcal{H})$ 为 $\mathcal{H}$ 上全体投影算符）的映射，满足：

  1. $\pi(\varnothing) = \mathbf{0}, \pi(X) = \mathbf{I}$；
  2. 对于一列不相交的 $E_1, E_2, …\in M$，有
    $$
    \pi\left(\bigsqcup_{i = 1}^\infty E_i\right) = \sum_{i = 1}^\infty \pi(E_i)
    $$
  3. 对于任意的 $E_1, E_2\in M$，有 $\pi(E_1\cup E_2) = \pi(E_1)\pi(E_2)$。当然很明显这一条是前两条的推论。

这里的 Borel-可测的集合 $X$ 可以被理解为测量结果的集合。常见的 $X$ 有：

  1. $\mathbb{R}, \mathbb{R}^3$ 之类的集合，表示位置、动量等；
  2. $\{0, 1\}$ 之类的有限集，量子比特。

在一个 PVM $\pi$ 下测量一个 $\mathcal{H}$ 中的量子态 $|\psi\rangle$ 进行测量，结果落在 $E\in M$ 中的概率为

$$
\Pr[E] = \langle \psi| \pi(E) |\psi\rangle
$$

若测量结果为 $x$，则测量后态为

$$
\frac{\pi(x)|\psi\rangle}{\langle\psi|\pi(x)|\psi\rangle^{1/2}}
$$

定义 3.2（正算子值测度，POVM）. 给定希尔伯特空间 $\mathcal{H}$ 和 Borel 集 $X$，其上的 $\sigma$-代数记作 $M$。$\mathcal{H}$ 上一个关于 $X$ 的投影值测度是一个 $X\rightarrow \mathscr{L}(\mathcal{H})$（此处 $\mathscr{L}(\mathcal{H})$ 为 $\mathcal{H}$ 上全体正自伴随有界算符）的映射 $\textsf{E}$，满足：

  1. $\textsf{E}(\varnothing) = \mathbf{0}, \textsf{E}(X) = \mathbf{I}$；
  2. 对于一列不相交的 $E_1, E_2, …\in M$，有
    $$
    \textsf{E}\left(\bigsqcup_{i = 1}^\infty E_i\right) = \sum_{i = 1}^\infty \textsf{E}(E_i)
    $$

对于一个量子态，其密度矩阵为 $\rho$，在 POVM $\textsf{E}$ 下测量结果在 $E$ 中的概率为

$$
\Pr[E] = \mathrm{tr}(\rho \textsf{E}(E))
$$

直觉上来说，POVM 之于 PVM，就是混态之于纯态。事实上，POVM 总是可以嵌入到高维空间后用 PVM 实现。我们有如下的定理：

定理 3.1（Naimark’s Dilation Theorem）. 设 $\textsf{E}$ 是 $\mathcal{H}_A$ 上的一个 POVM，则存在一个 $\mathcal{H}_B$ 及其上的 PVM $\pi$ 和一个 $\mathcal{H}_A \rightarrow \mathcal{H}_B$ 的保距映射 $V$，使得对于任意的 $E\in M$，有

$$
\textsf{E}(E) = V^*\pi(E)V
$$

当然这个定理过于抽象而不能指导我们具体怎么实现 POVM。这里我们考虑有限集 $X = \{1, 2, …, n\}$。则可以令

  • $\mathcal{H}_B = \mathcal{H}_A\otimes \mathcal{H}_{A’}$，$\mathcal{H}_{A’}$ 是一个 $n$ 维希尔伯特空间；
  • $\pi(i) = \mathbf{I}_A \otimes |i\rangle\langle i|$，这构成 $\mathcal{H}_B$ 上的一组 PVM。
  • $V = \sum_{i = 1}^n \sqrt{\textsf{E}(i)}\otimes |i\rangle$，这是一个 $\mathcal{H}_A$ 到 $\mathcal{H}_B$ 的映射，而它确实是保距的，因为 $VV^* = \mathbf{I}$。

注意到

$$
V\pi(i)V^* = \sum_{j = 1}^n \sum_{k = 1}^n \sqrt{\textsf{E}(j)\textsf{E}(k)}\otimes \langle j|i\rangle\langle i|k\rangle = \textsf{E}(i)
$$

这给出了测量的过程。假如你要做一个 POVM $\textsf{E}$，令 $U$ 是 $V$ 扩充成的 $\mathcal{H}$ 上的酉变换，首先复合上一个辅助 $n$ 维希尔伯特空间 $\mathcal{H}_{A’}$（用量子计算的语言就是加一个 ancilla $n$-qudit），然后按照 $U$ 演化，测量第二个 register。测出结果 $i$ 的概率为

$$
\mathrm{tr}(U \rho U^\dagger \pi(i)) = \mathrm{tr}(\rho U^\dagger \pi(i) U) = \mathrm{tr}(\rho \textsf{E}(i))
$$

测量后得到的态是 $U \rho U^\dagger \pi(i)$ 取 $\mathcal{H}_{A’}$ 上的偏迹。

Pretty Good Measurement

Pretty Good Measurement 对态区分问题的精确度最高的测量方法，参见 [2]。

给定一组纯态 $\{|\phi_i\rangle\}$，定义 $\rho = \sum_i |\phi_i\rangle\langle\phi_i|$，$\rho^{-1}$ 表示它的 Moore–Penrose 广义逆。定义 $|\mu_i\rangle = \rho^{-1/2}|\phi_i\rangle$，然后可以构造一个 POVM：

$$
\textsf{E}(i) = |\mu_i\rangle\langle\mu_i|
$$

为了验证这是一个 POVM，只需观察到

$$
\sum_{i}\textsf{E}(i) = \rho^{-1/2}\left(\sum_i |\phi_i\rangle\langle\phi_i|\right)\rho^{-1/2} = \mathbf{I}
$$

而对于态 $|\phi_i\rangle$，测出结果 $i$ 的概率为

$$
\mathrm{tr}\left(|\phi_i\rangle\langle\phi_i|\rho^{-1/2}|\phi_j\rangle\langle\phi_j|\rho^{-1/2}\right) = |\langle\phi_i|\rho^{-1/2}|\phi_j\rangle|^2
$$

需要注意到后面这个东西正是 $\{|\phi_i\rangle\}$ 的 Gram Matrix 的平方根，因为

$$
\sum_k \langle\phi_i|\rho^{-1/2}|\phi_k\rangle\langle\phi_k|\rho^{-1/2}|\phi_j\rangle = \langle\phi_i|\rho^{-1/2}\left(\sum_k |\phi_k\rangle\langle\phi_k|\right)\rho^{-1/2}|\phi_j\rangle = \langle\phi_i|\phi_j\rangle
$$

至此可以发现，向量组越正交，PGM 效果越好。这也非常符合直觉。

关于为什么 PGM 是 Pretty Good 的，这里暂时不证明，读者可以参考各种文献，一个比较现代的版本是 这个讲义。

完整证明

首先来补全引理 2.1 的证明，核心是分析向量组 $\{|\psi_x^k\rangle\}$ Gram 矩阵 $\mathbf{G}$。注意

$$
\langle\psi_x^k|\psi_y^k\rangle = \frac{1}{\binom nk}\sum_{|S| = k} [x_S = y_S] = \frac{\binom{n - d(x, y)}{k}}{\binom nk}
$$

因此 $G_{xy}$ 只和 $d(x, y)$ 有关，进而只和 $x\oplus y$ 有关。熟悉傅里叶变换诸多含义的读者可能知道，这种矩阵在乘法意义下同构于 $n$ 元（指标都是 $[n]$ 的子集）集合幂级数在异或卷积意义下构成的环。类似于循环矩阵可以被傅里叶变换矩阵正交对角化，这样的矩阵可以被 $n$ 维沃尔什变换（$\mathbb{F}_2^n$ 上的 FFT）矩阵对角化，特征值就是集合幂级数

$$
G(z) = \sum_{S \subseteq \{0, 1\}^n} \frac{\binom {n - |S|}{k}}{\binom nk}z^S
$$

做沃尔什变换后的诸元。计算可以知道

$$
\begin{align}
\hat{G}(x) &= \frac{1}{2^n} \binom nk^{-1}\sum_y (-1)^{x\cdot y}\binom {n - |y|}{k} = 2^{-k}\frac{\binom{n - |x|}{n - k}}{\binom nk} \label{eq:fourioer_G}
\end{align}
$$

这个组合恒等式看起来不是很显然，至少组合意义不明显，我们将证明放在附录中（引理 A.1）。

继续推进证明。尽管我们没法精确区分这些态，但我们可以 bound 住测量结果与真实结果的 Hamming Distance 的期望。考虑到矩阵的循环对称性，我们只需要算 $|\psi_x^k\rangle$ 测出的结果的模长的期望。

$$
\mathbb{E}[|\boldsymbol{y}|] = \sum_{\boldsymbol{y}\in \{0, 1\}^n} |\boldsymbol{y}|\sqrt{\mathbf{G}}_{0y}^2
$$

众所周知根据 Plancherel 定理，傅里叶变换保持内积不变。我们有

$$
\sum_{\boldsymbol{s}\in \{0, 1\}^n} f(\boldsymbol{s})h(\boldsymbol{s}) = 2^n \sum_{\boldsymbol{s}\in \{0, 1\}^n} \hat{f}(\boldsymbol{s})\hat{g}(\boldsymbol{s})
$$

我们来分析这两个东西的内积。首先令 $f(\boldsymbol{y}) = |\boldsymbol{y}|$，其傅里叶变换为

$$
\frac{1}{2^n}\sum_{\boldsymbol{x}\in \{0, 1\}^n}(-1)^{\boldsymbol{x}\cdot \boldsymbol{y}} |\boldsymbol{x}| = \begin{cases}
\frac n2 & \boldsymbol{y} = 0^n \\
-\frac 12 & |\boldsymbol{y}| = 1 \\
0 & \text{otherwise}
\end{cases}
$$

接下来要算 $h(\boldsymbol{y}) = \sqrt{\mathbf{G}}_{0y}^2$。考虑 $g(\boldsymbol{y}) = \sqrt{\mathbf{G}}_{0y}$，其傅里叶变换已经知道的 $(\ref{eq:fourioer_G})$ 的平方根。有 $h$ 实际上是 $g$ 自己点乘自己。那么做傅里叶变换之后，就有

$$
\begin{align}
\hat{h}(\boldsymbol{s}) &= \frac{1}{2^n}\sum_{\boldsymbol{t}\in \{0, 1\}^n} g(\boldsymbol{s})g(\boldsymbol{s}\oplus \boldsymbol{t}) \\
&= \frac{2^{-n - k}}{\binom nk}\sum_{\boldsymbol{t}\in \{0, 1\}^n} \binom{n - |\boldsymbol{t}|}{n - k}^{1/2}\binom{n - d(\boldsymbol{s}, \boldsymbol{t})}{n - k}^{1/2}
\end{align}
$$

我们只需要仔细计算 $|\boldsymbol{s}| = 0, 1$ 处的点值即可。$\hat{h}(\boldsymbol{0}) = 2^{-n}$ 是显然的。我们来计算 $\hat{h}(\boldsymbol{e}_i)$：

$$
\begin{align}
\hat{h}(\boldsymbol{e}_i) &= \frac{2^{-n - k}}{\binom nk}\sum_{t = 0}^n \binom{n - t}{n - k}^{1/2}\left(\binom{n - 1}{t - 1}\binom{n - t + 1}{n - k}^{1/2} + \binom{n - 1}{t}\binom{n - 1}{t}\binom{n - t}{n - k}^{1/2}\right) \\
&= 2^{-n - k}\sum_{t = 0}^k \binom{k}{t}\left(\frac{t}{n}\left(\frac{n - t + 1}{k - t + 1}\right)^{1/2} + \left(1 - \frac tn\right)\left(\frac{k - t}{n - t}\right)^{1/2}\right)
\end{align}
$$

只需要把这个括号 bound 在 $1 - O(1 / n)$ 范围内即可（$1$ 用来抵消 $0^n$ 的贡献，$O(1 / n)$ 用来确保期望模长不要太大）。此处有很多细节，我就不写了，感兴趣可以自己推：

  • 根据 Chernoff Bound，只需要考虑 $t$ 在 $\frac 12 \pm a / \sqrt n$ 范围内（$a$ 是常数）的情况即可，其他情况前面的系数是指数小的。
  • 取 $k = n - c\sqrt n$ 是欲证明引理的要求。这个参数具体怎么选出来的这里就不再追究了。
  • 用 $\sqrt x \geq \frac 23 x - \frac 12 x^2$ 放缩。

推下去确实可以 bound 住。综合起来得到 $\mathbb{E}[|\boldsymbol{y}|] = O(1)$。

$\blacksquare$

参考资料

  1. Ambainis, A. and Montanaro, A. (2014) “Quantum Algorithms for Search with Wildcards and Combinatrial Group Testing”, Quantum Information & Computation, Vol. 14, No. 5&6, pp. 439 - 453.
  2. Hausladen, P. and Wootters, W. K. (1994) “A ‘Pretty Good’ Measurement for Distinguishing Quantum States”, Journal of Modern Optics, 41(12), pp. 2385–2390. doi: 10.1080/09500349414552221.

附录

引理 A.1. 对于任意的 $\boldsymbol{x}\in \{0, 1\}^n$，$k$ 有

$$
\sum_{\boldsymbol{y}\in \{0, 1\}^n} (-1)^{\boldsymbol{x}\cdot \boldsymbol{y}} \binom{n - |\boldsymbol{y}|}{k} = 2^{n - k}\binom{n - |\boldsymbol{x}|}{n - k}
$$

证明. 首先枚举 $\boldsymbol{y}$ 的模，再枚举 $\boldsymbol{x}\cdot \boldsymbol{y}$ 有左边等于

$$
\sum_{i = 0}^n \binom{n - i}{k}{\color{blue}\sum_{j = 0}^n (-1)^j \binom{|\boldsymbol{x}|}{j}\binom{n - |\boldsymbol{x}|}{j - i}} \label{eq:krawchouk_summation}
$$

蓝色部分记作 $F(|\boldsymbol{x}|, i)$。考虑其普通型生成函数

$$
G(\boldsymbol{x}, z) = \sum_{i = 0}^n F(|\boldsymbol{x}|, i)z^i = (1 - z)^{|\boldsymbol{x}|}(1 + z)^{n - |\boldsymbol{x}|}
$$

明显 $\ref{eq:krawchouk_summation}$ 的值就是

$$
\begin{aligned}
\frac{1}{k!} \cdot \frac{\mathrm{d}^k}{\mathrm{d}z^k} z^n G(\boldsymbol{x}, z^{-1})\bigg|_{z = 1} &= \frac{1}{k!} \cdot \frac{\mathrm{d}^k}{\mathrm{d}z^k} \left((z - 1)^{|\boldsymbol{x}|}(z + 1)^{n - |\boldsymbol{x}|}\right)\bigg|_{z = 1}
\end{aligned}
$$

必须要把 $(z - 1)$ 因子全部导下来，否则代入 $z = 1$ 等于 $0$。因此答案是

$$
\frac{1}{k!}\cdot \binom{k}{|\boldsymbol{x}|} |\boldsymbol{x}|! \frac{(n - |\boldsymbol{x}|)!}{(n - k)!}2^{n - k} = 2^{n - k}\binom{n - |\boldsymbol{x}|}{n - k}
$$

$\blacksquare$