量子科技中心_量科网

近期量子设备因量子比特数量有限，促使研究人员在数据流模型下研究空间受限的量子计算。该团队证明，在此设定下香农熵估计展现了量子与经典空间复杂度之间的指数级差异。从技术层面，研究人员开发了一种基于显式构造预言机的两阶段量子流算法，该预言机直接来源于流输入数据。该算法在精度参数上实现了对数级空间复杂度，而任何经典流算法都需要多项式级空间。值得注意的是，现有量子查询模型中关于香农熵估计的研究仅能实现二次加速。该工作确立了一个在计算机网络领域具有实际应用价值的自然问题，并揭示了量子查询复杂度与流空间复杂度之间的本质差距，首次展现了量子空间优势可达指数级的典型案例。