Quantum Algorithms for Graph Connectivity and Formula Evaluation


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.
Submitted 3 Apr 2017 to Quantum Physics [quant-ph]
Published 5 Apr 2017
Updated 16 Aug 2017
Subjects: quant-ph cs.CC cs.DS
Author comments: Quantum version. (Typos fixed, sections clarified, template updated.) This article supersedes arXiv:1511.02235