三大不可能定理#

量子信息理论是一个广阔的研究领域，包含两个主要方向：量子计算与量子通信。量子计算理论的成功源于一个正面结果：肖尔算法¹。该算法能够以远高于现有计算机——甚至包括基于经典物理学最强大的可构想计算机——的效率完成整数分解。另一方面，量子通信的成功则源于理想量子密码协议的内在安全性，它依赖于一个负面结果：即无法在不以不可恢复方式扰乱量子信息的情况下读取它。

无干扰则无信息的性质催生了其他不可能定理，这些定理代表了量子信息理论中最著名、最经典的成果。其中必然包括不可克隆定理²，该定理指出复制量子信息是不可能的。这一不可能性显然是无提取信息而不扰动的不可能性的推论。事实上，如果我们能够精确复制系统的状态，将其再现到另一个同类系统上，那么我们就可以重复这一过程，生产出任意多的副本。随后我们就能从副本中提取所有感兴趣的信息，同时保持原始系统完好无损。

这一论证看似简单，却蕴含着一个关于量子信息——乃至更广义上任何可纯化的信息类型——的深刻洞见。假设确实存在一种测量手段，能够绝对精确地确定系统的状态。那么我们可以对系统进行这样的测量，一旦得知其确切状态，原则上就能随意多次重新制备相同的状态。如果某一理论禁止复制状态，那么我们必须得出这样的结论：在该理论中，测量状态同样被禁止！这正是纯化理论——尤其是量子理论——中的情形。³

在量子理论中，确定系统的状态是不可能的。我们只能对系统处于何种状态获得一些信息。这些信息可能很精确，但永远无法确定。这在经典理论中实际上也可能发生。然而，在我们的量子世界中，存在比实际不可能更强的情况。假设我们对状态有一些先验知识，并希望通过测量来检验它。在经典情况下，我们可以证实这样的预期；而在量子情况下，我们只能证伪自己的知识。换言之，即使发生了与先验知识相符的事件，这也永远不足以让我们确认对状态的信念。能够确定的只有否定的答案。

另一个源自“无干扰即无信息提取”这一不可能性的相关否定结果是不可编程定理，⁴该定理指出不可能构建一种量子设备，它接收两个输入态——一个数据态和一个程序态——并根据程序对数据精确执行任何幺正变换。这一否定结果揭示了经典信息论与量子信息论之间的又一差异。现代计算的成功确实不仅依赖于硅技术的惊人进步，还基于冯·诺依曼的“程序即数据”范式，它实现了通用图灵机的理念：通过提供一个编码为数据形式的合适程序，经典计算机可以编程执行任何计算。当该程序与实际数据一起通过通用程序进行处理时，计算机会对输入执行所需的操作。然而，这种简单架构在量子理论中是不可能的。事实上，通用量子计算只能近似实现，且近似程度随程序维度的增加而提高。

最后，我们将讨论一个刻画量子密码学特征的no-go定理：不可比特承诺定理（no-bit-commitment theorem）。该定理在量子信息领域非常流行，甚至被用作重构量子理论尝试中的一个原则。⁵ 比特承诺协议旨在允许一方（Alice）向另一方（Bob）发送一个比特，使得在Alice允许披露之前Bob无法读取该比特，同时Alice在编码后不能改变该比特的值。

比特承诺协议是密码学中一个非常重要的原始要素，而在经典信息论中已知完全安全的协议是不可能的。量子理论中也是如此，但证明需要相当复杂的工具来考虑每一方可能对协议中涉及量子系统施加的所有可能变换序列。对于具有纯化的一般理论，其证明涉及一个非常重要的刻画定理，该定理为策略提供了一种便捷的数学表示，因此因其简洁性和深刻洞见而极具启发性。

现在是时候看看所有这些惊人特征是如何从我们陈述的原理中得出的了。

9.1 不可克隆#

系统A的一组状态 $\{\rho_{i} \}_{i \in \mathrm{X}}$ 的克隆通道是从A到复合系统 $\mathrm{\ A A}^{\prime}$ 的一个通道，其中 $\mathrm{A}^{\prime}$ 与A操作等价，使得

$$ \mathcal{C} | \rho_{i} )_{\mathrm{A}} = | \rho_{i} )_{\mathrm{A}} | \rho_{i} )_{\mathrm{A}^{\prime}} . $$

如果存在这样的克隆通道，我们就说状态 $\{\rho_{i} \}_{i \in \mathrm{X}}$ 是完全可克隆的。注意，如果存在克隆通道，我们可以将其两次应用于未知状态 $\rho_{i} ,$ 从而得到它的三个相同副本，即

$$ ( {\mathcal{C}} \otimes{\mathcal{T}}_{\mathrm{A^{\prime}}} ) {\mathcal{C}} | \rho_{i} ) = | \rho_{i} )_{\mathrm{A}} | \rho_{i} )_{\mathrm{A^{\prime}}} | \rho_{i} )_{\mathrm{A^{\prime \prime}}} , $$

