给定自然数$ n $，$ \left[n\right] $表示集合$ \{\mathrm{1,2},\cdots ,n\} $。矩阵$ \boldsymbol{A}=\left[\boldsymbol{A}\left(x,y\right)\right] $表示其$ x $行$ y $列的元素为$ \boldsymbol{A}(x,y) $。对于矩阵$ \boldsymbol{A} $，$ {\boldsymbol{A}}^{\mathrm{T}} $表示其转置，$ {\boldsymbol{A}}^{\dagger } $表示其共轭转置。若矩阵$ \boldsymbol{A} $满足性质$ {\boldsymbol{A}}^{\dagger }=\boldsymbol{A} $，则称$ \boldsymbol{A} $为厄米特(Hermitian)矩阵。若一个厄米特阵$ \boldsymbol{A} $的所有特征值都是非负的，则称$ \boldsymbol{A} $为半正定(positive semidefinite, PSD)矩阵。

对任意非负矩阵$ \boldsymbol{P}\in {\mathbb{R}}_{+}^{n\times m} $, $ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left(\boldsymbol{P}\right) $为$ \boldsymbol{P} $的非负秩(nonnegative rank)，其定义为使得$ \boldsymbol{P} $能分解为$ r $个秩(rank)为1的非负矩阵的最小$ r $。此外，$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right) $为$ \boldsymbol{P} $的半正定秩(PSD-rank)。若$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right) $为$ r $，则存在半正定矩阵$ {\boldsymbol{C}}_{x},{\boldsymbol{D}}_{y}\in {\mathbb{C}}^{r\times r} $满足$ \boldsymbol{P}(x,y)=\mathrm{t}\mathrm{r}({\boldsymbol{C}}_{x}{\boldsymbol{D}}_{y}) $，且$ r $是满足这一半正定分解的最小值^[4-5]。对于$ \boldsymbol{P} $的$ k $区块半正定秩 ($ k $-block PSD-rank)，它是半正定秩的扩展，记作$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}^{\left(k\right)}\left(\boldsymbol{P}\right) $。若$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}^{\left(k\right)}\left(\boldsymbol{P}\right) $为$ r $，则存在半正定矩阵$ {\boldsymbol{C}}_{x}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}({\boldsymbol{C}}_{x}^{1},{\boldsymbol{C}}_{x}^{2}\cdots ,{\boldsymbol{C}}_{x}^{r}), {\boldsymbol{D}}_{y}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}({\boldsymbol{D}}_{y}^{1}, {\boldsymbol{D}}_{y,}^{2}\cdots , {\boldsymbol{D}}_{y}^{r})\in {\mathbb{C}}^{kr\times kr} $满足：

式中，$ {\boldsymbol{C}}_{x}^{l},\;{\boldsymbol{D}}_{y}^{l}\in {\mathbb{C}}^{k\times k} $。要求$ r $是满足这一$ k $区块半正定分解的最小值^[6-9]。

作用在希尔伯特空间$ \mathcal{H} $上的量子态$ \rho $是迹(trace)为1的半正定算子。若该算子秩为1，则其为纯态，可写作$ \rho =\left|\psi \right\rangle\langle\psi | $，其中$ \left|\psi \right\rangle $是模为1的向量。对于量子态$ \rho \in {\mathcal{H}}_{A} $，$ \left|\psi \right\rangle\in {\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B} $，若有$ \mathrm{t}{\mathrm{r}}_{{\mathcal{H}}_{B}} \left(|\psi \right\rangle\left\langle\psi |\right)=\rho $，则称$ \left|\psi \right\rangle $是$ \rho $的一个纯化(purification)。其中，$ \mathrm{t}{\mathrm{r}}_{{\mathcal{H}}_{B}} $代表在$ {\mathcal{H}}_{B} $空间上的部分迹(partial trace)。对任意的量子态而言，总可以对其进行纯化操作。

