量子通信复杂度 | Codeboy's Blog

形式陈述

协议状态与成本

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

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

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

\Pr[\Pi(x,y)=f(x,y)]\ge1-\varepsilon

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

无纠缠与纠缠辅助模型

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

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

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

直觉

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

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

例子与边界

Superdense coding 的资源账本

双方预共享 EPR pair

|\Phi^+\rangle =\frac{|00\rangle+|11\rangle}{\sqrt2}.

Alice 要发送两个经典 bit $(a,b)$ 。她在自己的 qubit 上施加 $X^bZ^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$ ，并制备指纹态

|\phi_x\rangle =\frac1{\sqrt m}\sum_{i=1}^m(-1)^{E(x)_i}|i\rangle.

若码保证不同码字有常数相对距离，则 $x\ne y$ 时 $|\langle\phi_x|\phi_y\rangle|$ 与 $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 从任意经典输入编码中可提取的经典互信息至多 $q$ bits。它不禁止量子协议以较少 qubits 计算某个函数，因为函数输出可能远小于完整输入。

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

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

与经典随机通信的边界

任何经典 bit 可编码为计算基 qubit，所以量子模型能模拟经典随机协议，但模拟是否保留 public coins、轮数和错误需要说明。反向用测量把每个 qubit 变成一 bit 一般会丢失相位与纠缠。

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

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

推论与应用

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

经典随机下界工具不能未经修改地套到量子 transcript 上，因为测量、相位和不可复制性破坏了普通协议叶的矩形图像。可用下界通常转向 Holevo 信息、量子信息复杂度、迹距离或专门的矩阵范数，并始终匹配是否允许纠缠与接收方 side information。

参考资料

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.

形式陈述 ​

协议状态与成本 ​

无纠缠与纠缠辅助模型 ​

Superdense coding 的资源账本 ​

Quantum fingerprinting ​

信息读取边界 ​

与经典随机通信的边界 ​