TY - JOUR T1 - Quantum Algorithms for Graph Connectivity and Formula Evaluation Y1 - 2017 A1 - Stacey Jeffery A1 - Shelby Kimmel AB -

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( √ 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.

UR - https://arxiv.org/abs/1704.00765 ER -