对于任意的两体纯态$ {\left|\psi \right\rangle}_{AB} $，总存在$ {\mathcal{H}}_{A},\;{\mathcal{H}}_{B} $上的标准正交基$ \left\{\right|{i}_{A}\rangle\},\;\{|{i}_{B}'\rangle\} $使得$ {\left|\psi \right\rangle}_{AB}=\displaystyle\sum _{i}\sqrt{{p}_{i}}\left|{i}_{A}\right\rangle\otimes |{i}_{B}'\rangle $。其中$ {p}_{i} $为非负实数，满足$ \displaystyle\sum _{i}{p}_{i}=1 $。该分解为施密特分解(Schmidt decomposition)，$ \sqrt{{p}_{i}} $为施密特系数(Schmidt coefficient)，非零施密特系数的数目定义为施密特秩 (Schmidt rank)，记作$ \mathrm{S}-\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\left(\right|\psi \rangle) $。更详细的量子信息基础介绍可参考文献[10]。

在经典场景中，Alice和Bob通过仅共享关联种子$ {\boldsymbol{P}}'=({X}',Y') $或仅进行经典通讯，并在各自拥有的子系统上进行本地操作，使得二人最终输出的联合概率分布$ (X,Y) $与目标经典关联$ \boldsymbol{P} $一致。文献[1]将这一任务所需的最小代价，即所需的最小$ \mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}\left(\boldsymbol{P}'\right) $或所交换的最少比特数，与$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left(\boldsymbol{P}\right) $建立了联系，并给出了$ {R}\left(\boldsymbol{P}\right)=\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left(\boldsymbol{P}\right)} \right\rceil $这一精确刻画。下文给出简要的证明思路。

根据$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left(\boldsymbol{P}\right) $的定义，可将经典关联$ \boldsymbol{P} $分解为$ {\boldsymbol{P}}_{x,y}=\displaystyle\sum _{i=1}^{r}{q}_{i}{\boldsymbol{a}}_{i}\left(x\right){\boldsymbol{b}}_{i}\left(y\right) $，其中$ \left\{{q}_{i}\right\},{\boldsymbol{a}}_{i},{\boldsymbol{b}}_{i} $均为概率分布，且$ r=\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left(\boldsymbol{P}\right) $。则Alice和Bob可通过从共享的$ \left\{{q}_{i}\right\} $中采样$ i $，然后各自从$ {\boldsymbol{a}}_{i},{\boldsymbol{b}}_{i} $中采样$ x,y $，并将其输出。由于其输出$ \left(x,y\right) $的概率与$ {\boldsymbol{P}}_{x,y} $一致，则说明$ {R}\left(\boldsymbol{P}\right)\le \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left(\boldsymbol{P}\right)} \right\rceil $。

对于$ {R}\left(\boldsymbol{P}\right) $的下界，考虑二者进行经典通讯的场景，即尝试证明$ \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left(\boldsymbol{P}\right)} \right\rceil \le \mathrm{R}\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}\left(\boldsymbol{P}\right) $。假设经典关联$ {\boldsymbol{P}} $是通过$ r $轮的通讯协议$ \boldsymbol{M}=\left({M}_{1},{M}_{2},\cdots ,{M}_{r}\right) $生成的，其中随机变量$ {M}_{i} $是第$ i $轮传输的信息。Alice和Bob各自拥有私有随机变量$ {r}_{A} $和$ {r}_{B} $，不失一般性，假设由Alice开始传输信息$ {M}_{1} $。则有：

将$ {\mathrm{P}\mathrm{r}}_{{r}_{A},{r}_{B}}\left[M=m\right] $展开，即为：

这里最后的概率是基于$ {r}_{A} $还是基于$ {r}_{B} $取决于最后一轮由谁通讯。此外，由于给定信息$ m $后，Alice和Bob的输出是相互独立的，条件概率为：

将式(2)和式(3)代入式(1)，整理可得：

给定$ m $，第一个括号中的乘积项只与$ x $有关，第二个括号中的乘积项只与$ y $有关，因此每一个求和项对应一个秩为1的矩阵。此外，由于矩阵中的元素对应概率的乘积，因此该矩阵为非负矩阵。换句话说，可以将$ \boldsymbol{P} $分解为$ {2}^{c} $项秩为1的非负矩阵之和，$ c $为传输的总比特数。由此得证，$\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left(\boldsymbol{P}\right)} \right\rceil \le \mathrm{R}\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{m}\left(\boldsymbol{P}\right)$。

在量子场景中，Alice和Bob可通过仅共享量子纠缠或仅进行量子通讯，即传输量子比特，并在各自拥有的系统上进行本地操作来生成经典关联$ \boldsymbol{P} $。值得注意的是，在量子场景下，如果能制备形如$ \rho =\displaystyle\sum _{x,y}\boldsymbol{P}(x,y)|x\rangle\langle x|\otimes |y\rangle\langle y| $的量子态，则Alice和Bob可通过在各自的子系统上进行计算基下的测量得到$ \boldsymbol{P} $。一个值得关注的结果是文献[2]将$ \boldsymbol{P} $的关联复杂度$ Q\left(\boldsymbol{P}\right) $与$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right) $关联起来，并给出了与经典场景类似的精确刻画，即$ Q\left(\boldsymbol{P}\right)=\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right)} \right\rceil $。

