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

摘要

在信息处理任务中，多方共享的随机变量和量子纠缠都是重要的计算资源，其中共享的随机变量也被称为经典关联。经典关联生成问题研究的是生成目标关联所需消耗的最少随机性或量子纠缠的数量。该文综述性地介绍了在经典场景、量子场景以及经典、量子混合场景下的经典关联生成协议。其中，非负秩和半正定秩分别刻画了生成目标关联所需共享的最少随机性与量子纠缠的量。基于这一结果，事先共享量子纠缠相比于事先共享随机性展示出了指数级优势。考虑到近期可实现的量子设备规模有限，经典、量子混合场景下的经典关联生成协议是一个现实的选择。在可操控的量子系统大小有限的前提之下，可用k区块半正定秩来量化完成经典关联生成任务所需通讯的最少经典比特。在这一混合协议中，量子资源仍能表现出相对经典资源而言的巨大优越性。由此可见，经典关联生成问题提供了一个新的视角来对比量子资源和经典资源之间的差别。

关键词

通讯复杂度 / 关联复杂度 / 关联生成 / 混合协议 / 量子优势