显然，重复这一过程，我们可以产生任意多的副本。

现在我们证明，在具有纯化的理论中，一组生成状态（特别是系统A的纯态集）不能被完美克隆。该证明基于完美可克隆性与完美可区分性的等价性。⁶ 实际上，这一结果在任何允许所有“测量-制备”通道的凸理论中都成立，无需因果性和局域可区分性。

定理9.1（克隆-区分等价性） 在允许所有“测量-制备”通道的凸理论中，确定性状态 $\{\rho_{i} \}_{i \in \mathrm{X}} \subset \mathsf{St}_{1} ( \mathrm{A} )$ 完全可克隆当且仅当它们完全可区分。

证明假设状态 $\{\rho_{i} \}_{i \in \mathrm{X}}$ 可以被完美克隆，并考虑两个状态 $\rho_{j} , \rho_{l} , j \neq l ,$ 之间的一般二元区分策略，对应于一个二元观测检验 $\{a_{j} , a_{l} \}$ 。将最坏情况错误概率定义为

$$ p_{\mathrm{wc}} : = \operatorname*{max} \{p ( l | j ) , p ( j | l ) \} \qquad p ( k | i ) : = ( a_{k} | \rho_{i} )_{\mathrm{A}} , $$

并取最优区分，对应于所有二元检验的最小值

$$ p_{\mathrm{wc}}^{( \mathrm{opt} )} : = \operatorname*{min}_{a_{j} , a_{l}} p_{\mathrm{wc}} , $$

这由最优检验 $\{a_{j}^{\mathrm{( o p t )}} , a_{l}^{\mathrm{( o p t )}} \}$ 实现。现在，如果存在克隆信道，我们可以将其应用于未知态 $\rho_{i}$ 两次，从而得到如式(9.2)所示的三个相同副本。在执行三次最优检验后，我们可以采用多数投票判别策略，对应一个新的二元判别检验 $\{b_{j} , b_{l} \}$，定义如下：

