论文标题
查询有效的量子算法，可在一般图上进行最大匹配
A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs
论文作者
论文摘要
我们设计量子算法以最大程度地匹配。在查询模型中工作，在邻接矩阵和邻接列表设置中，我们都可以改进一般图形最著名的算法，与以前获得的两部分图的结果相匹配。特别是，对于带有$ n $节点和$ m $边缘的图表，我们的算法使$ o（n^{7/4}）$ QUERIES中的矩阵模型中的Queries和$ O（N^{3/4}（M+N）^{1/2}）$查询在列表模型中。我们的方法将Gabow的经典最大匹配算法[Gabow，fuldamenta Informaticae，'17]与Beigi和Taghavi的猜测树方法[Beigi和Taghavi，Quantum，'20]结合在一起。
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].
