Quantum algorithms for graph connectivity and formula evaluation

Stacey Jeffery; Shelby Kimmel

doi:10.22331/q-2017-08-17-26

Quantum algorithms for graph connectivity and formula evaluation

Stacey Jeffery¹ and Shelby Kimmel²

¹QuSoft and CWI, Amsterdam, the Netherlands
²Middlebury College, Middlebury, VT, USA

Published:	2017-08-17, volume 1, page 26
Eprint:	arXiv:1704.00765v2
Doi:	https://doi.org/10.22331/q-2017-08-17-26
Citation:	Quantum 1, 26 (2017).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Updated version: The authors have uploaded version v3 of this work to the arXiv which may contain updates or corrections not contained in the published version v2. The authors left the following comment on the arXiv:

This version fixes a bug in statement and proof of Lemma 32 (regarding time complexity of algorithms). This article supersedes arXiv:1511.02235

Abstract

We give a new upper bound on the quantum query complexity of deciding $st$-connectivity on certain classes of planar graphs, and show the bound is sometimes exponentially better than previous results. We then show Boolean formula evaluation reduces to deciding connectivity on just such a class of graphs. Applying the algorithm for $st$-connectivity to Boolean formula evaluation problems, we match the $O(\sqrt{N})$ bound on the quantum query complexity of evaluating formulas on $N$ variables, give a quadratic speed-up over the classical query complexity of a certain class of promise Boolean formulas, and show this approach can yield superpolynomial quantum/classical separations. These results indicate that this $st$-connectivity-based approach may be the "right" way of looking at quantum algorithms for formula evaluation.

Note added: The authors have post publication of this paper uploaded version 1704.00765v3, which fixes a bug in statement and proof of Lemma 32 (regarding time complexity of algorithms).

Popular summary

We show a connection between two important classes of problems in computer science: evaluating a logical formula, and deciding if two nodes in a network are connected by a path (called st-connectivity). The latter problem has a particularly elegant quantum algorithm, based on the model of "span programs''. We improve this algorithm for the special case when the network is planar, meaning no two edges of the network cross each other. We show that to evaluate a formula, it is sufficient to solve a related st-connectivity problem on a planar network, and so our new st-connectivity algorithm can also be used to evaluate formulas.

► BibTeX data

@article{Jeffery2017quantumalgorithms,
  doi = {10.22331/q-2017-08-17-26},
  url = {https://doi.org/10.22331/q-2017-08-17-26},
  title = {Quantum algorithms for graph connectivity and formula evaluation},
  author = {Jeffery, Stacey and Kimmel, Shelby},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {1},
  pages = {26},
  month = aug,
  year = {2017}
}

► References

[1] S. Aaronson and S. Ben-David. Sculpting quantum speedups. In Proceedings of the 31st Conference on Computational Complexity, CCC '16, pages 26:1–26:28, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-008-8. 10.4230/LIPIcs.CCC.2016.26. URL http://dl.acm.org/citation.cfm?id=2982445.2982471.
https://doi.org/10.4230/LIPIcs.CCC.2016.26
http://dl.acm.org/citation.cfm?id=2982445.2982471

[2] D. Aldous and J. Fill. Reversible Markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/ aldous/RWG/book.html.
http://www.stat.berkeley.edu/~aldous/RWG/book.html

[3] 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. 10.1145/2213977.2213985.
https://doi.org/10.1145/2213977.2213985

[4] 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. 10.1007/978-3-642-33090-2_18.
https://doi.org/10.1007/978-3-642-33090-2_18

[5] S. Ben-David and R. Kothari. Randomized query complexity of sabotaged and composed functions. In Proceedings of the 43th International Colloquium on Automata, Languages and Programming (ICALP 2016), volume 55, pages 60:1–60:14, 2016. 10.4230/LIPIcs.ICALP.2016.60.
https://doi.org/10.4230/LIPIcs.ICALP.2016.60

[6] M. Boyer, G. Brassard, P. Høyer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46 (4-5): 493–505, 1998. ISSN 1521-3978. 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P.
https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P

[7] G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53–74, 2002.

[8] C. Cade, A. Montanaro, and A. Belovs. Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness, 2016. arXiv:1610.00581.
arXiv:1610.00581

[9] A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari. The electrical resistance of a graph captures its commute and cover times. Computational Complexity, 6 (4): 312–340, 1996. 10.1007/BF01270385.
https://doi.org/10.1007/BF01270385

[10] G. A. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs. Journal of the London Mathematical Society, 1 (1): 85–92, 1952. 10.1112/jlms/s1-27.1.85.
https://doi.org/10.1112/jlms/s1-27.1.85

[11] P. G. Doyle and J. L. Snell. Random Walks and Electrical Networks, volume 22 of The Carus Mathematical Monographs. The Mathematical Association of America, 1984.

[12] R. J. Duffin. Topology of series-parallel networks. Journal of Mathematical Analysis and Applications, 10 (2): 303–318, 1965. ISSN 0022-247X. http://dx.doi.org/10.1016/0022-247X(65)90125-3. URL http://www.sciencedirect.com/science/article/pii/0022247X65901253.
https://doi.org/10.1016/0022-247X(65)90125-3
http://www.sciencedirect.com/science/article/pii/0022247X65901253

[13] 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. 10.1137/050644719.
https://doi.org/10.1137/050644719

[14] E. Farhi, J. Goldstone, and S. Gutmann. A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4 (8): 169–190, 2008. 10.4086/toc.2008.v004a008. arXiv:quant-ph/0702144.
https://doi.org/10.4086/toc.2008.v004a008
arXiv:quant-ph/0702144

[15] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th annual ACM Symposium on Theory of computing (STOC 1996), pages 212–219. ACM, 1996. 10.1145/237814.237866.
https://doi.org/10.1145/237814.237866

[16] R. Heiman and A. Wigderson. Randomized vs. deterministic decision tree complexity for read-once Boolean functions. Computational Complexity, 1 (4): 311–329, 1991. 10.1007/BF01212962.
https://doi.org/10.1007/BF01212962

[17] 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. 10.4230/LIPIcs.ICALP.2016.12. arXiv:1507.00432.
https://doi.org/10.4230/LIPIcs.ICALP.2016.12
arXiv:1507.00432

[18] M. Karchmer and A. Wigderson. On span programs. In Proceedings of the IEEE 8th Annual Conference on Structure in Complexity Theory, pages 102–111, 1993. 10.1109/SCT.1993.336536.
https://doi.org/10.1109/SCT.1993.336536

[19] S. Kimmel. Quantum adversary (upper) bound. Chicago Journal of Theoretical Computer Science, 2013 (4), 2011. 10.4086/cjtcs.2013.004.
https://doi.org/10.4086/cjtcs.2013.004

[20] T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy. Quantum query complexity of state conversion. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), pages 344–353, 2011. 10.1109/FOCS.2011.75.
https://doi.org/10.1109/FOCS.2011.75

