量子通信复杂度

量子消息不是一串等待逐位读取的隐藏经典数，而是一个可在后续操作中发生干涉的状态。协议优势来自对目标函数所需区分的输入结构进行编码和联合测量，并不意味着接收者能恢复描述该状态的全部复振幅。

预共享纠缠提供相关性，却单独不能传信。它像在通信开始前铺好的相干资源：只有与之后真正传输的寄存器结合，才可能改变编码密度或协调方式。因此 qubit、classical bit、EPR pair、轮数和错误率必须分账。

Superdense coding 的资源账本 ​

双方预共享 EPR pair

Alice 要发送两个经典 bit $(a,b)$。固定联合顺序为 Alice 的半边在前、Bob 的半边在后；她先做 $Z^a$、后做 $X^b$，总矩阵为 $X^b{Z}^a$，再把自己的 qubit 发送给 Bob。按Bell 测量公理库Bell 测量Bell measurement · Bell-basis measurement · Bell 基测量用 CNOT 与 Hadamard 将四个 Bell 向量解码为计算基标签，并区分相同测量效应下不同的测后状态。的标签约定，有

对每个固定经典输入，右侧符号是整个联合态的整体相位，不影响解码。Bob 收到寄存器后，以收到的半边控制原有半边做 CNOT，再对收到的半边做 H，最后分别测量，确定得到 $a,b$。这说明联合测量确实在收到量子消息之后才能本地执行。

通信是一 qubit，预共享资源是一对纠缠 qubits，输出为两 classical bits。若把 EPR pair 的预分发也算入当前会话，总代价就不同；若没有预共享纠缠，一 qubit 不能稳定携带任意两个经典 bit。

这个例子说明纠缠辅助下 classical information per transmitted qubit 可达到 $2$，却不表示“一 qubit 等于两 bit”在所有模型中成立。协议能力取决于预共享态和允许测量。

量子传态公理库量子传态Quantum teleportation · 量子隐形传态以预共享 Bell 对和两位经典消息传输未知 qubit 状态，逐分支证明校正，并计算消息到达前的最大混合态。给出另一方向的资源转换：预共享一对 Bell qubits 后，Alice 用两位经典消息让 Bob 恢复一个未知 qubit 的完整状态，连同它与外部参考的关联。执行阶段消耗 1 ebit 和 2 classical bits；这是一套协议的用量，资源预分发仍须另行记账。传态与超密编码分别完成量子态传输和经典标签传输，不能将两个任务的成本混为一个单位换算。

Quantum fingerprinting ​

取 $n\ge 2$。在SMP 拓扑公理库同时消息传递模型Simultaneous message passing · SMP modelAlice 与 Bob 不相互通信，各自只向无输入 referee 发送一条消息，由 referee 合并两份摘要输出。中，用量子寄存器替换经典消息，Alice、Bob 各只向无输入 referee 发送一次，彼此不通信，也不共享随机币或纠缠。为计算Equality公理库Equality 通信问题Equality communication problem · EQ communication problem比较双方 n-bit 私有串是否完全相同，展示确定性完整传输与公共随机指纹之间的指数差异。，可把经典串 $x$ 映到组合块码公理库信道码Channel code把消息映为信道输入码字并从带噪输出恢复消息的编码—译码对。的码字 $E(x)\in \{0,1{\}}^m$，并制备指纹态

为使不同输入的绝对重叠有常数间隔，要求相对距离同时远离 $0$ 与 $1$：对某个常数 $0<\delta <1/2$，不同码字满足 $\delta \le d_H(E(x),E(y))/m\le 1-\delta$。因为 $⟨{\varphi }_x|{\varphi }_y⟩=1-2d_H(E(x),E(y))/m$，于是其绝对值至多 $1-2\delta$。只有距离下界还不够：互为补串的码字会给出仅差整体负号的同一纯态。

这种双侧距离条件可由常率、常数相对距离的二进码得到：取 $C:\{0,1{\}}^n\to \{0,1{\}}^{\ell }$，其中 $\ell =O(n)$，不同码字距离至少为 ${\delta }_0\ell$，$0<{\delta }_0<1$ 为常数。令 $E(x)=C(x)0^{\ell }$，则 $m=2\ell$，相对距离落在 $[{\delta }_0/2,1/2]$，可取 $\delta ={\delta }_0/2$。于是指纹只需 $\lceil {\log }_{2}m\rceil =O(\log n)$ 个 qubit。Alice、Bob 各向 referee 发送若干份这样的指纹。Referee 将Hadamard 测试公理库Hadamard 测试Hadamard test逐振幅推导受控酉期望值的实部和虚部读出，固定S逆门的相位约定，并给出样本数、输入制备和黑盒控制访问的完整成本。用于联合输入 $|{\varphi }_x⟩\otimes |{\varphi }_y⟩$ 与已知的 SWAP 门；受控 SWAP 是他本地可实施的电路。因为

