量子科技中心_量科网

子图包含问题的量子查询复杂度一直是研究热点，这类问题要求判断输入图 G 中是否包含给定的子图 H。这一兴趣不仅源于这些问题自然且动机明确的表述形式，更源于为求解这些问题而涌现的一系列新颖量子算法技术。值得注意的是，即使是针对路径和环等相对简单的子图，其查询复杂度的完整理解仍然悬而未决。 在本工作中，该团队研究了邻接矩阵模型下路径和环包含问题的若干变体，主要关注长度为常数 k ∈ O(1) 的路径或环的搜索。该团队比较了有向图与无向图、目标是检测还是寻找路径/环的存在性、以及寻找的路径/环长度恰好为 k 或至多为 k 等不同设置。同时，该团队还考虑了这些问题的若干承诺版本，即预先知道输入图具有特定结构的情形。通过使用随机归约将这些问题相互关联，并将其归入若干等价类，该团队刻画了路径和环包含问题这些变体之间的相对难度。 当该团队将注意力限制在路径包含问题上时，这导致了一个二分性结论。部分路径包含问题可以用线性数量次查询求解，而所有其他问题在随机归约下（至多常数乘法开销）彼此等价（同时与若干环包含问题也等价）。针对后一个等价类，该团队提出了一种新颖的基于量子游走的算法，实现了查询复杂度 Õ(n^{3/2 - α_k})，其中 α_k ∈ Θ(c^{-k})，c = (3+√17)/2 ≈ 1.33，优于此前该问题查询复杂度的最佳上界 O(n^{3/2})。该团队还基于图碰撞问题给出了一个条件性下界，表明该等价类不存在线性查询的量子算法，除非图碰撞问题存在 O(n) 查询算法。