Quantum Algorithms for Connectivity and Related Problems

Jarret, Michael; Jeffery, Stacey; Kimmel, Shelby; Piedrafita, Alvaro

doi:10.4230/LIPIcs.ESA.2018.49

File

LIPIcs.ESA.2018.49.pdf

Filesize: 484 kB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.ESA.2018.49
URN: urn:nbn:de:0030-drops-95121

Author Details

Michael Jarret

Perimeter Institute, Waterloo, ON, Canada

Stacey Jeffery

Qusoft CWI, Amsterdam, The Netherlands

Shelby Kimmel

Middlebury College, Middlebury, VT, USA

Alvaro Piedrafita

Qusoft CWI, Amsterdam, The Netherlands

Cite AsGet BibTex

Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum Algorithms for Connectivity and Related Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.49

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.

Subject Classification

ACM Subject Classification

Theory of computation → Graph algorithms analysis

Keywords

Electrical networks
Quantum algorithms
Span programs
Connectivity
Graph theory

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

A. Āriņš. Span-Program-Based Quantum Algorithms for Graph Bipartiteness and Connectivity, pages 35-41. Springer International Publishing, Cham, 2016. URL: http://dx.doi.org/10.1007/978-3-319-29817-7_4.
A. Belovs. Learning-graph-based quantum algorithm for k-distinctness. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pages 207-216, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.18.
A. Belovs. Span programs for functions with constant-sized 1-certificates. In Proceedings of the 44th Symposium on Theory of Computing (STOC 2012), pages 77-84, 2012.
A. Belovs and B. W. Reichardt. Span programs and quantum algorithms for st-connectivity and claw detection. In Proceedings of the 20th European Symposium on Algorithms (ESA 2012), pages 193-204, 2012.
C. Cade, A. Montanaro, and A. Belovs. Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness, 2016. arXiv:1610.00581.
C. Dürr, M. Heiligman, P. Høyer, and M. Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310-1328, 2006.
T. Ito and S. Jeffery. Approximate span programs. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pages 12:1-12:14, 2016. arXiv:1507.00432.
Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum algorithms for connectivity and related problems. arXiv preprint arXiv:1804.10591, 2018.
S. Jeffery and S. Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1:26, 2017. URL: http://dx.doi.org/10.22331/q-2017-08-17-26.
M. Karchmer and A. Wigderson. On span programs. In Proceedings of the 8th Annual IEEE Conference on Structure in Complexity Theory, pages 102-111, 1993.
N. Nisan and A. Ta-Shma. Symmetric logspace is closed under complement. In Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing (STOC 1995), pages 140-146, New York, NY, USA, 1995. ACM. URL: http://dx.doi.org/10.1145/225058.225101.
B. W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS 2009), pages 544-551, 2009. arXiv:quant-ph/0904.2759.
B. W. Reichardt. Span programs and quantum query algorithms. Electronic Colloquium on Computational Complexity (ECCC), 17:110, 2010.
B. W. Reichardt. Reflections for quantum query algorithms. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pages 560-569. SIAM, 2011.
B. W. Reichardt and R. Špalek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8(13):291-319, 2012.
M. Szegedy. Quantum speed-up of Markov chain based algorithms. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), pages 32-41, Washington, DC, USA, 2004. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2004.53.