量子科技中心_量科网

计算模型通常假设运算以固定的顺序执行。近年来，多项研究开始探索放宽这一假设，考虑无固定因果结构的计算方式，并证明此类“因果非确定性”计算可在多种任务中带来优势。近期，布尔函数的量子查询复杂度被用作标准计算复杂度理论框架下探究其计算能力的工具，但迄今尚未发现精确查询复杂度上的分离现象。本文从更简单且完全经典的布尔函数确定性查询复杂度概念入手，以可能呈现因果非定性的经典确定性过程作为广义计算框架，对这一问题展开研究。研究团队首先证明，确定性查询复杂度的标准多项式下限和证书下限在此类广义模型中依然成立。随后，团队构造了一个布尔函数实例，证明因果非定性可降低其查询复杂度，并将该优势放大为多项式级别的分离。最后，基于经典确定性场景的研究启示，研究人员给出一个量子查询复杂度因因果非定性计算而降低的布尔函数实例。