该结果的证明基于如下引理^[2]：对量子态$ \rho \in {\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B} $，$ Q\left(\rho \right)=\underset{{\mathcal{H}}_{{A}_{1}},{\mathcal{H}}_{{B}_{1}}}{\mathrm{min}}\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{S}-\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\left(|\psi \rangle\right)} \right\rceil $，其中$ \left|\psi \right\rangle\in {\mathcal{H}}_{{A}_{1}}\otimes {\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B}\otimes {\mathcal{H}}_{{B}_{1}} $是$ \rho $的纯化。基于这一引理，下文给出$ Q\left(\boldsymbol{P}\right)=\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right)} \right\rceil $的简要证明。

首先，尝试给出$ Q\left(\boldsymbol{P}\right) $的上界。令$ r=\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right) $，$ \rho =\displaystyle\sum _{x,y}\boldsymbol{P}(x,y)|x\rangle\langle x|\otimes |y\rangle\langle y| $。若存在$ \rho $的纯化$ |\psi \rangle $满足$ S-\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\left(\left|\psi \right\rangle\right)\le r $，结合如上引理，则有$ Q\left(\boldsymbol{P}\right)\le \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right)} \right\rceil $。考虑半正定矩阵$ {\boldsymbol{C}}_{x},{\boldsymbol{D}}_{y}\in {\mathbb{C}}^{r\times r} $使得对任意$ x\in X,y\in Y $，$ \boldsymbol{P}(x,y)=\mathrm{t}\mathrm{r}({\boldsymbol{C}}_{x}{\boldsymbol{D}}_{y}) $都成立。令$ |{v}_{x}^{i}\rangle $为$ \sqrt{{\boldsymbol{C}}_{x}^{\mathrm{T}}} $的第$ i $列向量，$ |{w}_{y}^{i}\rangle $为$ \sqrt{{\boldsymbol{D}}_{y}} $的第$ i $列向量。定义$ \left|\psi \right\rangle\in {\mathcal{H}}_{A}\otimes {\mathcal{H}}_{A}\otimes {\mathcal{H}}_{{A}_{1}}\otimes {\mathcal{H}}_{B}\otimes {\mathcal{H}}_{B}\otimes {\mathcal{H}}_{{B}_{1}} $为如下形式：

显而易见，$ {S}-\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\left(\left|\psi \right\rangle\right)\le r $，并可验证$ \left|\psi \right\rangle $是$ \rho $的一个纯化。因此，Alice和Bob可以在计算基下测量各自的第一部分系统，并抛弃后面两部分的系统，最终生成$ \boldsymbol{P} $。

此外，对于$ {Q}\left(\boldsymbol{P}\right) $的下界，上面的引理意味着：存在$ \rho $的纯化$ |\psi \rangle $满足$ {S}-\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}\left(\left|\psi \right\rangle\right)=r $且$ \mathrm{Q}\left(\boldsymbol{P}\right)=r $。因此，只要证明$ r\ge \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right) $，即可完成论证。令：

可对任意$ x\in X $，定义$ r\times r $的半正定矩阵$ {\boldsymbol{C}}_{x} $，其$ i $行$ j $列的元素$ {\boldsymbol{C}}_{x}\left(i,j\right)=\langle{v}_{x}^{i}|{v}_{x}^{j}\rangle $；定义$ r\times r $的半正定矩阵$ {\boldsymbol{D}}_{y} $，其$ i $行$ j $列的元素$ {\boldsymbol{D}}_{y}\left(i,j\right)=\langle{w}_{y}^{j}|{w}_{y}^{i}\rangle $。可验证$ \left|\psi \right\rangle $在$ {\mathcal{H}}_{A}\otimes {\mathcal{H}}_{B} $上的约化密度矩阵：

因此，$ {\boldsymbol{C}}_{x} $和$ {\boldsymbol{D}}_{y} $是$ \boldsymbol{P} $的一个半正定分解，有$ r\ge \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right) $。由此得证。

