License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.49
URN: urn:nbn:de:0030-drops-95121
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9512/
Jarret, Michael ;
Jeffery, Stacey ;
Kimmel, Shelby ;
Piedrafita, Alvaro
Quantum Algorithms for Connectivity and Related Problems
Abstract
An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs.
We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa>1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian.
BibTeX - Entry
@InProceedings{jarret_et_al:LIPIcs:2018:9512,
author = {Michael Jarret and Stacey Jeffery and Shelby Kimmel and Alvaro Piedrafita},
title = {{Quantum Algorithms for Connectivity and Related Problems}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {49:1--49:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-081-1},
ISSN = {1868-8969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9512},
URN = {urn:nbn:de:0030-drops-95121},
doi = {10.4230/LIPIcs.ESA.2018.49},
annote = {Keywords: Electrical networks, Quantum algorithms, Span programs, Connectivity, Graph theory}
}
|
Keywords: |
|
Electrical networks, Quantum algorithms, Span programs, Connectivity, Graph theory |
|
Collection: |
|
26th Annual European Symposium on Algorithms (ESA 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
14.08.2018 |
