Quantum Algorithms for Matching and Network Flows

DOI10.1007/11672142_13zbMATH Open1136.68395arXivquant-ph/0508205OpenAlexW2120252658MaRDI QIDQ5449796FDOQ5449796

Authors: Robert Špalek, Andris Ambainis 

Publication date: 19 March 2008

Published in: STACS 2006 (Search for Journal in Brave)

Abstract: We present quantum algorithms for the following graph problems: finding a maximal bipartite matching in time O(n sqrt{m+n} log n), finding a maximal non-bipartite matching in time O(n^2 (sqrt{m/n} + log n) log n), and finding a maximal flow in an integer network in time O(min(n^{7/6} sqrt m * U^{1/3}, sqrt{n U} m) log n), where n is the number of vertices, m is the number of edges, and U <= n^{1/4} is an upper bound on the capacity of an edge.

Full work available at URL: https://arxiv.org/abs/quant-ph/0508205

Recommendations

• Quantum algorithms for matching problems
• Quantum algorithms for connectivity and related problems
• A query-efficient quantum algorithm for maximum matching on general graphs
• Quantum algorithms
• scientific article; zbMATH DE number 1839431
• Quantum Algorithms
• Applications of the quantum algorithm for st-connectivity
• Quantum search of matching on signed graphs
• Quantum computational networks
• scientific article; zbMATH DE number 2132448

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Quantum computation (81P68) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (9)

• Quantum search for the dating market
• Title not available (Why is that?)
• Quantum bridge analytics. II: QUBO-plus, network optimization and combinatorial chaining for asset exchange
• Quantum algorithms for matching problems
• Quantum algorithm for dynamic programming approach for DAGs and applications
• A query-efficient quantum algorithm for maximum matching on general graphs
• Symmetries, graph properties, and quantum speedups
• The quantum query complexity of the determinant
• Quantum algorithm for shortest path search in directed acyclic graph

This page was built for publication: Quantum Algorithms for Matching and Network Flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5449796)