[21] 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. 10.1109/FOCS.2009.55. arXiv:quant-ph/0904.2759.
https://doi.org/10.1109/FOCS.2009.55
arXiv:quant-ph/0904.2759

[22] B. W. Reichardt. Span programs and quantum query algorithms. Electronic Colloquium on Computational Complexity (ECCC), 17: 110, 2010.

[23] 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.

[24] B. W. Reichardt and R. Špalek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8 (13): 291–319, 2012. 10.4086/toc.2012.v008a013.
https://doi.org/10.4086/toc.2012.v008a013

[25] M. Saks and A. Wigderson. Probabilistic Boolean decision trees and the complexity of evaluating game trees. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (FOCS 1986), pages 29–38. IEEE, 1986. 10.1109/SFCS.1986.44.
https://doi.org/10.1109/SFCS.1986.44

[26] J. Valdes, R. E. Tarjan, and E. L. Lawler. The recognition of series parallel digraphs. In Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC 1979), pages 1–12. ACM, 1979. 10.1145/800135.804393. URL http://doi.acm.org/10.1145/800135.804393.
https://doi.org/10.1145/800135.804393

[27] B. Zhan, S. Kimmel, and A. Hassidim. Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS 2012), pages 249–265, New York, NY, USA, 2012. ACM. ISBN 978-1-4503-1115-1. 10.1145/2090236.2090258. URL http://doi.acm.org/10.1145/2090236.2090258.
https://doi.org/10.1145/2090236.2090258

Cited by

[1] Ahmed Zaiou, Younès Bennani, Mohamed Hibti, and Basarab Matei, IFIP Advances in Information and Communication Technology 646, 495 (2022) ISBN:978-3-031-08332-7.

[2] Shelby Kimmel and R. Teal Witter, Lecture Notes in Computer Science 12808, 543 (2021) ISBN:978-3-030-83507-1.

[3] Arnab Roy, Joseph L. Pachuau, and Anish Kumar Saha, Advances in Computers 128, 273 (2023) ISBN:9780323898102.

[4] Neelu Jyothi Ahuja and Sarthika Dutt, Lecture Notes on Data Engineering and Communications Technologies 133, 183 (2022) ISBN:978-3-031-04612-4.

[5] Peter Nimbe, Benjamin Asubam Weyori, and Adebayo Felix Adekoya, "Models in quantum computing: a systematic review", Quantum Information Processing 20 2, 80 (2021).

[6] Michael Jarret and Kianna Wan, "Improved quantum backtracking algorithms using effective resistance estimates", Physical Review A 97 2, 022337 (2018).

[7] Arjan Cornelissen, Stacey Jeffery, Maris Ozols, and Alvaro Piedrafita, "Span programs and quantum time complexity", arXiv:2005.01323, (2020).

The above citations are from Crossref's cited-by service (last updated successfully 2023-12-05 20:16:14) and SAO/NASA ADS (last updated successfully 2023-12-05 20:16:15). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.