由于量子可模拟经典行为，有$ {Q}\left(\boldsymbol{P}\right)\le {R}\left(\boldsymbol{P}\right) $。此外，Alice和Bob可直接共享经典关联$ \boldsymbol{P} $，从而平凡地生成$ \boldsymbol{P} $。因此，对于$ \boldsymbol{P} $的关联复杂度有如下这一简单关系：

那么一个自然的问题就是，$ {Q}\left(\boldsymbol{P}\right) $与$ {R}\left(\boldsymbol{P}\right) $之间的差距有多大？根据前文介绍的结果，这一问题等价于刻画非负矩阵$ \boldsymbol{P} $的$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right) $和$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left(\boldsymbol{P}\right) $之间的差距。以下展示两个极具代表性的例子。

一个是欧式距离矩阵(Euclidean distance matrix, EDM)：给定$ n $个互不相同的实数$ {c}_{1},{c}_{2},\cdots ,{c}_{n} $，其对应的EDM为$ n\times n $的对称非负矩阵$ {\boldsymbol{Q}} $，该矩阵$ i $行$ j $列的元素为$ \boldsymbol{Q}(i,j)={({c}_{i}-{c}_{j})}^{2} $。有研究结果证明，存在欧氏距离矩阵$ {\boldsymbol{Q}}_{1} $满足$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left({\boldsymbol{Q}}_{1}\right)=2 $，且$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left({\boldsymbol{Q}}_{1}\right)\ge 2\sqrt{n}-2 $^[11]。换言之，若要生成经典关联$ {\boldsymbol{P}}_{1}={\boldsymbol{Q}}_{1}/{||{\boldsymbol{Q}}_{1}||}_{1} $，在量子场景下，Alice和Bob只需要传输1量子比特；而若在经典场景下，Alice和Bob需要传输的比特数为$ O\left({\mathrm{log}}_{2}n\right) $量级。随着$ n $的增大，生成关联$ \boldsymbol{P} $所需的量子比特和经典比特数之间的差距可以达到任意大。

此外，考虑一个$ {2}^{n}\times {2}^{n} $的非负矩阵$ {\boldsymbol{M}} $，其$ i $行$ j $列的元素为$ \boldsymbol{M}(i,j)={(1-{i}^{{\rm{T}}}j)}^{2} $。这里$ i $和$ j $是长度为$ n $的比特串，$ {i}^{\mathrm{T}}j $是$ i $和$ j $模2的内积。对于该矩阵而言，有$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{M}\right)=O\left(n\right) $，且$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left({\boldsymbol{Q}}_{2}\right)={2}^{{\varOmega }\left(n\right)} $^[4]。即，若Alice和Bob想要生成经典关联$ {\boldsymbol{P}}_{2}= \boldsymbol{M}/{||\boldsymbol{M}||}_{1} $，在量子场景下，二人所需传输的量子比特数为$ O\left({\mathrm{log}}_{2}n\right) $量级；而在经典场景下，二人所需传输的经典比特数为$ {\varOmega }\left(n\right) $量级。在这一任务中，量子和经典之间的差距甚至达到了指数级别。因此，关联复杂度提供了区分量子和经典资源能力的一个视角。

在纯经典、量子的场景对比中，量子展示了极大的优势。但从目前的实验水平看来，距离实现大规模的量子计算这一目标，仍有相当长的路要走^[12-13]。对于近期可实现的量子设备，其能操作的量子系统规模有限，通常为几十个量子比特。因此，对于需要更多量子比特才能完成的任务而言，一个亟待解决的问题就是：如何在可操作的量子资源有限的情况下，既能充分利用现有的量子资源，又能顺利完成任务？

出于这一需求，文献[3]研究了量子、经典混合场景下的经典关联生成问题。定义量子能力 (quantum capability) 为可完全操控的量子比特数的一半。考虑如下场景：Alice和Bob想要生成经典关联$ \boldsymbol{P} $，且二人具有的量子能力为$ s $，但$ s < \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{P}\right)} \right\rceil $，也即二人不能通过纯量子协议直接生成经典关联$ \boldsymbol{P} $，必须引入额外的经典计算资源才有可能完成任务。在这种情况下，一个有趣的问题是，在充分利用现有量子资源的前提下，他们该如何完成这一任务？同时，他们需要额外引入的经典资源最少是多少？

在量子、经典混合场景中，主要考虑先进行经典操作，后根据经典结果给定量子态的经典−量子混合协议；以及先给定固定的量子态(与经典信息无关)，而后才进行经典操作的量子−经典混合协议。

