2017/04/03 by Stacey Jeffery, Jeffery, Stacey, Shelby Kimmel +1 · 2 citations
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #cs.DS #quant-ph
paper · pdf · doi:10.48550/arxiv.1704.00765
This version fixes a bug in statement and proof of Lemma 32 (regarding time complexity of algorithms). This article supersedes arXiv:1511.02235
arxiv created 2019/12/18 · arxiv updated 2019/12/19
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.