(强)指数时间假设非典型应用两则

这篇写两个指数时间假设 (ETH, exponential-time hypothesis), 以及变种强指数时间假设 (SETH, strong exponential-time hypothesis) ^[1] 的非典型应用. 指数时间假设是这么个东西:

指数时间假设 (Exponential-Time Hypothesis). 对于任何 $k$-SAT 实例, 即给定一个 $n$ 变量的布尔表达式, 在 CNF (conjunctive normal form) 下每个子句至多只有 $k$ 个变量, 判断是否存在一组赋值使得这个布尔表达式被满足. 对于任何整数 $k \geq 3$, 定义 $s_k$ 为"最小" (下确界) 的实数 $\delta$ 使得 $k$-SAT 有 $O(2^{\delta n})$ 时间的算法, 不难看出 $s_3 \leq s_4 \leq \cdots$. 于是 ETH 是说, 对于任何 $k \geq 3$, $s_k > 0$.

如果假设 ETH 正确的话, 那么 $\sf NP$-complete 问没有亚指数时间 (sub-exponential time) 算法, 即他们没有时间复杂度 $O(2^{\alpha n})$ 的算法, 其中 $\alpha$ 对任意 $\alpha >0$ 成立. 否则这样的算法, 假设多项式时间规约 (譬如 Karp 规约), 会推翻 ETH. 类似地, 这一结果也会推出 $\sf \#P$-complete 没有亚指数时间算法.

而强指数时间假设 (Strong Exponential-Time Hypothesis) 则是说, 随着 $k$ 不断增加, $s_k$ 会逐渐收敛到 $1$. 相比之下 ETH 比 SETH 会可靠一些, 原因是 SETH 依赖于某个神奇的常数, 我们知道如果直接应用 Grover 算法的话, 那么这个常数会变成 $1/2$; 因而, 也许会有一些技术, 能做到 $s_k$ 比 $1$ 小.

至于为什么说是非典型应用呢? 因为 ETH 和 SETH 是 fine-grained complexity 的核心假设, 而这一类结果通常是证明在这些假设下, 某些问题没有比平方时间更快的算法 (甚至是近似算法). 从 $\sf NP$-complete 问题相关的假设出发, 得到 $\sf P$ 里的问题的时间下界, 这也是为什么我们说这些结果是细粒度 (fine-grained) 的原因.

在本文剩下的部分, 我会介绍两个非典型的规约过程: 一个和判断量子态是否纠缠有关 (test of separability), 想起来写这个是因为在 HUJI IIAS Winter School 上 Boaz Barak 的报告介绍了^[2]; 另外一个则是用 SETH 导出最近格矢量问题 (CVP, closest vector problem) 没有亚指数时间算法 ^[3][4], 常见的几个格问题的近似版本是现代公钥密码学 (特别是量子安全的) 所依赖的主要假设之一, 而目前为止我们甚至没有这些问题的精确版本的亚指数时间算法.

下面开始正文.

判断量子纠缠有多难?

纠缠态, 可分态和凸几何

给定 $n=n_1+n_2$ 个量子比特上定义的一个量子态 $\rho$ , 判断前 $n_1$ 个量子比特和后 $n_2$ 个量子比特的部分之间有没有纠缠. 怎么用定义纠缠态呢?

可分态和纠缠态. 我们说一个量子态 $\rho$ 在 $\mathcal{H}_{n_1}$ 和 $\mathcal{H}_{n_2}$ 是可分的 (separable), 当且仅当它可以被写成一系列 $\mathcal{H}_{n_1}$ 和 $\mathcal{H}_{n_2}$ 上的纯态 $\rho^{(1)}_i:=|\psi^{(1)}_i\rangle\langle\psi^{(1)}_i|$ 和 $\rho^{(2)}_i:=|\psi^{(2)}_i\rangle\langle\psi^{(2)}_i|$ 的张量积 $\rho_i^{(1)}\otimes \rho_i^{(2)}$ 的凸组合, 即 $\rho = \sum_{i=1}^l a_i \rho_i^{(1)} \otimes \rho_i^{(2)}$ 其中 $\forall i, a_i\geq 0$ 并且 $\sum_{i=1}^l a_i =1$.

注意到所有纯态构成一个凸集, 那么由凸集分离定理 (hyperplane separation theorem), 存在一个超平面能把纠缠态 (entangled state) 和可分态 (separable state) 分开. 这个超平面可以被看成一组被称为纠缠判据 (entanglement witness) 的测量, 于是我们可以写出来下述最佳可分态问题 (best separable state):

