Quantum algorithms for matching and network flows

Andris Ambainis; Robert Špalek

doi:10.1007/11672142_13

Quantum algorithms for matching and network flows

Andris Ambainis^*
, Robert Špalek

^*Corresponding author for this work

University of Waterloo
University of Amsterdam

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

41 Citations (Scopus)

Abstract

We present quantum algorithms for some graph problems: finding a maximal bipartite matching in time O(n√m log n), finding a maximal non-bipartite matching in time O(n ²(√m/n+log n) log n), and finding a maximal flow in an integer network in time O(min(n ^7/6√m · U ^1/3, √nUm) 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.

Original language	English
Title of host publication	STACS 2006
Subtitle of host publication	23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Pages	172-183
Number of pages	12
DOIs	https://doi.org/10.1007/11672142_13
Publication status	Published - 2006
Externally published	Yes
Event	STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings - Marseille, France Duration: 23 Feb 2006 → 25 Feb 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3884 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Country/Territory	France
City	Marseille
Period	23/02/06 → 25/02/06

Access to Document

10.1007/11672142_13

Cite this

Ambainis, A., & Špalek, R. (2006). Quantum algorithms for matching and network flows. In STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pp. 172-183). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3884 LNCS). https://doi.org/10.1007/11672142_13

@inproceedings{f4e7755415864ecda40a59b102784303,

title = "Quantum algorithms for matching and network flows",

abstract = "We present quantum algorithms for some graph problems: finding a maximal bipartite matching in time O(n√m log n), finding a maximal non-bipartite matching in time O(n 2(√m/n+log n) log n), and finding a maximal flow in an integer network in time O(min(n 7/6√m · U 1/3, √nUm) 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.",

author = "Andris Ambainis and Robert {\v S}palek",

year = "2006",

doi = "10.1007/11672142\_13",

language = "English",

isbn = "3540323015",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "172--183",

booktitle = "STACS 2006",

note = "STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings ; Conference date: 23-02-2006 Through 25-02-2006",

}

Ambainis, A & Špalek, R 2006, Quantum algorithms for matching and network flows. in STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3884 LNCS, pp. 172-183, STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings, Marseille, France, 23/02/06. https://doi.org/10.1007/11672142_13

Quantum algorithms for matching and network flows. / Ambainis, Andris; Špalek, Robert.
STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. 2006. p. 172-183 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3884 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

T1 - Quantum algorithms for matching and network flows

AU - Ambainis, Andris

AU - Špalek, Robert

PY - 2006

Y1 - 2006

N2 - We present quantum algorithms for some graph problems: finding a maximal bipartite matching in time O(n√m log n), finding a maximal non-bipartite matching in time O(n 2(√m/n+log n) log n), and finding a maximal flow in an integer network in time O(min(n 7/6√m · U 1/3, √nUm) 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.

AB - We present quantum algorithms for some graph problems: finding a maximal bipartite matching in time O(n√m log n), finding a maximal non-bipartite matching in time O(n 2(√m/n+log n) log n), and finding a maximal flow in an integer network in time O(min(n 7/6√m · U 1/3, √nUm) 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.

UR - https://www.scopus.com/pages/publications/33745606675

U2 - 10.1007/11672142_13

DO - 10.1007/11672142_13

M3 - Conference paper

AN - SCOPUS:33745606675

SN - 3540323015

SN - 9783540323013

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 172

EP - 183

BT - STACS 2006

T2 - STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings

Y2 - 23 February 2006 through 25 February 2006

ER -

Quantum algorithms for matching and network flows

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this