$$ \begin{array}{r} {( b_{j} | _{\mathrm{A}} : = [ ( A_{j j l} | _{\mathrm{AA}^{\prime} \mathrm{A}^{\prime \prime}} + ( A_{j l j} | _{\mathrm{AA}^{\prime} \mathrm{A}^{\prime \prime}} + ( A_{l j j} | _{\mathrm{AA}^{\prime} \mathrm{A}^{\prime \prime}} + ( A_{j l j} | _{\mathrm{AA}^{\prime} \mathrm{A}^{\prime \prime}} ] ( \mathcal{C} \otimes \mathbb{Z}_{\mathrm{A}^{\prime}} ) \mathcal{C} ,} \\ {( b_{l} | _{\mathrm{A}} : = [ ( A_{j l l} | _{\mathrm{AA}^{\prime} \mathrm{A}^{\prime \prime}} + ( A_{l j l} | _{\mathrm{AA}^{\prime} \mathrm{A}^{\prime \prime}} + ( A_{l l j} | _{\mathrm{AA}^{\prime} \mathrm{A}^{\prime \prime}} + ( A_{l l l} | _{\mathrm{AA}^{\prime} \mathrm{A}^{\prime \prime}} ] ( \mathcal{C} \otimes \mathbb{Z}_{\mathrm{A}^{\prime}} ) \mathcal{C} ,} \end{array} $$

其中 $( A_{x y z} | _{\mathrm{A A^{\prime} A^{\prime \prime}}} : = ( a_{x}^{( \mathrm{opt} )} | _{\mathrm{A}} ( a_{y}^{( \mathrm{opt} )} | _{\mathrm{A^{\prime}}} ( a_{z}^{( \mathrm{opt} )} | _{\mathrm{A^{\prime \prime}}}$ 。观测检验 $\{b_{j} , b_{l} \}$ 的错误概率由下式给出：

$$ p^{\prime} ( i | j ) = f ( p^{( \mathrm{opt} )} ( i | j ) ) \qquad f ( x ) : = x^{2} ( 3 - 2 x ) , $$

其中 $p^{( \mathrm{opt} )} ( i | j ) : = ( a_{i}^{( \mathrm{opt} )} | \rho_{j} )_{\mathrm{A}}$ 。由于 $f$ 在区间 $x \in [ 0 , 1 ]$ 上是非递减函数，我们也有 $p_{\mathrm{wc}}^{\prime} = f \left( p_{\mathrm{wc}}^{( \mathrm{opt} )} \right)$ 。然后，由于 $p_{\mathrm{wc}}^{( \mathrm{opt} )}$ 是最小错误概率，根据定义有 $p_{\mathrm{wc}}^{\prime} \geq p_{\mathrm{wc}}^{\mathrm{( o p t )}}$ 。不等式 $f ( x ) \geq x$ 的唯一解是 $x = 0$ 和 $x \in [ 1 / 2 , 1 ]$，并且由于 $p_{\mathrm{wc}}^{( \mathrm{opt} )}$ 必定在区间 $[ 0 , 1 / 2 )$ 内（见问题3.1），我们得到 $p_{\mathrm{wc}}^{\mathrm{( o p t )}} = 0$ 。这意味着来自集合 $\{\rho_{i} \}_{i \in \mathrm{X}}$ 的任意一对态都可以被完美区分。反过来，这又意味着使用 $| \mathrm{X} | - 1$ 次成对测试，我们可以完美区分所有态 $\{\rho_{i} \}_{i \in \mathrm{X}}$ （见练习9.1）。这证明了一个态集合的完美可克隆性蕴含其完美可区分性。如果该理论包含所有可能的"测量并制备"通道，则逆命题显然成立：如果态可以通过观测检验 $\{a_{i} \}_{i \in \mathrm{X}}$ 被完美区分，那么测量并制备通道 $\begin{array}{r} {\mathcal{C} : = \sum_{i \in \mathrm{X}} \vert \rho_{i} )_{\mathrm{A}} \vert \rho_{i} )_{\mathrm{A}^{\prime}} ( a_{i} \vert_{\mathrm{A}}} \end$ 就是一个克隆通道。

由于测量并制备通道可以通过根据观测检验的结果来条件化制备检验的选择而获得，任何因果理论都满足前述定理的假设，从而得出：

推论9.2（因果理论中的克隆-区分等价性）在因果理论中，态 $\{\rho_{i} \}_{i \in \mathrm{X}} \subset \mathsf{St}_{1} ( \mathrm{A} )$ 是完美可克隆的当且仅当它们是完美可区分的。

在具有纯化的因果理论情况下，到目前为止证明的结果蕴含以下不可克隆陈述。

推论9.3（纯态不可克隆）在具有纯化的因果理论中，对于生成态集合的克隆通道不可能存在。特别地，纯态不能被克隆。

这确实是推论9.2与定理9.1和练习10.1结合的立即结论，在练习10.1中我们证明了在具有纯化的因果理论中，无法通过单个观测检验区分所有纯态。

练习9.1 证明如果态集合 $\{\rho_{i} \}_{i \in \mathrm{X}} \subseteq \mathsf{St}_{1} ( \mathrm{A} )$ 使得任意一对满足 $j \neq l$ 的 $\rho_{j} , \rho_{l}$ 是完美可区分的，则集合 $\{\rho_{i}^{\otimes ( | \mathrm{X} | - 1 )} \}_{i \in \mathrm{X}} \subseteq \mathsf{St}_{1} ( \mathsf{A}_{1} \mathsf{A}_{2} \dots \mathsf{A}_{| \mathrm{X} | - 1} )$ 是完美可区分的。

练习9.2 [克隆与信号传递] 证明Nick Herbert犯了一个错误。⁷

9.2 不可编程#

我们介绍的第二个不可行定理是不可编程。该定理指出，与经典情况不同，在量子理论中不存在通用处理器。系统A的通用处理器是一个通道 $\mathcal{C} \in \mathsf{Transf}_{1} ( \mathrm{AP} )$，它可以通过向系统P提供合适的程序态 $\sigma$ 而被指示对系统A执行任意处理。用数学术语来说，对于每个目标通道 $\mathcal{D} \in \mathsf{Transf}_{1} ( \mathrm{A} )$，必须存在一个程序态 $\sigma \in \mathsf{St}_{1} ( \mathsf{P} )$，使得以下等式成立：

$$ {\frac{\textsc{A}} {( {\sigma} ) \textsc{p}}} \biggl [ {\mathcal{C}} \biggr ]_{\textsc{p} [ {e} )}^{\textsc{A}} = {\frac{\textsc{A} \sqrt{{\mathcal{D}}} \textsc{A}} {{\vert{\mathcal{D}} \vert}^{\textsc{A}}}} . $$

根据量子不可编程定理，不可能将涉及有限个输入目标系统的所有算法编码在有限程序系统 P 的状态上。这一结果⁸可以推广到具有纯化和局部可区分性的因果理论中，这类理论中系统拥有无限多个纯态——或者等价地，通过传递性，拥有无限个可逆变换群。

实际上，在具有纯化和局部可区分性的因果理论中，概率编程是可行的：信道 _D 的程序状态可以通过将信道作用于一个忠实态得到，即

$$ \overbrace{\vphantom{\int_{\mathbb{P}} \int_{\mathbb{P}} 2}}^{\mathrm{{\tiny ~ P}_{1}}} = \overbrace{\vphantom{\int_{\mathbb{P}} \int_{\mathbb{P}} 2} \mathrm{d} \underbrace{\vphantom{\int_{\mathbb{P}} \int_{\mathbb{P}}} \mathrm{d}}_{\mathrm{\tiny ~ P}_{2}}}^{\mathrm{{\tiny ~ P}_{1}}} , $$

然后执行概率隐形传态协议。实际上，这一方案提供了一个具有以下结构的概率通用处理器：

$$ \begin{array}{r l} {\frac{\mathrm{A}} {\mathrm{P_{1}}} \Bigg [ \mathcal{C} \Bigg ] \frac{\mathrm{A}} {\mathrm{P_{1}}} =} & {\ \frac{\mathrm{A}^{\top}} {\mathrm{P_{1}}^{\top}} \Bigg [ \frac{B_{x}} {B_{x}} \Bigg ] \Bigg [ \Psi \Bigg ] \frac{- \mathrm{e}^{- \mathrm{e}^{- \mathrm{e}^{- \mathrm{e}^{- \mathrm{e}^{- \mathrm{e}^{- \mathrm{e}^{- \mathrm{e}^{- \mathrm{e}^{- \mathrm{e}^{\mathrm{\pi}}}}}}}}}}} \Bigg [ \mathcal{S} \Bigg ] \frac{\mathrm{A}} {\mathrm{P_{1}}}} {\Bigg [ \mathrm{P_{2}}} ,} \\ {\frac{\mathrm{P_{2}}} {\mathrm{P_{2}}}} \end{array} $$

其中 $\mathsf{P}_{1} \sim \mathsf{P}_{2} \sim \mathbf{A}$，表示交换门 $S | \psi ) | \varphi ) = | \varphi ) | \psi )$，是任意态，$\{B_{x} \}_{x \in \mathrm{X}}$ 是一个观测检验，使得

$$ \begin{array}{r} {\overbrace{\vphantom{\int} \Phi \underbrace{\vphantom{\int} \left( \Phi \frac{\partial \Theta} {\partial \Theta} \right)} \mathrm{d} \mathrm{d} \mathrm{~ ~ \Gamma ~}}^{\mathrm{~ A ~}} = p_{0} \overbrace{\mathrm{~ ~ \Gamma ~} \mathrm{~ ~ \Omega ~}}^{\mathrm{~ A ~}} \overbrace{\vphantom{\int} \mathbb{Z} \biggr ] \mathrm{~ ~ \Gamma ~} \mathrm{~ \}}^{\mathrm{~ A ~}} ,} \end{array} $$

如式(7.15)所示。然而，以下定理告诉我们，上述编程过程通常无法通过任何方法扩展为确定性过程。事实上，该定理证明，对一组可逆信道进行编程需要完全可区分的程序状态。由此可以清楚地看到，在系统可逆变换群为无限的理论中，完美编程是不可能的。

定理9.4（程序状态的完美可区分性） 设 $\{\mathcal{U}_{i} \}_{i \in \mathrm{X}}$ 是 A 上的一组可逆信道，$\{\eta_{i} \}_{i \in \mathrm{X}}$ 是 P 的一组纯态。如果存在信道 $\mathcal{R} \in \text{Transf(AP)}$ 使得

$$ \frac{\textsc{{A}}} {( \eta_{i} ) \textsc{{P}}} \overline{{{\mathscr C} \underbrace{\textsc{{P}}}}} = \frac{\textsc{{A}} \sqrt{\mathscr{U}_{i}} \textsc{{A}}} {\textsc{{C}}} $$

则态 $\{\eta_{i} \}_{i \in \mathrm{X}}$ 是完全可区分的。

证明取的一个酉膨胀，其中纯态 $\varphi_{0} \in{\mathsf{St}}_{1} ( {\mathsf{C}} )$ 和可逆信道 $\mathcal{U} \in \mathsf{Transf} ( \mathrm{APC} )$。定义纯态 $\varphi_{i} : = \eta_{i} \otimes \varphi_{0}$，我们有

$$ \frac{\textsc{A}} {( \varphi_{i} ) \textsc{p c}} \overline{{\mathcal{U}}} \overline{{\Bigg | \underbrace{\mathrm{~ {\scriptstyle{\cal ~ P C} ~}}_{\mathrm{\tiny ~ P C}}}_{\mathrm{\tiny ~ P C}}}} = \frac{\textsc{A} \sqrt{\mathcal{U}_{i}} \biggr ) \textsc{A}} {\textsc{i}} . $$

由于式(9.8)的左边是可逆变换 $\mathcal{U}_{i}$ 的一个膨胀，根据可逆膨胀的唯一性（参见习题7.4），必存在一个纯态 $\psi_{i} \in{\sf S t}_{1} ( \mathrm{PC} )$ 使得

$$ \frac{\textsc{A}} {( \varphi_{i} ) \textsc{p c}} \boxed{\mathcal{U}} \frac{\textsc{A}} {\textsc{p c}} = \frac{\textsc{A} \boxed{\mathcal{U}_{i}} \textsc{A}} {( \psi_{i} ) \textsc{\textsc{p c}}} . $$

通过对式 (9.10) 两边左侧应用 $\boldsymbol{\mathcal{U}}_{i}^{- 1}$，右侧应用 $\displaystyle{\mathcal{U}}^{- 1}$，可得

$$ \begin{array}{r l r} {\frac{\mathrm{~ {\cal ~ A} ~} \sqrt{{\mathcal{U}}_{i}^{- 1}} \Big | \mathrm{~ {\cal ~ A} ~}} {\mathrm{~ {\cal ~ P} ~} \mathrm{~ {\cal ~ C} ~}} =} & {{}} & {\frac{\mathrm{~ {\cal ~ A} ~}} {( {\mathcal{Y}}_{i} ) \mathrm{~ {\cal ~ P} ~} \mathrm{~ {\cal ~ C} ~}} \Bigg [ {\mathcal{U}}^{- 1} \Bigg ] \frac{\mathrm{~ {\cal ~ A} ~}} {\mathrm{~ {\cal ~ P} ~} \mathrm{~ {\cal ~ C} ~}} .} \end{array} $$

组合式 (9.10) 和 (9.11)，我们得到

(9.12)

这意味着通过迭代应用和 $\displaystyle{\mathcal{U}}^{- 1}$，我们可以获得无限多的 $\mathcal{U}_{i}$ 和 $\boldsymbol{\mathcal{U}}_{i}^{- 1}$ 副本。现在，如果 $\mathcal{U}_{i}$ 和 $\mathcal{U}_{j}$ 不同，那么使用 N 个副本区分它们的错误概率会随着 N 趋于无穷而降至零（这可以通过重复 N 次最优测试并使用多数投票来实现，如定理 9.1 的证明所示）。由于对变换 $\{( \mathcal{U}_{i} \otimes \mathcal{U}_{i}^{- 1} )^{\otimes N} \}$ 进行编程并区分它们，是区分程序状态 $\varphi_{i}$ 的一种特定策略，因此后者必须是可完美区分的。最后，由于状态 $\varphi_{i} = \eta_{i} \otimes \varphi_{0}$ 是可完美区分的，程序状态 $\{\eta_{i} \}$ 也必须是可完美区分的。

推论 9.5（不可编程定理）在一个具有纯化和局部可区分性的因果理论中，对于具有无穷多纯态的系统，精确编程是被禁止的。

练习 9.3 证明使用混合程序状态 $\{\rho_{i} \}$ 不能帮助减少程序系统 P 中所需的可完美区分状态的数量。

9.3 比特承诺的不可行性#

比特承诺是一种重要的原始密码学任务，在通信和计算理论中有各种应用。该任务涉及两方：Alice 和 Bob。Alice 应该存储一位比特，供 Bob 在 Alice 披露后稍后访问。如果一个比特承诺协议具有绑定属性，则 Alice 不能在向 Bob 披露之前更改存储比特的值；而如果具有隐藏属性，则 Bob 在 Alice 披露之前无法访问该比特。如果在给定理论中存在一个既绑定又隐藏的协议，则比特承诺在该理论中是可行的。

在经典情况下，存在比特承诺协议，其绑定和隐藏属性依赖于实际中无法高效解决某些给定问题，例如计算离散对数或反转给定类中的函数。在量子情况下，不可能存在一个既隐藏又绑定的比特承诺协议（参见章末注释以了解简要历史回顾）。

我们现在将证明，在因果性、局部可区分性和纯化的假设下，这个不可能性证明可以在操作概率理论的框架中进行。(^9) 该证明将针对一个精确绑定和隐藏的协议的不可能性。正如量子密码学文献中所做的那样，将分析扩展到任意绑定和隐藏的协议，只是一个技术性问题，在此不再深入探讨。

9.3.1 量子策略：带记忆的信道#

一个两方多轮处理任务的量子协议，是双方执行的一系列操作，他们在每一轮交换一个系统，同时为自己保留一些系统用于后续轮次。这意味着完整的协议可以描绘如下：

$$ \begin{array}{r l r} & {} & {\frac{\mathrm{F}_{1}} {\mathrm{A}_{1}} \left[ \begin{array}{l} {\mathcal{C}_{1}} \\ {\widetilde{\mathbf{B}_{1}}} \\ {\widetilde{\mathbf{G}_{1}}} \end{array} \right] \frac{\mathrm{F}_{2}} {\mathrm{G}_{1}} \left[ \begin{array}{l} {\mathcal{C}_{2}} \\ {\mathcal{C}_{2}} \\ {\widetilde{\mathbf{B}_{2}}} \end{array} \right] \frac{\mathrm{F}_{3}} {\mathrm{G}_{2}} \left[ \begin{array}{l} {\mathrm{F}_{3}} \\ {\mathrm{B}_{2}} \\ {\widetilde{\mathcal{D}_{2}}} \\ {\widetilde{\mathbf{G}_{3}}} \end{array} \right] \frac{\mathrm{A}_{3}} {\mathrm{G}_{3}} \ldots \frac{\mathrm{G}_{N}} {\mathrm{G}_{N - 1}} \left[ \begin{array}{l} {\mathrm{F}_{N}} \\ {\mathrm{B}_{N - 1}} \\ {\mathcal{D}_{N - 1}} \\ {\mathrm{G}_{N}} \end{array} \right] \frac{\mathrm{G}_{N}} {\mathrm{G}_{N}} .} \end{array} $$

如果我们现在将上述电路分成两部分，上半部分表示Alice的操作序列，下半部分表示Bob的操作序列，我们就得到两个图，分别表示Alice和Bob的策略。例如，Alice的策略由下图表示：

$$ \frac{\mathrm{~ {~ \cal ~ A ~} ~}_{1}} {\mathrm{~ {~ \cal ~ F} ~}_{1}} \left[ \begin{array}{l} {{\mathcal{C}}_{1}} \\ {{\mathcal{C}}_{2}} \end{array} \right] \frac{\mathrm{~ {~ \cal ~ B} ~}_{1}} {\mathrm{~ {~ \cal ~ F} ~}_{2}} \left[ \begin{array}{l} {{\mathcal{A}}_{2}} \\ {{\mathcal{C}}_{2}} \end{array} \right] \frac{\mathrm{~ {~ \cal ~ B} ~}_{2}} {\mathrm{~ {~ \cal ~ F} ~}_{3}} \ldots \frac{\mathrm{~ {~ \cal ~ A} ~}_{N}} {\mathrm{~ {~ \cal ~ F} ~}_{N}} \left[ \begin{array}{l} {{\mathcal{C}}_{N}} \\ {{\mathcal{C}}_{N}} \end{array} \right] \frac{\mathrm{~ {~ \cal ~ B} ~}_{N}} {\mathrm{~ {~ \cal ~ F} ~}_{N + 1}} $$$$ \begin{array}{r l} & {\frac{\mathrm{F}_{1}} {\mathrm{A}_{1}} \Bigg [ \mathcal{C}_{1} \Bigg ] \frac{\mathrm{B}_{1}} {\mathrm{F}_{2}}} \\ {=} & {\frac{\mathrm{A}_{3}} {\mathrm{A}_{3}} \frac{\Bigg [ \mathcal{C}_{2} \Bigg ] \frac{\mathrm{B}_{2}} {\mathrm{F}_{3}}} {\Bigg [ \mathcal{C}_{2} \Bigg ] \frac{\mathrm{F}_{3}} {\mathrm{F}_{4}}} \ldots \frac{\mathrm{B}_{1}} {\mathrm{A}_{N}}} \\ & {\quad \vdots} \\ & {\quad \quad \quad \quad \quad \quad \quad \mathrm{A}_{N - 1} \underbrace{\mathrm{\Lambda}_{\dots} \Bigg [ \mathcal{C}_{N} \Bigg ] \frac{\mathrm{B}_{N}} {\mathrm{F}_{N + 1}}}_{\mathrm{\Lambda}_{N + 1}}} \end{array} . $$

上述方案也适用于涉及经典信息交换的协议。事实上，经典信息可以通过完全可区分的态来建模，而经典信道可以通过"测量-制备"信道来建模，其中观测检验是可区分的，制备的态也是完全可区分的。某些系统只能被制备成完全可区分的态这一事实，通常被称为协议的"通信接口"。¹⁰

图表(9.14)的结构是含记忆信道的一般结构，因为它利用了记忆系统——图表(9.14)中标为$\mathrm{F}_{i}$（其中$i \geq 2$）的系统——这些系统存储给定步骤i中$\mathcal{C}_{i}$输出的信息，以供后续步骤使用。¹¹

在一个具有纯化和局域可区分性的因果理论中，如图表(9.14)所示的含记忆信道$\mathcal{C}^{( N )}$总可以通过膨胀信道$\mathcal{C}_{1} , \ldots , \mathcal{C}_{N}$来扩展到可逆信道，将输出膨胀系统$\mathrm{D}_{j + 1}$包含在记忆系统$\mathrm{F}_{j + 1}^{\prime} : = \mathrm{F}_{j + 1} \mathrm{D}_{j + 1}$中，并在最终步骤$N$后全部丢弃，如下所示：

(9.15)

由于图表(9.15)中提供的实现是${\mathcal{C}}^{( n )}$的纯且可逆膨胀，根据练习7.4中纯且可逆膨胀的唯一性，该实现本质上是唯一的。这一观察对于下一节提供的"无比特承诺"定理至关重要。

9.3.2 无比特承诺定理#

含记忆信道的序列可用于描述密码协议或多方博弈中某一方的连续行动。¹²在此场景中，记忆系统是某一方持有的私有系统，而其他输入-输出系统则是与其他方通信中交换的系统。在此背景下，因果信道实现的唯一性直接蕴含了诸如完全安全的比特承诺等任务的不可能性。¹³一般情况下的证明如下所示。

定理9.6（无比特承诺）在具有纯化的理论中，如果一个N轮协议具有完全隐藏性，则存在完美欺骗。

证明首先，对于不涉及经典信息交换的协议证明该论断。设 $\mathcal{A}_{0} , \mathcal{A}_{1} \ \in \ \mathsf{Transf} ( \mathsf{A}_{1} \ldots \to \mathsf{A}_{N} , \mathsf{B}_{1} \ldots \mathsf{B}_{N - 1} \mathsf{B}_{N} \mathsf{F}_{N + 1} )$ 为两个带有记忆的 N 方信道（这里两个信道的最后一个输出系统均为二分系统 $\mathrm{B}_{N} \mathrm{F}_{N + 1} )$ ，分别对应 Alice 为编码比特值 $b = 0 , 1$ 所采取的行动。系统 $\mathrm{F}_{N + 1}$ 是在协议的披露阶段（称为打开）由 Alice 发送给 Bob 的系统，用以揭示比特值。现在，取 $\mathcal{A}_{0}$ 和 $\mathcal{A}_{1}$ 的两个纯化且可逆的膨胀，分别记为 $( \mathrm{C} , \mathrm{D} , H_{0} , \mathcal{V}_{0} )$ 和 $( \mathrm{C} , \mathrm{D} , H_{1} , \mathcal{V}_{1} )$ ，如图9.15所示，其中 $\mathbf{C} : = \mathbf{C}_{1} \mathbf{C}_{2} \ldots \mathbf{C}_{N} , \mathbf{D} : = \mathbf{D}_{N}$ ，且 $H_{i} : = \eta_{1}^{( i )} \otimes \eta_{2}^{( i )} \cdots \otimes \eta_{N}^{( i )} \stackrel{} {\in}$ $\mathsf{P u r S t_{1}} ( \mathbf{C} )$ ，而 $\nu_{i}$ 对应于图9.15实现中的可逆记忆信道，由 $1 \le j \le N$ 的可逆信道 $\mathcal{U}_{j}^{( i )}$ 串联得到。如果协议是完全隐藏的，则打开阶段前的约化信道 $( e | _{\mathrm{F}_{N + 1}} \mathcal{A}_{i}$ 必须不可区分，即 $( e | _{\mathrm{F}_{N + 1}} \mathcal{A}_{0} = ( e | _{\mathrm{F}_{N + 1}} \mathcal{A}_{1} = : \mathcal{C}$ 由于 $\mathcal{V}_{0}$ 和 $\mathcal{V}_{1}$ 也是该信道的两个膨胀，根据练习7.4中可逆膨胀的唯一性，存在一个信道 $\mathcal{R} \in \mathsf{RevTransf} ( \mathrm{F}_{N} \mathrm{C}_{\mathrm{out}} )$ ，使得 $\mathcal{V}_{1} = \mathcal{R} \mathcal{V}_{0}$ 。Alice 对其私有系统应用信道 $\mathcal{R}$ ，可以在打开前从 $\mathcal{V}_{0}$ 切换到 $\mathcal{V}_{1}$ ，反之，应用 $\mathcal{R}^{- 1}$ 可以从 $\mathcal{V}_{1}$ 切换到 $\mathcal{V}_{0}$ 。随后 Alice 丢弃辅助系统 D，分别得到第一种情况下的信道 $\mathcal{A}_{1}$ 和第二种情况下的 $\mathcal{A}_{0}$ 。欺骗是完美的，因为 Alice 可以在承诺阶段一直执行策略 $\mathcal{V}_{0}$ ，并在打开前决定比特值而不被 Bob 检测到。

上述推理可以扩展到涉及经典信息交换的 N 轮协议。实际上，如果协议的通信接口涉及非平凡的经典信息交换，我们可以按如下步骤进行。首先取可逆膨胀 $\mathcal{V}_{0} , \mathcal{V}_{1}$ 以及信道，使得 $\mathcal{V}_{1} = \mathcal{R} \mathcal{V}_{0}$ 。为了符合协议的通信接口，需将所有携带经典信息的系统上的 $\mathcal{V}_{0}$ 和 $\mathcal{V}_{1}$ 与经典信道复合，从而得到两个不再可逆的信道 ${\mathcal{E}}_{0}$ 和 $\mathcal{E}_{1}$ ，如下图表示：

由于 $\mathcal{V}_{1} = \mathcal{R} \mathcal{V}_{0}$ ，信道 $\mathcal{E}_{0} , \mathcal{E}_{1}$ 仍然满足 $\mathcal{E}_{1} = \mathcal{R} \mathcal{E}_{0}$ 。丢弃辅助系统 $\mathrm{C_{o u t}}$ ，并在系统 $\mathrm{F}_{N}$ 上应用一个测量-制备信道 $\mathcal{F}$ （如果通信接口要求如此），Alice 便可得到信道 ${\mathcal{E}}_{0}$ 或 $\mathcal{E}_{1}$ 。再次，存在一个可逆信道使得 $\mathcal{E}_{1} = \mathcal{R} \mathcal{E}_{0}$ ，允许 Alice 在打开前决定比特值，而不被检测到。■

9.4 小结#

在本章中，我们证明了量子信息论中的三个重要不可行定理：不可克隆定理、不可编程定理和无比特承诺定理。这些定理在 $0 \mathsf{P} \mathsf{I} \mathsf{s}$ 框架内证明，仅使用了我们的原理，从而凸显了这些原理的概念性力量。

9.4 小结#

非因果理论中的不可克隆定理#

如第9.1节所述，在具有纯化的理论中，不可克隆定理成立的充分条件是因果性。然而，这一结果只是定理9.1的推论，该定理的假设较弱，仅需凸性和自由测量-制备测试。存在一类相关的非因果理论满足这些假设，即二阶理论。从每个因果理论 $\Theta$ （其中状态-变换同构成立）出发，可以通过将变换集合 Transf(A → B) 视为二阶系统 $^{6} \mathrm{A} \mathrm{B}$ 的状态集合 $\mathsf{S t^{\prime}} ( \mathrm{A} \to \mathrm{B} )$ 来构造其二阶理论 $\Theta^{\prime}$ ，其中确定性状态对应于信道。第5.7节引入的理论提供了一个例子，其中状态是量子操作。可以证明，在这种情况下对状态 $\mathcal{C} \in \mathsf{St}^{\prime} ( \mathsf{A {} B} )$ 执行观察测试，可以在底层因果理论 $\Theta$ 中解释为：将变换 $\mathcal{C} \in \mathsf{T r a n s f ( A \Delta B )}$ 应用于输入状态 $\sigma \in{\sf S t}_{1} ( \mathrm{AC} )$ ，然后对输出状态 $( \mathcal{C} \otimes \mathcal{T}_{\mathrm{C}} ) | \sigma )_{\mathrm{AC}}$ 执行观察测试 $\{b_{i} \}_{i \in \mathrm{X}}$ （参见例如 Chiribella 等人，2015）。当然，由于理论 $\Theta$ 是因果的，我们可以使用条件化并执行依赖于结果 i 的信道 $\mathcal{C}_{i}$ 。这就在非因果理论 $\Theta^{\prime}$ 中实现了任意测量-制备信道。

不可编程定理与通用量子计算#

不可编程定理表面上与通用量子图灵机的存在性相冲突，后者定义上即是一个可编程量子处理器。然而，Bernstein 和 Vazirani（1993）证明通用量子图灵机是存在的，并且在量子电路模型中也能够实现通用量子计算，Yao（1993）证明该模型等价于量子图灵机。这些结果表面冲突的原因在于整个量子计算基于近似编程的概念：换句话说，通用量子图灵机不需要精确近似任何量子信道，而是允许任意小的误差，其资源成本随误差大小的倒数多项式增长。对于可编程 POVM 的情况，D'Ariano 和 Perinotti（2005）推导出了最优通用量子处理器。量子计算理论的通用性定理证明此类通用处理器存在，从而降低了不可编程定理的实际相关性，同时保留了其基础重要性。

无条件安全量子比特承诺#

与通用处理器的情况类似，在具有纯化和局域可区分性的因果理论中，完美比特承诺协议不存在，并不意味着如果我们允许作弊成功的小概率，就无法找到有效的协议。事实上，在量子情形下证明无比特承诺的主要技术困难源于放松了协议必须完美安全的要求。允许任意安全性的一系列日益安全的协议被称为无条件安全比特承诺。在量子情形下，可以证明无条件安全比特承诺是不可能的，这才是实际上的量子不可行定理。然而，将不可行性证明扩展到具有纯化的因果理论中的无条件安全协议，并不仅仅是技术细节问题。为此所需的一个缺失要素是：要有一个定理确保，给定两个在操作范数距离上接近的状态，总能找到一对具有相同距离的同一状态的纯化。这一在量子情形下成立的定理由 Uhlmann（1977）证明。

历史上，对量子协议的分析始于20世纪90年代，Mayers（1997）以及Lo和Chau（1997）的结果表明，既具有隐蔽性又具有约束性的量子协议是不可能的。H. P. Yuen（参见Yuen, 2012及其中的参考文献）对这些安全性证明提出了批评。一个完整的不可行性证明需要对量子场景中所有可执行的协议进行彻底分类，而所有可能性的完整说明最终在D’Ariano等人（2007）的证明中得到了考虑。Chiribella等人（2013b）利用量子梳理论（Chiribella等人，2008c, 2009）——该理论特别适用于描述多轮量子通信协议——提供了另一个证明，其分析过程显著更短。

选做习题与练习题解答#

练习9.1#

假设图(9.9)中对应于酉变换 $\mathcal{U}_{i}$ 的程序态 $\rho_{i}$ 是如下混合态 $\begin{array}{r} {\rho_{i} = \dot{\sum_{j}} p_{j}^{( i )} \psi_{j}^{( i )}} \end$ 。由于可逆变换是原子的，这意味着每个纯态 $\psi_{j}^{( i )}$ 必须作为 $\mathcal{U}_{i}$ 的程序来工作。但上述定理表明，无论我们如何选择，纯态 $\{\varphi_{j_{i}}^{( i )} \}_{i \in \mathrm{X}}$ 必须是完美可区分的。