最佳可分态问题 ( ${\sf BSS}_{c,s}$ ). 给定一个两体系统上的纠缠判据, 即在 $n=n_1+n_2$ 个量子比特上的测量 $0 \preceq M \preceq I$, 其满足下述两种情形之一 ( $0 \leq s < c \leq 1$ ): - YES case: 存在可分态 $\rho$ 使得 ${\rm Pr}[M \text{ accepts } \rho] = \langle \rho |M |\rho \rangle \geq c$ ; - NO case: 对于所有可分态 $\rho=\rho_{\phi}\otimes \rho_{\psi}$, ${\rm Pr}[M \text{ accepts } \psi\otimes \phi]=\langle \psi\otimes \phi|M|\psi\otimes \phi\rangle \leq s$. 这里的测量算符 $M$ 是个 $(d_1 \cdot d_2)\times (d_1 \cdot d_2)$ 的半正定矩阵, 其中 $d_1=2^{n_1}, d_2=2^{n_2}$.

对照前文提及的凸集分离定理, 不难看出, 上面的最佳可分态问题, 就是判断可分态对应的凸集, 和测量(纠缠判据)对应的超平面是否相交. 这里的输入规模是 $d_1,d_2$ (而不是 $n_1,n_2$ ), 这个问题有多难呢?

• Gurvits 在 2003 年证明 ^[5] 了, $c-s \geq 1/\exp(d_1,d_2)$ 的 ${\sf BSS}_{c,s}$ 是 $\sf NP$-hard 的.
• Gharibian 在 2009 年 ^[6] 把上述结果改进到了 $c-s \geq 1/{\rm poly}(d_1,d_2)$ 的 ${\sf BSS}_{c,s}$ 是 $\sf NP$-hard 的.

最佳可分态问题似乎比我们预想中要困难很多, 但是如果我们把量子比特数 $n_1,n_2$ 看成输入规模的话, 这里的 $c-s$ 的间隙是指数小的 – 看起来我们对纠缠判定的精度要求有点过高. 如果考虑更常见的精度要求呢? 比如说和 local Hamiltonian problem 一样是 $c-s\geq 1/{\rm polylog}(d_1,d_2)=1/{\rm poly}(n_1,n_2)$, 或者 $c-s$ 是常数的情形呢?

这里就有了一系列出人意料地联系:

• ETH 可以导出算法的时间 (准多项式) 下界 ^[7][8];
• Sum-of-squares 则可以给出算法的时间 (亚指数) 上界 ^[8:1], 并且后者的证明过程与 log-rank conjecture 有关.
• 此外, 这一问题也跟量子计算复杂性中公开的 ${\sf QMA(2)}$ 的上界有关.

可分态判定和量子计算复杂性

这一节我们来说一说 ${\sf BSS}_{1,1/2}$ 和量子计算复杂性理论的联系, 其中 ${\sf BSS}_{1,1/2}$ 的算法时间复杂度下界是由 ETH 导出的.

对计算复杂性理论有一些了解的读者通常都会知道 PCP 定理, 其中的一个版本是, 一个 NP-hard 的问题可以用多个证明者和一个验证者的一轮对数规模通信的交互式证明系统 ( ${\sf MIP_{log}}$ ) 来验证. 近年来对量子交互式证明系统的理解也深刻了很多 (见 一份关于 ${\sf MIP^*}={\sf RE}$ 的不太长的介绍 和 量子交互式证明可以验证停机问题吗?), 我们现在知道, 共享纠缠的多量子证明者和一个经典验证者的一轮交互对数规模通信 ( ${\sf MIP^*_{log}}$ ), 在常数的 $c-s$ 间隙下, 可以验证 NEXP-complete 完全问题.

如果我们对证明者们增加更多的限制呢? 譬如说不允许他们和验证者交互 (只能发送一次信息), 并且他们直接也不能共享纠缠. 经典计算复杂性理论中, 这样的问题被称作 Merlin-Arthur system, 并且证明了多个证明者并不会让非交互式证明的能力更强, 即 ${\sf MA} = {\sf MA(k)},k\le{\rm poly}(n)$. 那么量子情形呢?

有些出人意料地是, Aaronson, Beigi, Druker, Fefferman 和 Shor 在 2008 年证明 ^[7:1] 了$\sqrt{n} {\rm polylog }(n)$ 个不共享纠缠的量子证明者, 可以通过分别发送 $\log(n)$ 规模的信息给验证者, 来验证 $n$ 个子句的 SAT 问题, 即 ${\sf 3\text{-}SAT} \in {\sf QMA}_{\log(n)}(\sqrt{n} {\rm polylog}(n))_{1-\Omega(1),1}$. 证明者们给验证者发的量子信息的规模的总和, 与经典 PCP 定理中需要的通信规模相比有平方优势! 因为 PCP 定理中的通信规模至少是关于输入规模 $n$ 线性的.

