量子通信复杂度

协议状态与成本 ​

Alice 持有经典输入 $x$，Bob 持有经典输入 $y$。双方各有私有量子工作空间，协议每轮对本地寄存器施加依赖自身输入的量子操作，再把一个消息寄存器传给对方。最终一方测量输出寄存器，得到经典答案。

交换一个 $d$ 维量子系统的成本记为 ${\log }_{2}d$ qubit。若协议同时发送经典消息，应分别报告 qubits 与 classical bits，或明确采用怎样的统一换算。局部量子计算通常免费，轮数、错误和是否共享纠缠仍是独立参数。

给定输入 $(x,y)$ 后，输出随机性来自测量和可能的经典随机币。Bounded-error 复杂度要求

$$\text{Pr}[\mathrm{\Pi }(x,y)=f(x,y)]\ge 1-\epsilon$$

对每个固定合法输入成立。不能只对输入分布平均，也不能把量子态的振幅直接当作输出概率；概率要在最终测量后由 Born rule 得到。

无纠缠与纠缠辅助模型 ​

无预共享纠缠的模型让双方初始工作空间是乘积态，通信是建立量子相关性的唯一渠道。Entanglement-assisted 模型允许在看到输入前共享固定态 $|\psi {⟩}_{AB}$；该态不计通信，却必须与输入独立。

共享纠缠本身不能传递信息：Alice 对自己的半边做任何局部操作，Bob 在没有消息时看到的 reduced state 不变。它可以与后续 qubit 结合，提高编码或协调能力，因而需要在复杂度符号中显式标记。

量子公共随机性、共享 EPR pairs 和经典 public coins 也不是同一资源。测量纠缠对可生成相关随机 bit，但选择测量基和保留相干性可能提供不同协议能力。

Superdense coding 的资源账本 ​

双方预共享 EPR pair

$$|{\mathrm{\Phi }}^{+}⟩=\frac{|00⟩+|11⟩}{\sqrt{2}}.$$

Alice 要发送两个经典 bit $(a,b)$。她在自己的 qubit 上施加 $X^b{Z}^a$，把四种输入编码成四个正交 Bell states，再把这一 qubit 发送给 Bob。Bob 对收到的 qubit 与自己持有的半边做 Bell measurement，精确恢复 $(a,b)$。

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

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

Quantum fingerprinting ​

在 SMP Equality 中，可把经典串 $x$ 映到误差校正码字 $E(x)\in \{0,1{\}}^m$，并制备指纹态

$$|{\varphi }_x⟩=\frac{1}{\sqrt{m}}\sum _{i=1}^m(-1{)}^{E(x{)}_i}|i⟩.$$

若码保证不同码字有常数相对距离，则 $x\ne y$ 时 $|⟨{\varphi }_x|{\varphi }_y⟩|$ 与 $1$ 保持常数 gap。Alice、Bob 各向 referee 发送若干份 $O(\log m)=O(\log n)$-qubit 指纹；referee 用 swap test 估计重叠并判断 Equality。

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

信息读取边界 ​

Holevo bound 说明，没有预共享纠缠时，接收 $q$ qubits 从任意经典输入编码中可提取的 classical mutual information 至多 $q$ bits。它不禁止量子协议以较少 qubits 计算某个函数，因为函数输出可能远小于完整输入。

纠缠辅助时，superdense coding 显示可提取上限需要相应调整到至多 $2q$ classical bits。引用 Holevo 下界时必须匹配是否纠缠、输入先验和接收方已有 side information。

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

与经典随机通信的边界 ​

任何经典 bit 可编码为计算基 qubit，所以量子模型能模拟经典随机协议公理库随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。，但模拟是否保留 public coins、轮数和错误需要说明。反向用测量把每个 qubit 变成一 bit 一般会丢失相位与纠缠。

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

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

参考资料

• Andrew Chi-Chih Yao, “Quantum Circuit Complexity,” FOCS, 1993, pp. 352–361.
• Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf, “Quantum Fingerprinting,” Physical Review Letters 87, 2001, 167902.
• Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010, Chapters 2 and 12.