在经典−量子混合协议中，Alice和Bob可以先从概率分布$ \left\{{p}_{i}\right\} $中采样$ i $，后根据采样结果$ i $制备量子态$ {\rho }_{i} $，最后基于量子态$ {\rho }_{i} $生成目标经典关联$ \boldsymbol{P} $。假设$ \boldsymbol{P} $可分解为$ \boldsymbol{P}=\displaystyle\sum _{i\in I}{p}_{i}{\boldsymbol{P}}_{i} $，其中$ \left\{{p}_{i}\right\} $是$ i\in I $的概率分布，$ {\boldsymbol{P}}_{i} $是一个经典关联，并满足$ \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left({P}_{i}\right)} \right\rceil \le s $。那么，Alice和Bob就可以从$ \left\{{p}_{i}\right\} $中采样$ i $，随后制备$ {\boldsymbol{P}}_{i} $。因为$ \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left({\boldsymbol{P}}_{i}\right)} \right\rceil \le s $，制备$ {\boldsymbol{P}}_{i} $是在量子能力范围之内的。这样，Alice和Bob输出$ X $和$ Y $的联合概率分布就与$ \boldsymbol{P} $的分布一致，也即完成了目标经典关联$ \boldsymbol{P} $的生成。结合这一发现，文献[3]将量子能力为$ s $时所需交换的经典比特数$ c $与$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}^{\left({2}^{s}\right)}\left(\boldsymbol{P}\right) $建立联系，并给出了$ c=\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}^{\left({2}^{s}\right)}\left(\boldsymbol{P}\right)} \right\rceil $这一结论。下面给出这一结果的简要证明。

首先证明Alice和Bob所需交换的经典比特数的下界。假设二人所需的最小量子比特数为$ c $，则$ \boldsymbol{P} $可分解为$ \boldsymbol{P}(x,y)=\displaystyle\sum _{i=1}^{{2}^{c}}{p}_{i}{\boldsymbol{P}}_{i}(x,y) $，其中$ \left\{{p}_{i}\right\} $是$ i\in \left[{2}^{c}\right] $上的概率分布，且有$ \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left({\boldsymbol{P}}_{i}\right)} \right\rceil \le s $。令$ {\boldsymbol{P}}_{i} $对应的半正定分解为$ {\boldsymbol{P}}_{i}\left(x,y\right)=\mathrm{t}\mathrm{r}({\boldsymbol{C}}_{x}^{i}{\boldsymbol{D}}_{y}^{i}) $，其中$ {\boldsymbol{C}}_{x}^{i},{\boldsymbol{D}}_{y}^{i}\in {\mathbb{C}}^{{2}^{s}\times {2}^{s}} $为半正定矩阵。定义半正定矩阵${\boldsymbol{C}}_{x}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}({p}_{1}{\boldsymbol{C}}_{x}^{1},{p}_{1}{\boldsymbol{C}}_{x}^{2},\cdots ,{p}_{{2}^{c}}{\boldsymbol{C}}_{x}^{{2}^{c}})$，${\boldsymbol{D}}_{y}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}({\boldsymbol{D}}_{y}^{1},{\boldsymbol{D}}_{y}^{2},\cdots , {\boldsymbol{D}}_{y}^{{2}^{c}})$。则简单验证可得，$\boldsymbol{P}\left(x,y\right)=\mathrm{t}\mathrm{r}({\boldsymbol{C}}_{x}{\boldsymbol{D}}_{y})$。因此，有$ \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}^{\left({2}^{s}\right)}\left(\boldsymbol{P}\right)} \right\rceil \le c $。