我们能用更少的证明者来解决问题吗? Harrow 和 Montanaro 在 2010 年给出了肯定答案 ^[8:2], 他们证明了 ${\sf QMA}(2) = {\sf QMA}(k), k\leq {\rm poly}(n)$. 具体来说他们证明了下述引理:

引理 . 对于任何 $m,k,0\leq s < c\leq 1$,${\sf QMA}_m(k)_{c,s} \subseteq {\sf QMA}_{km}(2)_{c',s'}$, 其中 $c'=(1+c)/2$ 且 $s'=1-(1-s)^2/100$ .

由上述引理以及 ^[7:2] 中的验证协议, 我们只需要两个不共享纠缠的量子证明者, 分别给验证者发送 $\sqrt{n} {\rm poly log}(n)$ 规模的信息, 就可以验证 $n$ 个子句的 ${\sf 3\text{-}SAT}$ 的可满足性.

更进一步地, 如果我们假设指数时间假设 (ETH), 即 $n$ 个子句的 3-SAT 没有 ${\sf DTIME}(\exp(o(n)))$ 的算法, 即亚指数时间算法, 那么可以推出模拟不共享纠缠的两个证明者的量子非交互证明系统至少需要准多项式时间, 即 ${\sf QMA}_{\log(d)}(2)_{1,1/2} \not\subseteq{\sf DTIME}(d^{o(\log d)})$. 也就是说, 我们得到了下述定理.

定理. 假设 ETH 成立, 那么 ${\sf BSS}_{1,1/2}$ 没有比准多项式时间 $n^{o(\log n)}$ 更快的算法.

同样地, 如果上述下界是紧的, 那么 ${\sf BSS}_{0.99,0.5}$ 的准多项式时间算法可以推出 ${\sf QMA}(2) \subseteq {\sf EXP}$, 代入 $d_i=2^{n_i}, i=1,2$ 即可 (这里取 $c=0.99$ 是因为 ${\sf QMA}(2)\overset{?}{=}{\sf QMA}(2)_1$ 也是公开问题). 而 ${\sf QMA}(2)$ 目前只有平凡上界 $\sf NEXP$, 即给定一个可分态的经典描述 (指数规模), 然后直接验证. 如果允许一些不太标准的假设, 比如多项式谱系 (polynomial hierarchy) 的量子对应不会坍缩, 那么${\sf QMA}(2)$ 的上界是 ${\sf PSPACE}$ – 这和上述指数时间上界并不矛盾, 因为模拟任何多项式空间计算确实需要指数时间.

可分态判定问题的算法上界

我们对 ${\sf BSS}_{1,1/2}$ 的上界知道多少呢? 直到 Barak, Kothari 和 Steurer 在 2017 年的结果 ^[2:1] 之前, 我们都只有指数时间算法, 尽管 ^[9] 中的算法早在十五年前就给出了. ^[2:2][9:1] 用 Sum-of-squares hierarchy 给出了亚指数时间算法. 具体来说, 假设测量矩阵的维度 $d_1=d_2=d$ 的话, 那么 ^[2:3][9:2] 给出了 $2^{\tilde{O}(\sqrt{d})}$ 时间的经典确定性时间算法.

最后我试图胡乱地写几句 ^[2:4] 中的证明, Barak 的报告这部分听得我一头雾水… 假定关于秩-1 矩阵的分布存在 $\tilde{O}(\sqrt{d})$-degree moments . 输入是一个线性子空间 $W\subseteq \mathbb{R}^{d^2}$使得 $W$ 中存在秩-1 矩阵 $uu^T$(可分态是由秩-1 的纯态 $|\psi\rangle\langle \psi|$ 的凸组合), 输出是找到和 $W$ 距离为常数的 $vv^T$. [3] 中证明了下述定理, 对于秩-1 $d\times d$ 矩阵上的分布 \cal D , 存在 $\tilde{O}(d)$-degree 的多项式 $p$ 使得 $\bar{A}=\mathbb{E}[p(A) A]$ 是几乎秩-1 的. 这里的"几乎"意味着用 sum-of-squares hierarchy 生成足以乱真的 $\tilde{O}(\sqrt{d})$-degree moments.

