量子科技中心_量科网

该研究团队针对最大入度和出度受限于某通用常数d的有向图，开展了量子特性测试研究。对于邻近度参数ε，研究表明：任何在经典双向模型（可同时访问入边和出边）中仅需Oε,d(1)次查询即可测试的特性，在量子单向模型（仅能访问出边）中同样可通过n1/2−Ωε,d(1)次查询完成测试。这一发现实现了相对于单向模型中最优经典算法的近乎二次量子加速。 研究进一步证明该转化过程具有近乎紧致性：通过构建一个显式特性Pε，其在双向模型中仅需Oε(1)次经典查询即可完成ε测试，但在单向模型中需要Ω~(n1/2−f′(ε))次量子查询，其中f′(ε)是随ε趋近于0而趋近于0的函数。 作为副产品，该研究还表明：在单向模型中，使用o(n)次量子查询即可将任意固定尺寸子图H的出现次数估计精度控制在δn的加性误差范围内。