研究证明子图检测的量子查询复杂度具有无条件超线性下界

论文基于摘要报告了子图检测量子查询复杂度的无条件超线性下界：固定阶团检测的下界指数严格递增，并随团规模接近2；固定连通图的下界也随色数增长而趋近二次。该结果针对邻接矩阵查询和常数错误率，核心证明依赖独立采样输入下的全1证书下界；仅凭摘要尚不能核验完整证明及其适用范围。 本站设想：可在相同查询模型和错误率下，比较这些下界与相应子图检测量子算法的上界是否吻合。