经典、量子及其混合场景下的经典关联生成协议

林小蝶，魏朝晖

(1. 清华大学交叉信息研究院 北京 海淀区 100084；
2. 清华大学丘成桐数学科学中心 北京 海淀区 100084；
3. 北京雁栖湖应用数学研究院 北京 海淀区 100084)

在信息处理任务中，分隔各地的不同参与方常常需要协同完成计算任务。在这一过程中，多方之间共享计算资源往往是不可或缺的，如随机变量或量子纠缠，其中前者也被称作经典关联(classical correlation)。因此，如何高效地制备这些共享计算资源是一个重要问题。本文将介绍近期在经典关联生成这一任务上的一系列进展。经典关联生成问题主要研究的是：为了生成一个目标共享经典关联，最少需要涉及多少数量的初始共享随机性或者量子纠缠？本文主要讨论两方参与的情形，并将介绍经典场景、量子场景以及量子、经典混合场景下的经典关联生成协议[1-3]。

考虑这样一个具体的场景：分隔两地的Alice和Bob 二人想要从目标经典关联P=(X,Y)中进行采样，即二人各自输出随机变量X和Y，使得 (X,Y)的联合概率分布与P完全一致。那么，对于一个任意的经典关联P，如何刻画生成其所需要的最小代价？

关联复杂度(correlation complexity)和通讯复杂度(communication complexity)是与此相关的两个量。对于两体的共享经典随机变量P′=(X′,Y′)，可将其大小 size(P′)定义为(「log2X⏋+「log2Y⏋)/2，其中 X 和 Y 分别是随机变量X′和Y′采样集合的大小；
对于两体的量子态σ∈HA⊗HB，其大小size(σ)则定义为 ( 「log2DA⏋+「log2DB⏋)/2，其中DA和DB分别对应希尔伯特空间(Hilbert space) HA和 HB的维度。对于经典关联生成问题，Alice 和Bob 可以共享一个关联种子P′=(X′,Y′)，并且每个人都可以在自己的系统上进行本地操作(local operation, LO)以最终生成目标经典关联P。

称P的随机关联复杂度(randomized correlation complexity)为 最 小 的 size(P′)，记 作R(P) 。

若Alice 和Bob 共享的是量子态 σ，并且他们通过在自己的系统上进行本地量子操作，最终通过量子测量成功生成目标经典关联P。那么称P的量子关联复杂度(quantum correlation complexity)为最小的s ize(σ)， 记作Q(P)。

除了共享关联种子以外，Alice 和Bob 还可以利用通讯的方式来生成目标经典关联P。在协议的一开始，Alice 和Bob 并不共享任何资源，而是在协议的执行过程中通过进行相互间的通讯，最终协同生成目标经典关联P。若Alice 和Bob 进行的是经典通讯，则称P的随机通讯复杂度(randomized communication complexity)为二者交换的最少比特数，记作 RComm(P)；
若Alice 和Bob 进行的是量子通讯，则称P的量子通讯复杂度(quantum communication complexity)为二者交换的最少量子比特数，记作 QComm(P)。有研究结果证明，对于任意的量子态ρ，其量子关联复杂度和量子通讯复杂度总是相等的，也即Q(P)=QComm(P)且R(P)=RComm(P)[1]。因此，下文将直接使用R和Q的记号，不对关联复杂度和通讯复杂度进行严格的区分。

作用在希尔伯特空间 H 上的量子态 ρ是迹(trace)为1 的半正定算子。若该算子秩为1，则其为纯态，可写作 ρ=|ψ〉〈ψ|， 其中 |ψ〉是模为1 的向量。对于量子态 ρ ∈HA， |ψ〉∈HA⊗HB， 若有trHB(|ψ〉〈ψ|)=ρ， 则称 |ψ〉是 ρ的一个纯化(purification)。其中， trHB代表在 HB空间上的部分迹(partial trace)。对任意的量子态而言，总可以对其进行纯化操作。

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

给定m， 第一个括号中的乘积项只与x有关，第二个括号中的乘积项只与y有关，因此每一个求和项对应一个秩为1 的矩阵。此外，由于矩阵中的元素对应概率的乘积，因此该矩阵为非负矩阵。换句话说，可以将P分 解为 2c项秩为1 的非负矩阵之和，c为传输的总比特数。

由此得证，「log2rank+(P)⏋≤RComm(P)。

3.1 量子关联复杂度Q(P)

显而易见，S−rank(|ψ〉)≤r， 并可验证 |ψ〉 是ρ 的一个纯化。因此，Alice 和Bob 可以在计算基下测量各自的第一部分系统，并抛弃后面两部分的系统，最终生成P。

此外，对于Q(P)的下界，上面的引理意味着：存在 ρ的 纯化 |ψ〉满 足S−rank(|ψ〉)=r且 Q(P)=r。因此，只要证明r≥rankpsd(P)，即可完成论证。令：

3.2 随机、量子关联复杂度 R(P) 与Q (P)的对比

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

那么一个自然的问题就是，Q(P)与R(P)之间的差距有多大？根据前文介绍的结果，这一问题等价于 刻 画 非负 矩阵P的 rankpsd(P)和 rank+(P)之 间 的 差距。以下展示两个极具代表性的例子。

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

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

4.1 经典−量子混合协议

4.2 量子−经典混合协议

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

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

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

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

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

猜你喜欢量子态复杂度通讯《茶叶通讯》简介茶叶通讯(2022年2期)2022-11-15《茶叶通讯》简介茶叶通讯(2022年3期)2022-11-11通讯报道机械研究与应用(2022年4期)2022-09-15量子直接传态*物理学报(2021年19期)2021-11-01一类两体非X-型量子态的量子失谐湖北大学学报(自然科学版)(2020年1期)2020-01-07一种低复杂度的惯性/GNSS矢量深组合方法中国惯性技术学报(2019年6期)2019-03-04求图上广探树的时间复杂度中央民族大学学报（自然科学版）(2017年2期)2017-06-11通讯简史中国科技信息(2016年19期)2016-10-25某雷达导51 头中心控制软件圈复杂度分析与改进火控雷达技术(2016年3期)2016-02-06给定不确定结果的量子比特的量子态区分*中山大学学报(自然科学版)(中英文)(2015年1期)2015-06-13