We design quantum algorithms for maximum matching. Working in the query model, in both adjacency matrix and adjacency list settings, we improve on the best known algorithms for general graphs, matching previously obtained results for bipartite graphs. In particular, for a graph with $n$ nodes and $m$ edges, our algorithm makes $O(n^{7/4})$ queries in the matrix model and $O(n^{3/4}(m+n)^{1/2})$ queries in the list model. Our approach combines Gabow's classical maximum matching algorithm [Gabow, Fundamenta Informaticae, '17] with the guessing tree method of Beigi and Taghavi [Beigi and Taghavi, Quantum, '20].
翻译：我们设计了最大匹配的量子算法。 在查询模型中, 在相邻矩阵和相邻列表设置中, 我们改进了一般图形最已知的算法, 匹配了先前双面图形的结果。 特别是, 对于一个用美元节点和美元边缘的图表, 我们的算法在矩阵模型中查询$O( n ⁇ 7/4} $) 和在列表模型中查询$O( n ⁇ 3/4} (m+n) ⁇ 1/2} 。 我们的方法将加博的经典最大匹配算法[ Gabow, Fundamenta Informaticae,'17] 与Beigi 和 Taghavi [Beigi 和 Taghavi, Quantum, '20] 的猜测树法结合起来。
相关内容
微信扫码咨询专知VIP会员