Quantum algorithms for graph connectivity and formula evaluation

Stacey Jeffery1 and Shelby Kimmel2

1QuSoft and CWI, Amsterdam, the Netherlands
2Middlebury College, Middlebury, VT, USA

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.

Share
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

► 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/http://dx.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
http:/​/​doi.acm.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
http:/​/​doi.acm.org/​10.1145/​2090236.2090258