此外，令$ r=\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}^{\left({2}^{s}\right)}\left(\boldsymbol{P}\right) $。则有半正定矩阵$ {\boldsymbol{C}}_{x}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}({\boldsymbol{C}}_{x}^{1},{\boldsymbol{C}}_{x}^{2},\cdots ,{\boldsymbol{C}}_{x}^{r}) $，$ {\boldsymbol{D}}_{y}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}({\boldsymbol{D}}_{y}^{1},{\boldsymbol{D}}_{y}^{2},\cdots ,{\boldsymbol{D}}_{y}^{r}) $满足$\boldsymbol{P}\left(x,y\right)=\mathrm{t}\mathrm{r}({\boldsymbol{C}}_{x}{\boldsymbol{D}}_{y})$。其中，对所有的$ i\in \left[r\right] $，半正定矩阵$ {\boldsymbol{C}}_{x}^{i},{\boldsymbol{D}}_{y}^{i}\in {\mathbb{C}}^{{2}^{s}\times {2}^{s}} $。定义${\boldsymbol{Q}}_{i}\left(x,y\right)=\mathrm{t}\mathrm{r}({\boldsymbol{C}}_{x}^{i}{\boldsymbol{D}}_{y}^{i})$，经典关联$ {\boldsymbol{P}}_{i}{=\boldsymbol{Q}}_{i}/{||{\boldsymbol{Q}}_{i}||}_{1} $。当$ {p}_{i}={||{\boldsymbol{Q}}_{i}||}_{1} $时，根据$ {2}^{s} $区块半正定秩的定义，有$ {p}_{i} > 0 $。这意味着可将$ \boldsymbol{P} $分解为$ \boldsymbol{P}=\displaystyle\sum _{i=1}^{r}{p}_{i}{\boldsymbol{P}}_{i} $，并对所有的$ i\in \left[r\right] $有$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left({\boldsymbol{P}}_{i}\right)\le {2}^{s} $。由此，Alice和Bob可通过交换$ \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}r} \right\rceil $个经典比特来生成经典关联$ \boldsymbol{P} $，即有$ c\le \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}^{\left({2}^{s}\right)}\left(\boldsymbol{P}\right)} \right\rceil $。由此得证，$ c=\left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}^{\left({2}^{s}\right)}\left(\boldsymbol{P}\right)} \right\rceil $。

根据这一等价刻画，可以比较量子资源和经典资源之间的差别。在3.2节定义的欧氏距离矩阵$ {\boldsymbol{Q}}_{1} $对应的经典关联$ {\boldsymbol{P}}_{1} $，有$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left({\boldsymbol{P}}_{1}\right)=2 $，$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{+}\left({\boldsymbol{P}}_{1}\right)\ge 2\sqrt{n}-2 $。这里定义$ {\boldsymbol{P}}_{2}={\boldsymbol{P}}_{1}\otimes {\boldsymbol{P}}_{1} $，结合半正定秩的性质：$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{A}\otimes \boldsymbol{B}\right)\le \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{A}\right) \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left(\boldsymbol{B}\right) $^[14]，简单可得$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left({\boldsymbol{P}}_{2}\right)=4 $。因此，若通过执行纯量子协议来生成经典关联$ {\boldsymbol{P}}_{2} $，Alice和Bob需要传输的量子比特数为2。当量子能力$ s=1 $时，由于所需的量子系统超过了目前可操控的量子比特数，考虑用经典−量子混合协议来生成$ {\boldsymbol{P}}_{2} $。对于这一经典关联，有研究结果表明$ \mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}^{\left(2\right)}\left({\boldsymbol{P}}_{2}\right)\ge {\mathrm{log}}_{2}n $^[3]。即，缺少1个量子比特的代价需要用$ {\varOmega }\left({\mathrm{log}}_{2}{\mathrm{log}}_{2}n\right) $规模的经典比特来弥补。因此，在经典−量子混合场景中，同样可以看到量子资源相对经典资源的优势。

在经典−量子混合协议中，Alice和Bob拥有在看到经典采样$ i $后再对应选择共享量子态$ {\rho }_{i} $的自由度，即他们可以随意要求不同的初始共享量子态$ {\rho }_{i} $。但在某些时候，这一自由度仍是不易实现的。因此，这里考虑一个更为严格的场景，即Alice和Bob只能在协议一开始获得一个固定的量子态，该量子态与经典信息无关，而后二人才能进行经典操作，或在该量子态上进行本地操作以达成目的。在这一限制之下，前文提出的经典−量子混合协议就自然失效了。同样限制Alice和Bob具有的量子能力为$ s $。由于这里是先有的量子态，而后才介入经典操作，故考虑量子−经典混合协议来处理这一经典关联生成问题。

为了解决该问题，文献[3]将共享的量子态设定为纯态。对于任意的关联，若其能被$ {\mathbb{C}}^{d}\otimes {\mathbb{C}}^{d} $上的混态生成，那么一定存在$ {\mathbb{C}}^{d}\otimes {\mathbb{C}}^{d} $上的纯态同样可以生成这一关联^[15]。因此，共享量子态为纯态这一假定依然发挥了量子能力范围内该有的作用。