值得一提的是, ^[2:5] 中的证明受到了 Lovett 的 sqrt-rank theorem 的证明的启发, 即给定秩-n 的通信矩阵 (communication matrix), 这一问题的通信复杂度 (communication complexity) 的上界是 $\tilde{O}(\sqrt{n})$. 而通信复杂性中著名的 log-rank conjecture 则是说问题的通信复杂度上界是 ${\rm polylog}(n)$ 的.

为什么最近格矢量问题 (CVP) 需要指数时间

不像那些证明编辑距离 (edit distance) 没有亚平方时间算法的结果, 下面的应用算得上 quantitative hardness, 但是确实不太算得上 fine-grained:

用 SETH 证明 $\mathsf{CVP}_p$ (closest vector problem) 对于大多数 $\ell_p$-norm 没有亚指数时间算法 [7]. $\mathsf{SVP}_p$ (shortest vector problem) 也有类似的结果 ^[4:1], 而这两类格问题在 $\ell_2$-norm 下已知的最好的算法是 $2^{n+o(n)}$ 时间的 ^[10].

如果能继续改进 ^[10:1] 中的算法的话, 那么可以得到诸如 SVP 和 CVP 的典型格问题的匹配的时间复杂度上下界. 尽管直觉上 CVP/SVP 的时间复杂度下界应该是和 SETH 等价的, 但是即使只考虑 SETH-based 的格问题的时间复杂度下界, 格问题的几何性质仍然制造了不小的困难 – 譬如想证明 $\ell_2$-norm 的 SVP 的时间复杂度是 $2^{\Omega(n)}$ 的话, 我们需要更多假设 ^[4:2].

什么是最近格矢量

$\mathsf{CVP}_p$ 说的是这样一个问题:

考虑一个格 $L=\{a_1\mathbf{b}_1+\cdots+a_n\mathbf{b}_n | a_i\mathbb{Z}, \mathbf{b}_i\in\mathbb{R}^d\}$, 其中 ${B}=\{\mathbf{b}_i\}_{1\leq i\leq n}$ 是一组线性无关的向量 (基), $n$ 被称为这个格的秩, 而 $d$ 是格所在的空间的维度 (ambient dimension). 给定一个点 $\mathbf{t}\in\mathbb{R}^d$, 那么它到格上点的最短距离 $\mathrm{dist}_p(\mathbf{t},\mathcal{L}):=\min_{y\in\mathcal{L}} \|y-\mathbf{t}\|_p=\min_{z\in\mathbb{Z}^n}\|Bz-\mathbf{t}\|_p$ 是多少?

画个图的话, 大概下面这样:

最近格矢量问题 (CVP)

SETH 说的则是这么一件事:

存在一个常数 $k$, 使得没有算法能够在 $2^{\alpha n} (\alpha < 1)$ 的时间里解决 $k$-SAT.

从 2-SAT 到 CVP: NP-hardness

然后怎么办呢? 先证明 $\mathsf{CVP}_p$是 $\mathsf{NP}$-hard 的吧 –

我们知道 $\mathsf{MAX\text{-}2\text{-}SAT}$ 是 $\mathsf{NP}$-hard 的, 这东西和 SETH 一样用到了 SAT, 看起来是个不错的出发点. 然后我们需要从 $n$-变量的 2-SAT 的实例出发, 构造一个秩 $n$ 的 $\mathsf{CVP}_p$ 的实例.

考虑一个 $n$ 个变量 $m$ 个子句的 2-SAT 实例, 构造的格和点如下:

• 格$B:=\left(\frac{2\Phi}{2\alpha I_n}\right)$, 这里 $\Phi\in\mathbb{R}^{m\times n}$ 跟 2-SAT 实例有关, 而下面的 identity gadget 则保证我们确实在讨论这问题的精确解. 其中 $\Phi_{i,j}:=\begin{cases} 1, & x_j \text{ appears in clause } i\\ -1, &\neg x_j \text{ appears in clause } i\\ 0, &\text{otherwise} \end{cases}$ .
• 点 $\mathbf{t}:=\begin{pmatrix} t_1\\\vdots\\ t_m \\ - \\ \alpha \\\vdots \\ \alpha \end{pmatrix}$, 每个 $t_i$ 对应一个子句, 且 $t_i := 3-2 \cdot |\{\text{negated literals in clause }i\}|$ .