测试输出1的概率为 $(1-|⟨{\varphi }_x|{\varphi }_y⟩{|}^2)/2$。相等时它为零，不等时至少为 $g=2\delta (1-\delta )>0$。做 $k$ 次独立试验公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。，只在全部输出0时接受，则误收概率至多 $(1-g{)}^k\le e^{-gk}$。对 $0<\epsilon <1$，取 $k=\lceil g^{-1}\ln \left(1/\epsilon \right)\rceil$ 足够，总通信为 $2k\lceil {\log }_{2}m\rceil$ qubit；固定码距时这是 $O(\log n[1+\log \left(1/\epsilon \right)])$。

相等输入给同一纯态，不等输入只保证重叠受限；重复份数控制错误。量子态不能被 referee 任意复制，所以每次独立 swap test 需要协议实际提供相应副本，不能用 no-cloning 偷免通信。

信息读取边界 ​

Holevo 界公理库Holevo 界与可访问信息Holevo bound · Holevo theoremHolevo 界限制从量子系综的任意测量中读出的经典标签互信息；两种明确测量展示如何从 Born 概率算到信息量，并区分可访问信息与最小判别错误。说明，若接收者仅依据收到的 $q$ qubits 测量经典编码标签，可提取的经典互信息公理库互信息Mutual information用联合分布相对独立边缘乘积的 KL 散度量化统计依赖。至多 $q$ bits。已有侧信息须另外纳入条件或完整接收系统。它不禁止量子协议以较少 qubits 计算某个函数，因为函数输出可能远小于完整输入。

纠缠辅助时，superdense coding 给出发送一 qubit 读出两 bit 的具体协议：接收者测量的是完整的两个 qubit 系统，四个 Bell 态两两正交，符合维数为四的 Holevo 界。这一例子的达成计算本身不证明一般纠缠辅助上界。引用通信下界时，必须匹配是否纠缠、输入先验和接收方已有 side information。

测量还会破坏状态。经典 transcript 可以被双方复制、反复检查，量子消息通常不能；把经典矩形叶或 public transcript 证明原样搬入量子协议会失去结构。

与经典随机通信的边界 ​

任何经典 bit 可编码为计算基 qubit，所以量子模型能模拟经典随机协议公理库随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。，在相同固定消息日程下逐位编码会保留成本和错误；一般变长或变发言者协议要先说明补齐与控制开销。公共币也必须在量子模型中提供同样的可见性，不能凭编码免费获得。反向用测量把每个 qubit 变成一 bit 一般会丢失相位与纠缠。

成本也不能按 Hilbert space 振幅数计。一组 $q$ qubits 的状态需要 $2^q$ 个复振幅描述，但发送者并未发送这些经典描述；通信仍是 $q$ qubits。

最后，量子通信复杂度是信息论模型，不包含容错门、量子信道噪声或制备时间。工程实现需另加错误校正和物理资源，不能把免费本地量子操作当作硬件承诺。

Superdense coding 与 quantum fingerprinting 展示了两种不同的节省：前者用预共享纠缠提高经典信息编码密度，后者只为 Equality 保留足以比较的低维几何特征。前一种结果依赖 EPR 资源，后一种并不等价于压缩后可恢复原输入；解释量子优势时应指出究竟节省了哪项任务资源。

经典随机下界工具不能未经修改地套到量子 transcript 上，因为测量、相位和不可复制性破坏了普通协议叶的矩形图像。可用下界通常转向 Holevo 信息、量子信息复杂度、迹距离公理库迹距离Trace distance · Quantum trace distance迹距离是两个密度算子之差的迹范数的一半，恰好刻画单份量子态在最优测量下的可区分程度。或专门的矩阵范数，并始终匹配是否允许纠缠与接收方 side information。

自测：在 superdense coding 中，Alice 施加四种编码操作之后、发送 qubit 之前，Bob 的约化态分别是什么？答案均为 $I/2$。能从四个联合 Bell 态中恢复两 bit 的步骤，需要 Bob 真正收到另半个系统并执行联合测量。