Abstract
An important family of span programs, stconnectivity 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 1input, and the largest negative witness size of any 0input. 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 stconnectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on stconnectivity 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:149:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9512},
URN = {urn:nbn:de:0030drops95121},
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 