多党同时通信中量子通信与公开随机性的分离界限

作者证明，在无共享随机性和预共享纠缠的多党同时消息传递模型中，量子协议相对于经典公开硬币协议存在多项式与指数通信分离。论文分别对 XOR Equality 和 Multiparty Index Coordination 给出量子通信下界，同时展示经典公开硬币协议以每名玩家少量比特或 $O(log n)$ 最大消息长度完成任务。