此外，文献[16]曾用优超 (majorization) 这一概念刻画了将一个量子纯态通过本地操作和经典通讯 (local operation and classical communication, LOCC) 来转化成另一个量子纯态的充分必要条件。假设$ |\psi \rangle $和$ |\phi \rangle $是两个$ d\times d $的两体量子纯态，$ {\lambda }_{\psi } $和$ {\lambda }_{\phi } $是其对应的施密特系数的平方组成的向量。那么，$ |\psi \rangle $可以通过LOCC的方式被转化成$ |\phi \rangle $，当且仅当$ |\phi \rangle $优超$ |\psi \rangle $^[17]。由于任意$ {2}^{n}\times {2}^{n} $的量子纯态都优超$ n $对Einstein-Podolsky-Rosen (EPR) 态组成的复合系统$\left|n-{\rm{EPR}}\right\rangle={(1/\sqrt{2}\left(|00\right\rangle+|11\rangle\left)\right)}^{\otimes n}$，所以$\left|n-{\rm{EPR}}\right\rangle$可以通过LOCC的方式制备任意$ {2}^{n}\times {2}^{n} $的量子纯态。

结合以上两个事实，Alice和Bob可以首先共享$ s $对EPR态，这里的$ s $为受限的量子能力。然后，与经典−量子混合协议类似地，考虑$ \boldsymbol{P}= \displaystyle\sum _{i\in I}{p}_{i}{\boldsymbol{P}}_{i} $这一分解,其中$ \left\{{p}_{i}\right\} $是$ i\in I $的概率分布，$ {\boldsymbol{P}}_{i} $是一个经典关联，并满足$ \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}\left({\boldsymbol{P}}_{i}\right)} \right\rceil \le s $。这样，Alice和Bob就可以从概率分布$ \left\{{p}_{i}\right\} $中采样$ i $，随后用LOCC的方式将$ s $对EPR态转化成$ {\rho }_{i} $，并依据$ {\rho }_{i} $来制备$ {\boldsymbol{P}}_{i} $。这样，考虑Alice和Bob输出随机变量$ X $和$ Y $的整体行为，其概率分布与经典关联$ \boldsymbol{P} $一致，也即完成了量子−经典混合协议下的经典关联$ \boldsymbol{P} $的生成。

在这一过程中引入的经典通讯只存在于将$ s $对EPR态转化成$ {\rho }_{i} $这一部分，根据文献[16]的结果，该步骤所需的经典比特数至多为$ {2}^{s}-1 $。因此，对于量子−经典混合协议下的经典关联$ \boldsymbol{P} $的生成问题而言，给定量子能力$ s $，其所需要传输的经典比特数至多为$ \left\lceil {{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\mathrm{r}\mathrm{a}\mathrm{n}{\mathrm{k}}_{\mathrm{p}\mathrm{s}\mathrm{d}}^{\left({2}^{s}\right)}\left(\boldsymbol{P}\right)} \right\rceil +{2}^{s}-1 $。

随着量子计算和量子信息的兴起，越来越多的研究工作聚焦于对比量子资源和经典资源在计算能力上的差距^[17-20]。本文从经典关联生成问题入手，首先介绍了完成该任务的经典协议和量子协议的完整数学刻画。通过将经典协议所需的经典资源与非负秩建立联系，并将量子协议所需的量子资源与半正定秩对标，把该问题转化为对比非负矩阵的非负秩与半正定秩的问题。在此基础之上，本文介绍了两个区分量子和经典资源计算能力的例子，其中，事先共享量子纠缠甚至能比事先共享随机性有指数级的优势。

此外，针对近期量子设备规模，本文还介绍了量子、经典混合场景下的经典关联生成问题。根据在协议中提供初始共享量子态的时间点，分别讨论了经典−量子混合协议和量子−经典混合协议。与纯经典协议和纯量子协议类似，在量子、经典混合场景下，其所需的经典比特数与$ k $区块半正定秩相关。在这一量子、经典混合场景中，仍然可以看到量子相对经典的优势。因此，经典关联生成问题是对比量子资源和经典资源之间计算能力的一个极佳视角。

总体而言，经典关联生成问题中蕴含着丰富的数学结构。并且由于其与半正定秩的性质密切相关，而半正定秩的研究尚处于初期阶段，因此该问题仍有极大的探讨空间，希望后续能有更丰富的研究结果诞生。