量子科技中心_量科网

量子计算虽为特定问题带来指数级加速前景，但完全通用的量子计算机仍遥不可及，且近期设备固有噪声问题突出。鉴于此，该研究团队聚焦含噪声量子算法及𝖡𝖰𝖯与𝖡𝖯𝖵复杂性类别间的过渡地带。研究基于一种称为“ℓ阶傅里叶增长”（规模为ℓ的集合傅里叶系数绝对值之和）的关键技术——该技术原用于区分量子与经典算法，现被证明亦可鉴别采用不同资源类型的量子算法。研究表明，噪声对量子算法的影响会以与噪声类型深度关联的方式抑制其傅里叶增长。 具体而言，研究人员考察了两种高混合态普遍存在的含噪声量子计算模型：𝖣𝖰𝖢ₖ（含k个纯净量子比特，其余处于最大混合态）和½𝖡𝖰𝖯（初始态为最大混合态，但计算结束时获知初始态信息）。通过建立𝖣𝖰𝖢ₖ、½𝖡𝖰𝖯及𝖡𝖰𝖯算法傅里叶增长的上界，并利用这些上界间的差异，该工作实现了这些模型间的预言分离。特别地，研究证明2-关联与3-关联问题在𝖣𝖰𝖢₁和½𝖡𝖰𝖯模型中分别需要𝑁^Ω(1)次查询。这些结论通过一个可能具有独立学术价值的新矩阵分解引理得以验证。