注意到 $\forall z\in \mathbb{Z}^n$, $|2\alpha I_n z-\mathbf{\alpha}|_p^p=\alphap n $ 当且仅当 $z\in\{0,1\}^n$, 而左式对于 $z$ 的其他取值都至少是 $\alpha^p(n+2)$. 因而只需要考虑 $z\in\{0,1\}^n$ 中的格点, 那么 $\Phi_i z=|\{\text{positive literals satisfied}\}|-|\{\text{negated literals not satisfied}\}|$. 记子句 $i$ 中满足的文字 (literal) 的个数为 l $l_i$, 于是观察到 $2\Phi_i z-t_i=2l_i-3$. 注意到 2-SAT 中每个子句 $i$ 满足的文字个数只可能是 0,1,2, 那么 $|2\Phi_i z-t_i| $ 等于 1 (子句 $i$ 未被满足) 或者 3 (子句 $i$ 被满足) – 这里子句不满足的情形的"等距"性质在规约过程很重要.

因而此时给定点到格的最短距离 $\|\Phi z-t\|_p^p = 3^p m-(3^p-1) |\{\text{satisfied clauses}\}|$, 即 $\mathsf{CVP}_p$ 的解释给定的 2-SAT 实例中最多能满足的子句的个数. 上述规约意味着, 因为 $\mathsf{MAX\text{-}2\text{-}SAT}$ 是 $\mathsf{NP}$-hard, 所以 $\mathsf{CVP}_p$ 也是 $\mathsf{NP}$-hard 的. 更进一步地,

如果 $\mathsf{MAX\text{-}2\text{-}SAT}$ 没有 $2^{o(n)}$ 时间算法的话, 那么 $\mathsf{CVP}_p$ 也没有 $2^{o(n)}$ 时间算法.

值得一提的是, 到目前为止 $\sf SVP$ 的 $\sf NP$-hardness 证明仍然需要使用随机规约, 并没有像上述 $\sf CVP$ 的 $\sf NP$-hardness 这样的简单粗暴的证明.

从 k-SAT 到 CVP: 为什么我们需要指数时间

上面的规约看起来很不错, 唯一的问题是依赖的假设并不标准. 另外上文的规约中的"等距"性质也不能直接推广到 k-SAT, 因为子句中满足的文字个数可能是 0,1,2,…,k, 我们显然不能指望在一维数轴上有三个点和某一个点的距离都一样. 等等…如果换成向量呢? 考虑如下构造.

• $\Phi_{i,j}:=\begin{cases} \mathbf{v}_l, & \text{if } x_j \text{ is the } l^{th} \text{ literal in clause } i\\ -\mathbf{v}_l, & \text{if } \neg x_j \text{ is the } l^{th} \text{ literal in clause } i\\ 0, & \text{otherwise} \end{cases},$
• $t_i := t^* - \sum_{l^{th} \text{literal negated}} v_l .$

那么对于格点 $z\in\{0,1\}^n$, 计算可知 $\Phi_i z-t_i = \sum_{z \text{ satisfies } l^{th} \text{ literal}} v_l - t^*$. 我们想要的是上述"等距"性质的高维版本, 即 $\|\Phi_i z -t_i\|_p$ 是常数, 并且 $\|\Phi_i z-t_i\|_p \leq \|t^*\|_p$. 也就是说, 我们想找的是分离平行多面体 (isolated parallelepiped), 譬如下图:

2-范数的二维的分离平行多面体

找到一组 $V=(\mathbf{v}_1,\cdots,\mathbf{v}_l)\in \mathbb{R}^{m\times k}$ 和 $t^* \in \mathbb{R}^m$ 使得 $\forall y\in\{0,1\}^n \setminus \mathbf{0}, \|Vy-t^*\|_p=1$, 并且 $\|\mathbf{0}-t^*\|_p > 1$. 即除原点 $\mathbf{0}$ (子句被满足) 以外的其他格点到 $t^*$的距离都相等.

这样的点 $t^*$ 是否存在呢? 对于不同的 $\ell_p$-norm, 这样的 $t^*$ 是不一样的. [1] 证明了对于所有奇数 $p$, 这样的 $t^*$ 对于所有 $k$ 存在, 这意味着下述结果:

假设 SETH 成立, 所有奇数 $p$ 范数的 $\mathsf{CVP}_p$ 没有亚指数时间算法!

对于偶数 $p$ 情况则糟糕的多, 只有部分情况下能找到满足条件的 $t^*$, 甚至更尴尬的是这并不包含 $p=2$ 的情况. 而关于 $\mathsf{SVP}_p$ 的 SETH-based 结果中, 对于 $p=2$ 的情形仍然需要更多的假设才能证明 – 这也许是几何风格的问题的有趣之处, 困难总会在出人意料的地方出现.

参考文献