量子科技中心_量科网

最大匹配问题的量子查询复杂度下界为Ω(n^{3/2})，适用于由邻接矩阵表示的n个顶点构成的图。目前最优量子算法具有O(n^{7/4})的查询复杂度，这比平凡上界O(n^2)有所改进。构造一个查询复杂度打破O(n^{7/4})上界的量子算法仍是一个悬而未决的问题。量子行走技术是通过将经典随机游走搜索转化为量子搜索来构建量子算法的通用框架，该技术已成功应用于为另一问题构建具有紧致查询复杂度的算法。该工作表明，量子行走技术无法产生改进已知（甚至平凡）查询复杂度上界的快速算法。具体而言，若采用现有技术设计的量子行走算法能以任何常数ε>0的O(n^{2−ε})查询次数解决最大匹配问题，且底层经典随机游走与输入图无关，则其确保的时间复杂度将超过n的任意多项式。